Четвёртая открытая интернет-олимпиада по математике

======= 137 ========

Оценка за решение задачи ММ137 учитывается дважды: в основном Марафоне
и в тематическом конкурсе.

ММ137 (МИ4) (6 баллов)

Шашки двух игроков стоят на противоположный полях прямоугольника 1x(N+2), между ними N клеток. Начальная скорость каждой шашки равна 1.
Каждый ходом игрок может или передвинуть свою шашку в сторону противника на величину, равную текущей скорости или увеличить скорость на 1 и передвинуть шашку в этом направлении уже на величину увеличенной скорости.
Выигрывает тот, кто поставит свою шашку на шашку противника или перепрыгнет через неё.
Для каких натуральных N, не превосходящих 100, выиграет второй игрок?

Решение

В данной игре позиция описывается тройкой чисел: текущее расстояние n, скорость фишки ходящего игрока v и его соперника w. Из позиции (n,v,w) можно попасть в (n-v,w,v) и в (n-v-1,w,v+1).

Таким образом, несложно организовать перебор даже в Excel'e и выяснить, что для значений v = w = 1 проигрышными будут позиции с n = 2, 6, 8, 11, 13, 17, 20, 24, 27, 29, 32, 36, 38, 41, 45, 47, 51, 53, 56, 58, 62, 64, 67, 70, 74, 76, 80, 83, 87, 89, 93, 96, 98 Обсуждение

Все участники, решившие задачу, использовали аналогичный метод. А я так надеялся, что вдруг, как в предыдущих тематических заданиях, кому-то удастся установить более простую закономерность в этой последовательности. Возможно, её стоит отправить в OEIS, как думаете?

Награды

За правильное решение задачи Анатолий Казмерчук, Алексей Волошин, Евгений Гужавин, Кирилл Веденский, Дмитрий Пашуткин, Александр Ларин и Сергей Половинкин получают 6 призовых баллов.

Эстетическая оценка задачи 4 балла

===============
Разбор задачи подготовил Алексей Извалов