KBOB: Все сообщения за 12 Декабря 2002 года

Из m=(n**3+1)/2 монет + одна заведомо настоящая монета, можно найти фальшивую за n взвешиваний.

1. Из двух монет + настоящая монета, за одно взвешивание находим фальшивую (тривиально).

2. Из пяти монет + настоящая монета, за два взвешивания.
на весах - 2/1+настоящая монета, еще две монеты в стороне.
Весы в рановесии - фальшивая монета среди двух, переходим к п.1
Весы не в равновесии - две монеты не лежащие на весах являются настоящими.
Одну из монет (не явл. заведомо настоящей) снимаем с весов, другую (так-же не заведомо настоящую) с соседней чашки переносим на место снятой, на освободившееся место кладем одну из двух настоящих монет (не лежавших до этого на весах).
Если весы пришли в равновесие, то мы сняли фальшивую монету.
Если показания весов не изменились то фальшивая монета затронута не была.
Если стрелка весов отклонилась в противоположную сторону фальшивая монета была перенесена с одной чашки на другую.

3. Из четырнадцати монет + настоящая, за три взвешивания
на весах - 5/4+настоящая монета, еще пять монет в стороне.
Весы в равновесии - фальшивая монета среди пяти, переходим к п.2
Весы не в равновесии - пять монет не лежащих на весах являются настоящими.
Три монеты (не включающие. заведомо настоящюю) снимаем с одной чашки весов, другие три (не вкл. заведомо настоящую) с соседней чашки переносим на место снятых, на освободившееся место кладем три из пяти настоящих монет (не лежавших до этого на весах).

Если весы пришли в равновесие, то фальшивая монета среди трех снятых. Если показания весов не изменились то фальшивая среди трех нетронутых монет, Если стрелка весов отклонилась в противоположную сторону - фальшивая монета среди трех перемещенных. (теперь мы знаем отличие в весе фальшивой монеты от настоящей!).
Последним взвешиванием определяем из трех монет фальшивую.

4. Из 41-й монеты + настоящая за четыре взвешивания.
на весах - 14/13+настоящая монета, 14 монет в стороне.
Весы в рановесии - фальшивая монета среди 14-ти, переходим к п.3

Весы не в равновесии - 14-ть монет не лежащих на весах являются настоящими.
9-ть монет (не включающие. заведомо настоящюю) снимаем с одной чашки весов, другие 9-ть (не вкл. заведомо настоящую) с соседней чашки переносим на место снятых, на освободившееся место кладем 9-ть из 14-ти настоящих монет (не лежавших до этого на весах).
Определяем, по показаниям весов, среди каких 9-ти монет фальшивая.
Из этих 9-ти монет за два взвешивания, зная отличие в весе фальшивой монеты от настоящей, находим ответ. (тривиально)

Каждое взвешивание имеет три исхода, три взвешивания дают 27 различных исходов.
Положение фальшивой монеты среди 14-ти возможно 14-тью различными способами, однако существует дополнительная информация о том тяжелее или легче фальшивая монета, чем настоящая. (по условию задачи этого не требовалось определить, "но придется").
С учетом этого существует 28 начальных состояний системы из 13-ти настоящих монет и одной фальшивой.

Вроде бы 28>27 Но в одном, единственном случае фальшивая монета так и не попадает на весы (когда во всех взвешиваниях весы оказывались в равновесии)! Т.е. мы находим где фальшивая монета, но не знаем каков ее вес (в сравнении с настоящей)! Поэтому возможных состояний на самом деле только 27.

А если по условию требуется все же определить, вовсех случаях, тяжелее или легче фальшавая монета, то можно ли это сделать для 13-ти монет?

•  инфо
•  инструменты
• Ответить на сообщение