Question

Имеется 11 мешков с монетами и весы с двумя чашками и стрелкой, которые показывают, на какой чашке груз тяжелее и на сколько именно.Известно, что в одном мешке все монеты фальшивые, а в остальных — все монетынастоящие. Все настоящие монеты имеют одинаковый вес, а все фальшивые — такжеодинаковый, но другой вес. За какое наименьшее число взвешиваний можноопределить, в каком мешке лежат фальшивые монеты?

Answer 1

Ответ: за два взвешивания. Первое взвешивание. На одну чашку кладем по одной монете из 10 мешков, на другую – 10 монет из оставшегося мешка. Второе взвешивание. На первую чашу кладем 1 монету из первого мешка, 2 монеты из второго, 3 – из третьего, ..10 монет из десятого. На другую – 55 монет из последнего (того же, что в прошлый раз) мешка. Покажем, как определить мешок с фальшивыми монетами, иходя из результатов этих двух взвешиваний. Пусть x – разность между весом фальшивой и настоящей монеты (возможно, x<0 ), i – номер мешка с фальшивыми монетами. Случай 1. i<11 . Тогда при первом взвешивании весы покажут разность весов x, а при втором – ix . Случай 2. i=11 . Тогда при первом взвешивании весы покажут число -10x, а при втором – -55x . Отсюда ясно, как можно определить мешок с фальшивыми монетами. Посчитаем отношение показаний весов при первом и втором взвешивании. Если это отношение – целое число, то оно равно номеру мешка с фальшивыми монетами (случай 1). Если же оно – нецелое, то фальшивые монеты находятся в мешке номер 11 (случай 2)

Answer 2

Для решения этой задачи можно использовать метод деления пополам или двоичного поиска. 1. Разделим все 11 мешков на две группы – по 5 и по 6 мешков. 2. Положим на весы по одному мешку из каждой группы. 3. Если весы показывают, что груз тяжелее с одной стороны, то знаем, что фальшивые монеты находятся в этой группе. Перейдем к шагу 4. 4. Разделим группу с 5 мешками на две подгруппы – по 2 и 3 мешка. 5. Положим на весы по одному мешку из каждой подгруппы. 6. Если весы показывают, что груз тяжелее с одной стороны, то знаем, что фальшивые монеты находятся в этой подгруппе. Перейдем к шагу 7. 7. Взвесим две монеты из подгруппы с 2 мешками. 8. Если весы показывают различие, то та монета, которая была положена на весы дважды, является фальшивой. 9. Если весы показывают одинаковый вес, то фальшивые монеты находятся в оставшемся мешке. 10. Если на шаге 6 весы показывают одинаковый вес, то фальшивые монеты находятся в оставшемся мешке из группы с 6 мешками. Таким образом, наименьшее число взвешиваний, необходимых для определения мешка с фальшивыми монетами, равно 3.