Вариант боев 1 (8)

Решение. Сравним между собой две монеты, затем две другие, затем еще две другие и так далее, до тех пор, пока все монеты, кроме, может быть, одной, не побывают по одному разу на весах. Покажем, что в результате наша задача сведется к аналогичной задаче, но с меньшим числом монет.

Пусть k раз сравнивались между собой настоящие монеты, l раз — одинаково весящие фальшивые монеты, m раз одна из монет перевешивала другую. Значит, куча состояла из 2k + 2l + 2m или 2k + 2l + 2m + 1 монет. Количество настоящих монет среди них не превосходило 2k + m или 2k + m + 1 соответственно.

В первом случае имеем неравенство 2k + m > k + l + m, откуда k > l.

Во втором случае имеем неравенство 2k + m + 1 ³ k + l + m = 1, откуда k ³ l, причем равенство k = l возможно только тогда, когда монета, не побывавшая на весах, — настоящая.

Следовательно, новая куча, куда мы соберем те и только те из оставшихся у нас монет, которые не участвовали в фиксировавших неравенство масс взвешиваниях, будет удовлетворять таким же условиям, что и исходная.

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

Автор задачи — С.Токарев, г.Иваново