Олимпиадная задача: определение тяжелой монеты среди 239 — теория алгоритмов, 10-11 класс

  Разобьём все монеты на группы А, Б, В и Г из соответственно 60, 60, 60 и 59 монет. Сначала сравним А с Б, затем Б с В. Фальшивые монеты могут быть не более, чем в двух кучках. Поэтому веса по крайней мере двух из взвешенных кучек равны. Следовательно, возможны только два результата.

  1) Веса всех взвешенных кучек равны. Это значит, что все 90 взвешенных монет – настоящие. Отложив из A любую монету и сравнив остальное с Г, узнаем требуемое.

  2) Веса двух кучек равны, а вес третьей – другой, например,  A = Б > В.  Тогда либо в А и в Б есть по фальшивой монете и они тяжелее настоящих, либо в В есть фальшивые монеты (одна или две) и они легче настоящих. Разделив А на две равные кучки и сравнив их между собой, определим, есть ли там фальшивая монета. Тем самым выяснится, какой из двух случаев имеет место.