Задача 115395

Темы:    [ Теория игр (прочее) ] [ Перебор случаев ]

Сложность: 4+ Классы: 8,9,10,11

Условие

Игровое поле представляет собой полоску 1× N . В начале игры на нескольких крайних левых полях стоит по одной белой шашке, на стольких же крайних правых полях — по одной чёрной шашке. Белые и Чёрные ходят по очереди, начинают Белые. Ход заключается в передвижении одной из своих шашек в направлении противника (Белые ходят направо, Чёрные — налево). Можно делать простой ход или бить шашки соперника. При простом ходе разрешается перемещать шашку на любое число клеток, но нельзя перепрыгивать ни через свои шашки, ни через чужие. Бьют шашки соперника по тем же правилам, что и в обычных шашках:
Шашка бьёт шашку соперника, стоящую на соседнем поле, если следующее за ним поле свободно. При этом своя шашка перемещается на это свободное поле, а побитая шашка соперника снимается с доски.
Бить обязательно: если есть возможность бить, делать вместо этого простой ход какой-либо шашкой нельзя.
Если шашка, побившая шашку соперника, может сразу побить следующую его шашку, она должна продолжать бить тем же ходом.
Кто — Белые или Чёрные — победят в этой игре вне зависимости от игры партнёра? Рассмотрите случаи:
а) У игроков по одной шашке, поле длиной N>2 клеток;
б) У игроков по две шашки, поле длиной N>4 клеток;
в) У игроков по три шашки, поле длиной N>6 клеток;
г) Дополнительное задание. Можно подумать, что численное преимущество решает исход игры. Придумайте и нарисуйте, однако, позицию, где у Белых меньше шашек, чем у Чёрных, и тем не менее, Белые начинают (с простого хода) и выигрывают.

Решение

В этой игре Белые, бесспорно, имеют преимущество, хотя иногда они и проигрывают. Клетки поля мы для удобства иногда будем нумеровать слева направо: 1, 2, 3, .. (N-1), N .
В пункте "а" при N=3 Белые проиграют (этот тривиальный случай многие "прозевали"), а в остальных случаях — победят, передвинув шашку с клетки 1 на клетку (N-2) . Эта атака — поставить свою шашку за одну клетку до шашки противника — будет часто в дальнейшем применяться Белыми.
В пункте "б" Белые тоже, казалось бы, должны идти с клетки 2 на (N-3) . Однако, такой ход возможен только если N-3>2 , то есть N>5 . В этом случае у Чёрных только один ход, следует размен, и возникает положение (рис. 5). Теперь Белые ходят с 1 на (N-4) (это возможно, так как N-4>1 при N>5 ) и выигрывают.

Случай же N=5 разбирается отдельно. Все ходы там вынужденные, и побеждают тоже Белые.
В пункте "в" Белые тоже побеждают, атакуя стандартным образом, но это возможно только при N>8 . Вот как пойдёт игра: Белые: 3 (N-4) , размен и далее Белые повторяют атаку: 2 (N-5) . Оба эти хода возможны: при N>8 заведомо будет и  N-4>3 , и  N-5>2 . После второго хода Белых возникнет ситуация как на рис 2. Теперь двигать левую чёрную шашку Чёрным невыгодно, а второй шашкой они смогут сделать максимум 2 хода, тогда как Белые (N-7) ходов. Поскольку N-7 2 при N>8 , у Чёрных раньше кончатся ходы, и им придётся отдавать свою шашку на съедение, что быстро приведёт их к проигрышу.
Случаи N=7 и N=8 требуют отдельного разбора. При N=7 ход у Белых один, далее серия вынужденных разменов, и возникает позиция (рис. 7), где Белые легко побеждают.
При N=8 у Белых теоретически два возможных первых хода. Поддаться первым ходом ( 3 5 ) оказывается невыгодным: после серии вынужденных ходов имеем положение (рис. 8), где ход Чёрных, так что они легко выигрывают, пойдя 7 5 . Атаковать тоже не удаётся: после первого хода 3 4 и разменов получается позиция (рис. 9). Ходить 2 4 глупо, после же 2 3 следует 8 7 , Белые ходят 1 2 , Чёрные 7 6 , после чего Белые вынуждены пойти на клетку 4 и проиграть. Итак, при N=8 победят Чёрные.









Возможное (видимо, простейшее) решение дополнительного задания представлено на рисунке 10. Пусть у Чёрных две шашки, у белых — только одна. Ходя на клетку влево, Белые вынуждают Чёрных сдать обе свои шашки следующим ходом.

Источники и прецеденты использования

олимпиада
Название	Турнир им.Ломоносова
номер/год
Название	конкурс по математическим играм
Год	2009
задача
Номер	3