Олимпиада имени Леонарда Эйлера2013-2014 учебный год, I тур заключительного этапа

Среди 49 одинаковых на вид монет — 25 настоящих и 24 фальшивых. Для определения фальшивых монет имеется тестер. В него можно положить любое количество монет, и если среди этих монет больше половины — фальшивые, тестер подает сигнал. Как за пять тестов найти две фальшивых монеты? ( К. Кноп )

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

Комментарии от администратора Комментарии от администратора №1.     Решение. Назовём «рабочими» те монеты, среди которых мы продолжаем искать пару фальшивых. Ситуацию «рабочими являются $N$ монет, среди которых не менее $M$ фальшивых» будем обозначать $N:M$. Если на очередном тесте был сигнал (обозначим это "+"), то после этого мы считаем рабочими те и только те рабочие монеты, которые в тесте участвовали, а если сигнала не было (« - »), то продолжим считать рабочими те и только те рабочие монеты, которые в этом тесте не участвовали. Вначале имеем ситуацию 49:24. Приведём возможный алгоритм решения задачи.
Тест 1: тестируем 27 монет. +: ситуация 27:14, - : ситуация 22:11.
Тест 2 для ситуации 27:14: тестируем 16 монет. +: ситуация 16:9, - : ситуация 11:6.
Тест 2 для ситуации 22:11: тестируем 16 монет. При обоих вариантах — ситуация 11:6.
Тест 3 для ситуации 16:9: тестируем 8 монет. При обоих вариантах — ситуация 8:5.
Тест 4 для ситуации 8:5: тестируем 4 монеты. При обоих вариантах — ситуация 4:3. Тест 5 для ситуации 4:3: тестируем две монеты. При обоих вариантах — ситуация 2:2, то есть мы нашли пару фальшивых.
Тест 3 для ситуации 11:6: тестируем 8 монет. +: ситуация 8:5, тесты 4 и 5 для которой указаны выше; - : ситуация 3:2. Тесты 4 и 5 для ситуации 3:2 — тестируем дважды по одной монете. Либо обе они окажутся фальшивыми («+»), либо одна будет настоящей (« - »), тогда другой фальшивой монетой будет третья из оставшихся.