Эйлер атындағы олимпиада, 2011-2012 оқу жылы, аймақтық кезеңнің 1 туры

Сырт жағынан бірдей болып келетін 100 тиын устел үстінде жатыр. Оның 85-і жалған, 15-і шың. Бізде ғажайып тестер бар. Егер сол тестерге екі тиынды салсақ, екеуі де жалған», «екеуі де шың» және «тиындар әр түрлі» деген жауап аламыз. Осындай 64 тесттің көмегімен барлық жалған тиындарды табуға бола ма? ( К. Кноп )

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

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