Всесиб 2023, отборочный этап, 9 класс, задача 4
( баллов) У Викентия есть две банки, красная и синяя, а также кучка из камешков. Изначально обе банки пусты. Ход в игре Викентия состоит в том, чтобы переложить камешек из кучки в одну из банок или вернуть камешек из одной из банок в кучку. Количество камешков в банках определяет позицию игры. После каждого хода число камешков в красной банке всегда не меньше числа камешков в синей банке; и в ходе игры ни одна позиция не может повториться. Какое максимальное количество ходов может сделать Викентий?
Ответ
Ответ. .
Решение. Позиция в игре Викентия однозначно задаётся парой неотрицательных целых чисел , и , где — числа камешков в синей и красной банках соответственно. Всего в игре Викентия возможна позиция. Назовём позицию чётной, если сумма её чисел камешков в банках чётна, и нечётной — в противоположном случае. Всего в игре чётных позиций и нечётных. Каждый ход в игре меняет чётность позиции, поэтому всего игра не может содержать более, чем чётных и нечётных позиций (с учётом того, что начинается она с чётной позиции ), всего позиций, и состоять из не более, чем ходов.
Приведём пример игры, когда Викентий сможет сделать ходов. При этом он делает единственно возможный первый ход с на , затем все позиции с нечётным проходит последовательно от до , после чего переходит к , а все позиции с чётным проходит последовательно от до , после чего переходит к . После всего указанного он оказывается в позиции , после чего его стратегия слегка меняется: все позиции с нечётным проходит последовательно от до , после чего переходит к , а все позиции с чётным проходит последовательно от до , после чего переходит к . В итоге он оказывается в позиции и совершает последний ход в . Не пройденными остались позиции — ровно штук, то есть пройденными в точности позиций. Совершено как раз ходов.