Олимпиадная задача по теории алгоритмов с картами
Фокусник выкладывает в ряд колоду из 52 карт и объявляет, что 51 из них будут выкинуты со стола, а останется тройка треф. Зритель на каждом шаге говорит, какую по счёту с края карту надо выкинуть, а фокусник выбирает, с левого или с правого края считать, и выкидывает соответствующую карту. При каких начальных положениях тройки треф можно гарантировать успех фокуса?
Показать ответ
При крайних положениях.
Разобрать решение
Тройку треф придётся выбросить, только если она в какой-то момент окажется в центре ряда, иначе можно выбросить другую карту. Так как ряд всегда содержит больше одной карты, то крайнюю карту можно сохранить до конца.
Пусть тройка треф Т сначала была не с краю. Приведём две стратегии для зрителя. Стратегия 1. Зритель называет что угодно, кроме крайних чисел, не давая удалять крайние карты. Когда останется три карты, тройка треф (если она ещё будет на столе) окажется в центре. Зритель назовёт 2. Стратегия 2. Зритель всегда называет номер положения Т. Фокусник будет выкидывать другую карту (у него нет выбора), уменьшая на единицу большее из расстояний от тройки треф до края. Значит, когда-то расстояния до краёв совпадут и придётся выкинуть тройку треф.
Обсуждение
0Комментариев пока нет.