Вариации на тему игры Баше

Задача

На столе лежат 25 спичек. Два игрока по очереди могут брать 1, 2, 3 или 4 спички. Выигрывает тот, кто забирает последнюю спичку. Кто выиграет при правильной игре?
Решить ту же задачу, если игроки могут брать 1, 3 или 6 спичек.

Решение

Первый вариант игры представляет собой игру Баше с максимальным ходом, равным 4. Будем анализировать игру «с конца». Если остаётся 1, 2, 3 или 4 спички, то тот игрок, чья очередь хода, забирает их и выигрывает. Если остаётся 5 спичек, то, сколько спичек ни возьми, второй игрок забирает остальные и выигрывает. Следовательно, нужно постараться оставить сопернику 5 спичек после своего хода. Это можно сделать, имея от 6 до 9 спичек на столе во время своего хода.

Далее находим, что если на столе остаётся 10 спичек, то игрок, делающий ход проиграет, поскольку, сколько бы он ни взял, противник своим ходом сможет оставить ему 5 спичек. Далее, аналогично определяем, что проигрышными для игрока, делающего ход, являются количества спичек, равные 15, 20 и 25.

Поскольку вначале спичек 25, то решение таково: выиграет второй игрок, если будет всегда своим ходом оставлять первому число спичек, кратное 5-ти.

И в общем случае: если в игре Баше игроки могут делать ходы от 1 до k, то для победы требуется оставлять сопернику кратное (k+1) число спичек. И, если начальное количество также кратно (k+1), то выигрывает второй игрок, а если нет – то первый.

Вторая игра в задаче намного интереснее. На её примере можно научиться находить выигрышную стратегию для практически любой математической игры.

Всего в игре может образоваться 26 позиций: от 25 до 0 спичек на столе. Построим таблицу из 26 столбцов (это удобно делать на листках в клеточку)

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

Понятно, что если до игрока дошёл ход, а на столе 0 спичек, то он проиграл. Отметим этот факт, поставив букву П в нулевой ячейке:

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
П

Теперь найдём, как одним ходом попасть в нулевую ячейку? Это можно сделать из ячеек №1, №3 и №6 (т.е., когда на столе 1, 3 или 6 спичек). Следовательно, эти позиции выигрышны для игрока, делающего ход. Поставим в соответствующих ячейках букву В:

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
П	В		В			В

Теперь поищем ячейки, из которых любой ход приводит в ячейку с буквой В. Иными словами, найдём позиции, из которых любой ход создаёт условия для выигрыша соперника.
Сейчас мы можем однозначно сказать, что такими ячейками являются: №2 и №4. Ставим в них букву П

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
П	В	П	В	П		В

Одним ходом в ячейку №2 или в №4 можно попасть из ячеек №№3, 5, 7, 8, 10. Это выигрышные позиции - ставим там буквы В.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
П	В	П	В	П	В	В	В	В		В

Далее последовательно находим проигрышные позиции (те, из которых все ходы ведут в выигрышные позиции) и выигрышные позиции (те, из которых одним ходом можно попасть в проигрышную) и таблица будет заполняться следующим образом:

Проигрышные: №№9, 11

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
П	В	П	В	П	В	В	В	В	П	В	П

Выигрышные: №№12, 14, 15, 17

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
П	В	П	В	П	В	В	В	В	П	В	П	В		В	В		В

Проигрышные: №№13, 18

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
П	В	П	В	П	В	В	В	В	П	В	П	В	П	В	В		В	П

Выигрышные: №№16, 19, 21, 24

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
П	В	П	В	П	В	В	В	В	П	В	П	В	П	В	В	В	В	П	В		В			В

Проигрышные: №№20, 22

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
П	В	П	В	П	В	В	В	В	П	В	П	В	П	В	В	В	В	П	В	П	В	П		В

Выигрышные: №№23, 25

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
П	В	П	В	П	В	В	В	В	П	В	П	В	П	В	В	В	В	П	В	П	В	П	В	В	В

Итак, позиция, когда на столе лежат 25 спичек – выигрышная. Для победы первому игроку нужно взять 3 спички и далее оставлять сопернику числа, дающие при делении на 9 остаток 0, 2 или 4.