|
|
 |
Условие
Двое играют в такую игру. Из кучки, где имеется 25 спичек, каждый берёт себе по очереди одну, две или три спички. Выигрывает тот, у кого в конце
игры – после того, как все спички будут разобраны, – окажется чётное число спичек.
а) Кто выигрывает при правильной игре – начинающий или его партнёр? Как он должен играть, чтобы выиграть?
б) Как изменится ответ, если считать, что выигрывает забравший нечётное число спичек?
в) Исследуйте эту игру в общем случае, когда спичек 2n + 1 и разрешено брать любое число спичек от 1
Решение
а) Вот выигрышная стратегия для второго игрока. Он должен:
1) всегда брать нечётное число спичек (одну или три);
2) оставлять начинающему число спичек, сравнимое с 0 или 1 по модулю 4.
Нетрудно проверить, что это возможно. При этом после шести ходов второго у него окажется чётное число спичек, а в кучке останется 0 или
1 спичка.
б) Вот выигрышная стратегия для первого игрока. Первым ходом он должен взять одну спичку, а дальше играть по стратегии, изложенной в а).
При этом он сделает ровно 7 ходов, и у него окажется нечётное число спичек.
в) 1) Исследуем сначала игры типа а) и б) в случае m = 3. Ясно, что алгоритм, приведённый в а), работает в игре типа а) при любом n, кратном 4,
а в игре типа б) при n ≡ 2 (mod 4).
При других n выигрывает первый. Например, в игре типа а) при 27 спичках он забирает две и "передает" ход второму, который, согласно а)
должен проиграть. При 29 спичках (31 спичке) он забирает одну (три) 3 спички и далее делает еще 7 ходов по тому же алгоритму.
Аналогично разбираются все случаи игры типа б).
2) Более того, аналогичные алгоритмы годятся при любом нечётном m. При этом первый проигрывает в игре типа а) при n, кратном m + 1,
в игре типа б) при n ≡ m+1/2 (mod m + 1), а в остальных случаях выигрывает.
3) При чётном m ситуация несколько другая: первый проигрывает в игре типа а) при n, кратном m/2 + 1, в игре типа б) при n ≡ m/2 (mod m/2 + 1),
а в остальных случаях он выигрывает. Поясним алгоритмы на примере m = 4.
4) Пусть n = 12 (25 спичек). Поскольку 12 кратно 3, в игре типа а) должен выиграть второй. Вот его стратегия.
Второй должен оставлять противнику число спичек, сравнимое с 0 или 1 по модулю 6, имея "на руках" чётное число спичек, и число, сравнимое
с 5 по модулю 6, имея на руках нечётное число спичек. Покажем, что это возможно.
Если первый забирает чётное число спичек, то второй просто дополняет это количество до 6.
Если первый забирает нечётное число спичек из кучки с 6k спичками, то второй дополняет это количество до 5. В кучке остаётся 6k – 5 спичек,
а у второго – снова чётное количество.
Если первый забирает нечётное число спичек из кучки с 6k + 1 спичкой, то второй дополняет это количество до 4. В кучке остаётся
6k + 3 спички,
а у второго становится нечётное количество спичек.
Если первый забирает нечётное число спичек из кучки с 6k + 5 спичками, то второй также дополняет это количество до 4. В кучке остаётся 6k + 1
спичка, а у второго становится чётное количество спичек. В результате в конце игры после последнего хода второго останется 0 или 1 спичка,
а у второго будет чётное число.
5) Пусть n = 14 (29 спичек). Поскольку 14 ≡ 2 (mod 3), в игре типа б) должен выиграть второй. Его стратегия аналогична: оставлять противнику
число спичек, сравнимое с 0 или 1 по модулю 6, имея "на руках" нечётное число спичек, и число сравнимое с 5 по модулю 6, имея на руках
чётное число спичек.
В остальных случаях выигрывает начинающий, придерживаясь аналогичных стратегий.
Ответ
а) Партнёр; б) начинающий.
в) В игре типа а) начинающий проигрывает только в случаях n ≡ 0 (mod m/2 + 1) при чётном m и n ≡ 0 (mod m + 1) при нечётном m;
в игре типа б) начинающий проигрывает только в случаях n ≡ m/2 (mod m/2 + 1) при чётном m и n ≡ m+1/2 (mod m + 1) при нечётном m.
Замечания
Другой подход к этой задаче см. в решениях Задачника "Кванта".
