|
|
 |
Условие
Двое играют в следующую игру: имеется две кучи конфет. Играющие делают ход по очереди. Ход состоит в том, что играющий съедает одну из куч, а другую делит на две (равные или неравные) части. Если он не может разделить кучу, так как там всего одна конфета, то он её съедает и выигрывает. Вначале в кучах было 33 и 35 конфет. Кто выиграет, начинающий или его партнер, и как для этого надо играть?
Решение
Докажем, что второй выигрывает тогда и только тогда, когда количество конфет в обеих кучах имеет вид 5k ± 2. Достаточно доказать следующую лемму.
Лемма. Если количество конфет хотя бы в одной из куч не имеет вид 5k ± 2, то можно выиграть за один ход, или сделать ход так, чтобы количество конфет в обеих кучах имело вид 5k ± 2.
Если количество конфет в обеих кучах имеет вид 5k ± 2, то невозможно за один ход выиграть и невозможно сделать ход так, чтобы
количество конфет в обеих кучах имело вид 5k ± 2.
Доказательство. Можно считать, что количество конфет в первой куче не имеет вид 5k ± 2. Тогда надо съесть вторую кучу. Если в первой куче только одна конфета, то этот ход выигрывает. Если же в первой куче более одной конфеты, то эту кучу можно так разделить на две, что в каждой из них количество конфет будет иметь вид
5k ± 2. Действительно, если в первой куче 5k конфет, то её можно разделить на кучи из 2 и 5k – 2 конфет; если в первой куче 5k + 1 конфета, то её можно
разделить на две кучи размера 3 и 5k – 2; если же в первой куче 5k + 4 конфеты, то её можно разделить на две кучи размера 2 и 5k + 2.
Заметим, что ни одна куча не состоит ровно из одной конфеты, а значит, выиграть за один ход невозможно. Сумма двух чисел вида 5k ± 2 имеет вид 5k или вид
5k ± 1. Следовательно, кучу из 5k ± 2 конфеты невозможно разделить на две кучи, в каждой из которых 5k ± 2 конфеты.
Итак, выигрышная стратегия для первого игрока состоит в том, чтобы каждым ходом переходить к ситуации, когда количество в каждой из куч имеет вид 5k ± 2.
Ответ
Начинающий.
