Олимпиада имени Леонарда Эйлера2012-2013 учебный год, II тур регионального этапа

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

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Решение. Выделим три кучки I, II, III по три монеты в каждой. Сравним кучки I и II, а затем — кучки II и III. Если все три кучки равны по весу, то все монеты в них настоящие, и мы нашли даже 9 монет. В противном случае одна из кучек отличается по весу от других, и нам известно — какая (если в одном из взвешиваний две кучки равны по весу, то фальшивая в третьей; иначе II отличается по весу как от I, так и от III, и фальшивая может быть только в II). Тогда искомые восемь монет — это остальные две кучки и две неиспользованные монеты.
Замечание. Приведённый способ — не единственный возможный.

Можно поделить 11 монет на 3 кучи, по 5 5 1 монет. Если 5 и 5 равны, то можно расплатиться ими, ну а если не так, то 5+1 монет уже настоящие. И теперь 5 монет разбиваем на кучи по 2 2 1 монет и взвешиваем 2 и 2 монетки. Если они равны, то это значит что III кучка фальшивая, а если нет то среди дыух ост. монет будет фальшивая.

Итого:

5 5 1

/ \

2 2 1

/ \

1 1

Таким способом мы сможем расплатиться 8 настоящими монетами, горантированно. Примечание, данный способ не является единственным