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

На столе лежат 100 одинаковых с виду монет, из которых 85 фальшивых и 15 настоящих. В вашем распоряжении есть чудо-тестер, в который можно положить две монеты и получить один из трех результатов — «обе монеты настоящие», «обе монеты фальшивые» и «монеты разные». Можно ли за 64 таких теста найти все фальшивые монеты? ( К. Кноп )

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

Комментарии от администратора Комментарии от администратора №1.     Ответ. Можно.
Решение. Приведём один из возможных вариантов определения фальшивых монет. Разделим монеты на 50 пар и проверим все пары, кроме одной. Мы узнаем количество фальшивых в каждой паре. Поскольку общее число фальшивых монет известно, мы узнаем также, сколько фальшивых в оставшейся паре. Нам осталось выяснить, какая монета фальшивая в каждой из пар, состоящих из разных монет. Для этого заметим, что есть пара, в которой обе монеты фальшивые, потому что фальшивых монет больше 50. Возьмем монету из такой пары и протестируем с ней по одной монете из каждой пары, где обе монеты разные. Таких пар не более 15, поскольку у нас только 15 настоящих монет. Поэтому всего мы использовали не более $49+15=64$ тестов.