ОЛ ВЗМШ при МГУ: Отделение математики

Избранные задачи Вопрос-Ответ
Вход для наших учеников
Личный номер
Пароль

Избранные задачи

В первом ящике 68 шаров, а во втором - 97. Двое играющих поочередно берут шары, причем за один ход игрок может взять из любого (но только одного) ящика произвольное количество имеющихся в нем шаров. Выигрывает берущий последние шары. Кто выигрывает при правильной игре, начинающий или его парт-нер, и как надо для этого играть?

Решение. Если первый игрок начнет с того, что уравняет количество шаров в ящиках (т.е. вынет из второго ящика 29 шаров), он получит возможность выиграть: его стратегия будет заключаться в том, чтобы все время и в дальнейшем уравнивать число шаров в ящиках после каждого хода второго игрока (так называемая "симметричная стратегия"). Поступая таким образом, он, очевидно, выиграет: поскольку второй игрок всегда своим ходом нарушает симметрию, он не может забрать последние шары (ведь тем самым он создаст симметричную ситуацию - оба ящика пусты) а когда второй игрок заберет все из одного ящика, (что рано или поздно неизбежно - ведь количество шаров после каждого хода уменьшается, что не может продолжаться бесконечно) первый следующим своим ходом сделает то же самое с другим ящиком - заберет все - и лишит второго игрока возможности сделать очередной ход. Если же первый игрок хотя бы один раз отступит от этой стратегии, второй получит возможность выиграть, если "перехватит инициативу" и сам начнет делать ходы, "симметричные" ходам первого.

Ответ: при правильной игре выигрывает первый игрок.

Программная часть/дизайн:
Соловьев П.Н. SPECIALIST® Online Certified

PHP Specialist
Контент:
Серебренникова Л.Г.
Rambler's Top100 Союз образовательных сайтов Яндекс цитирования