Задача 664
Бесконечная игра

Петр играет в одиночную игру на бесконечной шахматной доске, каждая клетка которой может содержать бесконечное количество фишек.

Каждый ход в игре состоит из следующих шагов:

  1. Выберите фишку $T$ для перемещения. Это может быть любая фишка на доске, кроме тех, чьи все четыре прилегающие клетки пусты.
  2. Выберите и сбросьте одну фишку $D$ с клетки, прилегающего к $T$.
  3. Переместите $T$ на любую из прилегающих к ней клеток (даже если она уже занята).
Разрешенные ходы

Доска изначально помечена линией, называющейся разделительной линией. Изначально каждая клетка слева от разделительной линии содержит одну фишку, а каждая клетка справа от разделительной линии пуста:

Начальное состояние

Цель Петра - переместить фишку как можно дальше вправо за конечное число ходов. Однако, он быстро осознает, что даже с бесконечным запасом фишек он не может переместить фишку дальше, чем на четыре клетки вправо от разделительной линии.

Тогда Петр рассматривает начальные расположения с бóльшими запасами фишек: каждая клетка в $d$-том столбце слева от разделительной линии начинает с $d^n$ фишками вместо 1. Ниже это проиллюстрировано для $n=1$:

Начальное состояние n=1

Пусть $F(n)$ будет максимальным количеством клеток, на которое Петр может переместить фишку за разделительную лнию. Например, $F(0)=4$. Также известно, что $F(1)=6$, $F(2)=9$, $F(3)=13$, $F(11)=58$ и $F(123)=1173$.

Найдите $F(1234567)$.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net