Решение. Весы и 12 монет (#102)
Идея 1. Если мы положили на весы не все монеты, то после такого взвешивания непременно обнаружатся подлинные монеты.
Идея 2. Если монета лежит на весах, то есть три варианта действий над ней: не трогать, переложить на другую чашу, убрать с весов. В зависимости от реакции весов можно делать выводы о монетах.
Конечно, имеет смысл класть на чаши только равное количество монет.
Динамическое решение — это такое решение, когда каждое последующее взвешивание зависит от результатов предыдущих. Ниже станет понятнее, что имеется в виду. Занумеруем монеты от 1 до 12. Изобразим решение в виде графа, в вершинах которого стоит конкретное взвешивание, а по рёбрам от вершины идут результаты данного взвешивания.
Покажем как читать граф на примере одного пути от корня (первое взвешивание) к листу (ответ)
1-е взвешивание. Сравниваем (1 2 3 4) и (5 6 7 8). Пусть левая чаша легче, тогда идём по левой ветке ‘<’. При этом монеты (9 10 11 12) можно пометить, как настоящие.
2-е взвешивание. Сравниваем (1 2 5) и (3 4 9). Пусть на весах равенство, тогда идём по правой ветке. В этом случае фальшивка среди тех монет, что не участвовали во втором взвешивании.
3-е взвешивание. Сравниваем (6) и (7). Пусть правая чаша легче, тогда идём по средней ветке. Фальшивка — монета с номером 6 и она тяжелее. Действительно, раз весы показали неравенство, значит фальшивка лежит на весах и она либо (6), либо (7). Вспомним 1-е взвешивание, тогда правая чаша с монетами (6) и (7) была тяжелее. Следовательно, фальшивка тяжелее, и она лежит на левой чаше при последнем взвешивании.
Статическое решение — это такое решение, когда взвешивания определены заранее и не зависят от результатов предыдущих взвешиваний. Рассмотрим таблицу взвешиваний
В таблице номера столбцов соответствуют номерам монет, а строки определяют взвешивания: 0 — монета не участвует во взвешивании, 1 — кладется на первую чашу, 2 — кладется на вторую чашу. В результате трёх взвешиваний определяется так называемый синдром, то есть тройка чисел, которая однозначно указывают на номер фальшивой монеты. Этот номер равен номеру столбца с соответствующим синдромом. Например, если синдром равен (2,2,0), то фальшивой является монета с номером 6, и она тяжелее настоящих.
Идея в составлении таблицы следующая
— Все тройки в столбцах должны быть разные (иначе невозможно будет различить монеты)
— В каждой строке должно быть одинаковое количество 0, 1, 2
Дополнительное чтение: Шестопал Г., Как обнаружить фальшивую монету, Квант, 1979, выпуск 10
