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

Сырт жағынан бірдей 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 — тестируем дважды по одной монете. Либо обе они окажутся фальшивыми («+»), либо одна будет настоящей (« - »), тогда другой фальшивой монетой будет третья из оставшихся.