Пока завершается тестирование конвейера, два сотрудника, Дэк и Вилл, решили привести в порядок
новогодние шары, делают они это в форме игры. Перед сотрудниками стоят две коробки шариков. Игроки
ходят друг за другом. Первый ход совершает Дэк. За один ход игрок может убрать из одной из коробок
один шар или уменьшить количество шаров в коробке вдвое (если количество шаров в коробке нечётно,
остаётся на один шар больше, чем убирается). Например, пусть в одной коробке 6, а в другой 7 шаров;
такую позицию мы будем обозначать (6, 7). За один ход из позиции (6, 7) можно получить любую из четырёх
позиций: (5, 7), (3, 7), (6, 6), (6, 4). Игра завершается в тот момент, когда суммарное количество шариков в
коробках становится не более 20. Победителем считается игрок, сделавший последний ход, то есть первым
получивший позицию, в которой в коробке будет 20 или меньше шаров. В начальный момент в первой
коробке было 10 шаров, во второй коробке — S шаров, S> 10. Найдите пять таких значений Ѕ, при которых у
Дэка есть выигрышная стратегия, причём одновременно выполняются два условия: Дэк не может
выиграть за один ход; - Дэк может выиграть своим вторым ходом независимо от того, как будет ходить
Вилл.
Будем говорить, что игрок имеет выигрышную стратегию, если может выиграть при любых ходах
противника. Описать стратегию игрока значит, описать, какой ход он должен сделать в любой ситуации,
которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует
включать ходы играющего по ней игрока, которые не являются для него безусловно выигрышными, т.е не
гарантирующие выигрыш независимо от игры противника.
Берем сначала 8 колец, делим на 3 кучи: 2 кучи по 3 кольца и в 1 куче 2 кольца. Взвесим 2 кучи по 3 кольца, если какая-то из них окажется легче, то фальшивое кольцо находится в этой куче. В этом случае достаточно взять 2 кольца из этой легкой кучи и взвесить. Если какое-то кольцо оказалось легче, оно и есть фальшивое. Иначе - фальшивое кольцо - то, которое осталось невзвешенным из этой кучи. Если же оказалось, что кучки по 3 кольца имеют одинаковый вес, то фальшивым является кольцо из третьей кучи, в которой 2 кольца. Тут тоже достаточно сделать второй взвес :)