Решение задачи 509

Условие:
Из 16 монет две фальшивые, более легкие. Чашечные весы недостаточно чувствительны, поэтому если на них положить настоящую и фальшивую монету, то они остаются в равновесии. Но две настоящие монеты перевешивают две фальшивые. Можно ли найти обе фальшивые монеты за 6 взвешиваний?

Решение:
Кодируем монеты четырьмя битами, коды попарно различны. Делаем следующие четыре взвешивания: в рамках i-го взвешивания на левую чашу весов кладем монеты, у которых в i-ом разряде кода стоит 0, а на правую -- те монеты, у которых в i-ом разряде кода стоит 1.

Если во время i-го взвешивания чаши в равновесии, значит фальшивые монеты находятся в разных группах. Делаем вывод, что у фальшивых монет в коде i-ые биты различаются. Если же одна из чаш перевесила, то обе фальшивые монеты находятся на другой чаше. Тогда i-ые биты в кодах фальшивых монет совпадают и мы точно знаем, чему именно равны (если перевесила правая, то 0, иначе 1).

Получается, для каждого бита мы точно знаем чему он равен у обеих фальшивых монет или то, что они различны. Тогда потенциальные фальшивые монеты можно разбить на пары. Для монет из одной пары каждые биты совпадают и равны чему-то или различаются согласно первым четырем взвешиваниям. Обе фальшивые монеты находятся в одной паре. Пар будет восемь, либо четыре, либо две или одна.

Например, мы выяснили, что первые два бита у фальшивых монет равны единицам, а вторые два различаются. Тогда потенциальные пары следующие: (1100, 1111) и (1101, 1110).

Теперь можно считать, что пара монет это одна большая монета и весы обычные чувствительные. Задача за два взвешивания найти фальшивую, которая легче. Как это сделать, имея восемь монет (или меньше), известная задача. Оставляем читателю в качестве упражнения.

Ответ: Можно.