Дистанционная олимпиада 26.10-02,11.2013
25.10.2013
31. Возле пальмы находятся 13 кокосов. Играют двое: каждый по очереди берет 1, 2 или 3 кокоса. Проигрывает тот, кто берет последний кокос. Как играть, чтобы выиграть?
Решение.
Так как 3 + 1 = 4, то ключевые позиции: 4, 8, 12. Сколько бы кокосов (1, 2 или 3) ни брал первый игрок, второй в сумме с первым за один ход будет брать 4 кокоса, и это приведет его к победе. Действительно, имеем:
1)ход 1-го игрока 1(берет 1 кокос), ответ 2-го 3(кокоса), сумма 4 кокоса;
или ход 1-го игрока 2, ответ 2-го 2, сумма 4;
или ход 1-го игрока 3, ответ 2-го 1, сумма 4.
2) ход 1-го игрока 4 +1(берет 1 кокос), ответ 2-го 3(кокоса), сумма 8 кокосов;
или ход 1-го игрока 4+2, ответ 2-го 2, сумма 8;
или ход 1-го игрока 4+3, ответ 2-го 1, сумма 8.
3) ход 1-го игрока 8 +1(берет 1 кокос), ответ 2-го 3(кокоса), сумма 12 кокосов;
или ход 1-го игрока 8+2, ответ 2-го 2, сумма 12;
или ход 1-го игрока 8+3, ответ 2-го 1, сумма 12.
После этого первому игроку не остается ничего другого, как взять последний кокос, т. е. он проигрывает. Следовательно, выигрывает второй игрок.
Ответ: в оптимальном варианте выигрывает второй игрок, если в сумме с первым игроком за один ход будет брать 4 кокоса.
32. На столе лежат 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 |