Решение задачи "Куча монет" неверное

Автор темы Олег Федько 
01.04.2004 19:46
Олег Федько
Решение задачи "Куча монет" неверное
Напомню условие:
В некоторой куче настоящих монет больше, чем фальшивых. Все настоящие монеты весят одинаково. Любая фальшивая монета отличается по весу от настоящей. Можно использовать чашечные весы, владелец которых после каждого взвешивания забирает себе в качестве арендной платы любую (выбранную им) монету из двух только что взвешенных. Верно ли, что можно выделить хотя бы одну настоящую монету и оставить ее себе?

Решение гласит что можно, а на самом деле не всегда.

Контрпример:
у нас 3 монеты: 2 настоящие и одна фальшивая.
Над надо выбрать 2 монеты для взвешивания, т.к. мы не знаем где какие, то МОЖЕМ выбрать 1 настоящую и 1 фальшивую.
Так как владелец весов не знает какая из них настоящая, он берёт наугад и с вероятностью 50% МОЖЕТ взять настоящую. Таким образом, остаётся 1 настоящая монета и 1 фальшивая, опять таки владелец весов с вероятностью 50% МОЖЕТ взять настоящую. И нам останется 1 фальшивая.
То есть говоря коротко, не существует стратегии которая гарантировала бы нам хотя бы одну настоящую монету, если вначале их было 2 и 1.
01.04.2004 23:06
Basilisk
А зачем второй раз взвешивать?
Если на весах не было равновесия, то, в случае 2 настоящих и 1
фалшивая, оставшаяся монетка будет настоящей.
P.S. Условие задачи я не читал :-)
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти