Задачки

Условие

В некоторой куче настоящих монет больше, чем фальшивых. Все настоящие монеты весят одинаково. Любая фальшивая монета отличается по весу от настоящей. Можно использовать чашечные весы, владелец которых после каждого взвешивания забирает себе в качестве арендной платы любую (выбранную им) монету из двух только что взвешенных. Верно ли, что можно выделить хотя бы одну настоящую монету и оставить ее себе?

Подсказка

Можно ли каким-то образом уменьшить общее количество монет так, чтобы настоящих по-прежнему было больше?

Решение

Ответ: да. Ниже описан способ, позволяющий выделить и оставить у нас меньшее число монет, причем среди оставшихся настоящих будет больше, чем фальшивых. Тогда рано или поздно мы дойдем до того, что монет останется одна или две; настоящих среди них будет больше, чем фальшивых, поэтому все они будут настоящие.
Рассмотрим два случая.
Число монет четно. Разобьем их на пары и взвесим. Если весы при каком-то взвешивании показали равенство, то монеты либо обе настоящие, либо обе фальшивые. Равенств среди настоящих монет должно быть больше, чем среди фальшивых. В следующий этап проходят по одной монете из каждого такого равенства (которые останутся после того, как заберет плату хозяин весов).
Число монет нечетно. Разобьем их на пары и еще одну монету. Произведем взвешивания в каждой паре, подсчитаем число равенств. Если их нечетное число, то отберем как и прежде, по одной монете из каждого равенства (так как равенств среди настоящих монет не может быть меньше, чем среди фальшивых). Если же равенств четное число, то возьмем оставленные нам хозяином весов монеты из равенств и добавим к ним оставленную ранее в стороне монету. Настоящих монет опять больше, чем фальшивых.

MMOnline