|
|
 |
Условие
Есть доска 1×1000, вначале пустая, и куча из n фишек. Двое ходят по очереди. Первый своим ходом "выставляет" на доску не более 17 фишек по одной на любое свободное поле (он может взять все 17 из кучи, а может часть – из кучи, а часть – переставить на доске). Второй снимает с доски любую серию фишек (серия – это несколько фишек, стоящих подряд, то есть без свободных полей между ними) и кладёт их обратно в кучу. Первый выигрывает, если ему удастся выставить все фишки в ряд без пробелов.
а) Докажите, что при n = 98 первый всегда может выиграть.
б) При каком наибольшем n первый всегда может выиграть?
Решение
а) Приведём стратегию первого игрока. Он вначале за несколько ходов выстраивает 12 серий по 8 фишек, так что соседние серии разделены одним пробелом, последовательно восстанавливая снятую серию и ставя ещё одну. Затем, восстановив конфигурацию после хода второго, он вставляет две фишки в крайние пробелы, получая конфигурацию 17, 8, 8, 8, 8, 8, 8, 8, 8, 17.
При любом ходе второго следующим ходом он строит непрерывный ряд, а именно: если второй снимает крайнюю серию, первый вставляет восемь фишек в пробелы между сериями и пристраивает с краю остальные девять фишек; если же второй снимает среднюю серию (длины 8), то первый своим ходом восстанавливает эту серию (восемь фишек) и заполняет пробелы между сериями (ещё девять фишек).
б) Пусть имеются n ≥ 98 фишек, и первый всегда выигрывает. Рассмотрим конфигурацию после предпоследнего хода первого. В ней несколько серий, разделённых одним или несколькими пробелами, и p фишек в куче. В каждой серии не более 17 фишек, иначе второй снимет такую серию и следующим ходом не удастся выставить все фишки.
В ответ на снятие любой серии первый может только: (а) восстановить снятую серию, затем заполнить все пробелы фишками из кучи и крайней серии (или нескольких крайних) или (б) переставить все фишки с одной стороны от снятой серии в пробелы между сериями другой стороны, пристроив оставшиеся с краю. Назовём серию средней, если на её снятие отвечают способом (а), левой – если способом (б) и фишки переставляются направо; правой – если (б) и налево. Ясно, что если на снятие крайней серии можно ответить способом (а), то можно и способом (б); будем считать, что первый отвечает (б), поэтому левая и правая серии всегда есть. Кроме того, если некоторая серия правая, то все серии слева от неё допускают ответ (б) с перестановкой налево. Мы будем считать, что первый игрок отвечает именно таким образом. Поэтому правые серии – это несколько крайних справа серий. Аналогично для левых серий.
Заметим, что в левых сериях и в куче в сумме не более 17 фишек: все фишки левых серий и фишки кучи нужно выставить или переставить при снятии самой правой из левых серий (аналогично – для правых серий).
Пусть есть ещё k средних серий. Если в одной из них m фишек, то m + k + 1 ≤ 17, поскольку при снятии этой серии надо восстановить m фишек и ещё заполнить по крайней мере k + 1 пробел между сериями, отсюда m ≤ 16 – k.
Итак, n ≤ p + 2(17 – p) + k(16 – k).
Максимум этого выражения достигается при p = 0 и k = 8, что даёт n ≤ 98.
Ответ
б) При n = 98.
Замечания
Баллы: 4 + 5
