Французский математик Клод Гаспар Баше в своей книге "Задачи приятные и развлекательные", вышедшей в 1612 г., описал игру с множеством предметов (камней, монет, спичек и т.д.). В этой игре партнеры из множества N предметов поочередно берут не менее одного и не более K предметов (K > 1, N ≥ K). Тот, кто берет последний предмет, проигрывает.
Исход игры определен после первого хода, если партнеры не делают ошибок.
Алгоритм простой за каждые два хода (твой и противника) ты всегда можешь гарантировать в сумме K+1 предмет, что и ведет к выигрышу
Победный алгоритм игры Баше легко получить, если рассуждать с «конца», то есть рассмотреть сначала позицию перед последним ходом. Для выигрыша надо оставить противнику перед его последним ходом K + 1 предмет. Тогда, сколько бы он ни взял (больше K брать нельзя), своим ходом вы забираете последний предмет. Поэтому перед предпоследним ходом надо оставить на столе 2(K + 1) предметов. В этом случае при любом ходе противника можно ответить так, что в куче останется K + 1 предмет.
Таким образом, в игре есть ряд ключевых позиций – K + 1, 2(К + 1), 3(К + 1) предметов и т.д., когда начинающий проигрывает. Значит, если начальная позиция неключевая, то нужно сразу же получить ключевую позицию, взяв «лишние» предметы, а затем уверенно доводить игру до победы.
Если же в особой позиции ваш ход, остается лишь уповать на то, что противник не читал литературы, где описана стратегия игры Баше, и ждать его ошибки.
В первоначальном варианте игры правила были следующими: первый игрок выбирает число от 1 до 10, второй прибавляет к нему любое число из того же интервала и т.д. Побеждает тот, кто получит в сумме 100. В ней также есть выигрышные позиции. Их указал сам Баше: 9, 19, 29, 89.
Пример:
На столе лежат 37 спичек. Каждому из двух игроков разрешается по очереди брать не более 5 спичек. Выигрывает тот, кто возьмет последнюю. Кто выигрывает при правильной стратегии - начинающий игру или второй игрок? Какова выигрышная стратегия?
Ответ:
Начинающий первым ходом берет одну спичку, а затем каждый раз дополняет число спичек, взятых соперником, до шести.
