Олимпиадная задача: определение тяжелой монеты среди 239 — теория алгоритмов, 10-11 класс
Задача
Из 239 неотличимых на вид монет две – одинаковые фальшивые, а остальные – одинаковые настоящие, отличающиеся от фальшивых по весу. Как за три взвешивания на чашечных весах без гирь выяснить, какая монета тяжелее – фальшивая или настоящая? Сами фальшивые монеты находить не нужно.
Решение
Разобьём все монеты на группы А, Б, В и Г из соответственно 60, 60, 60 и 59 монет. Сначала сравним А с Б, затем Б с В. Фальшивые монеты могут быть не более, чем в двух кучках. Поэтому веса по крайней мере двух из взвешенных кучек равны. Следовательно, возможны только два результата.
1) Веса всех взвешенных кучек равны. Это значит, что все 90 взвешенных монет – настоящие. Отложив из A любую монету и сравнив остальное с Г, узнаем требуемое.
2) Веса двух кучек равны, а вес третьей – другой, например, A = Б > В. Тогда либо в А и в Б есть по фальшивой монете и они тяжелее настоящих, либо в В есть фальшивые монеты (одна или две) и они легче настоящих. Разделив А на две равные кучки и сравнив их между собой, определим, есть ли там фальшивая монета. Тем самым выяснится, какой из двух случаев имеет место.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь