«Марковская игра»

Question

Игры, подобные описанной ниже, я называю марковскими. Я выбираю именно эту или, скорее, серию игр с одним параметром. Открытая задача - выяснить, кто из игроков$\ 0\ $ или же $\ 1\ $ имеет выигрышную стратегию по каждому из заданных параметров $\ W.$

ОБОЗНАЧЕНИЕ $\ n\%2=0\ $ за $\ n\ $ даже, и $\ n\%2=1\ $ за $\ n\ $ странный.;

Позволять $ d(0)=J(0)=0.\ $ Для произвольного положительного целого числа $\ n,\ $ игрок $\ n\%2\ $ выбирает положительное целое число $\ d(n)\le d(n-1)+1;\ $ тогда $\ J(n)=J(n-1)+d(n).$

Когда игроки соревнуются в игре $\ M(W),\ $ где $\ W\ $ является произвольно фиксированным положительным целым числом, то игрок, получивший ровно $J(n)=W\ $ побеждает.

Позволять $\ \omega(W)=0\ $ если игрок $0$ имеет выигрышную стратегию в $M(W);\ $ в противном случае пусть $\ \omega(W)=1\ $ если игрок $1$ имеет выигрышную стратегию в $M(W)$.

ПРОБЛЕМА:   функция вычисления$\ \omega:\mathbb N\to\{0\ 1\}.$

Например: $\ \omega(1)=1;\ \omega(2)=\omega(3)=0;\ \omega(4)=1, $ и т. д. Однако $\ \omega(120)\ $ или же $\ \omega(5553)\ $ немного сложнее (и мне неизвестно).

Answer 1

Ответ не сильно меняется с увеличением числа.

Полный ответ $$ \omega(W)=\left\{ \begin{array}{ll} 1, & W\%5=1,4\\ 0, & W\%5=0,2,3 \end{array}\right. $$

Скажем, эта позиция $(W-J,d)$ выигрывает, если игрок $n\%2$ имеет выигрышную стратегию для игры $M(W)$ в свою очередь $n$ с участием $d(n)=d,J(n)=J$. В противном случае он проигрывает. Ясно, что это действительно зависит только от разницы$W-J$.

$(i,d)$ выигрывает, если есть проигрыш $(j,f)$ ул $j+f=i,f\le d+1$. Нас интересует,$(W-1,1)$ побеждает.

Для этого достаточно рассмотреть только $(i,d)$ с участием $d\le 3$.

Паттерн выглядит так:

$ \begin{array}{ccc} - & - & -\\ + & + & +\\ + & + & +\\ - & + & +\\ + & + & +\\ - & - & -\\ \vdots & \vdots & \vdots \end{array} $

Чтобы увидеть это, обратите внимание:

• $(0,d)$ проигрывает для всех $d$, т.е. первая строка заполнена $-$с
• если $(i,d)$ выигрывает, тогда $(i,d+1)$ выигрывает, т.е. справа от $+$ всегда другой $+$

Answer 2

У нас уже есть полный ответ от @JosephGordon, который доказал периодичность $\ \omega,\ $ длина периода равна 5. Джозеф - большое спасибо!

Позвольте мне написать решение, которому, по крайней мере, мне будет легче следовать.

Помните этого игрока $\ \omega(n)\ $ тот, у кого есть выигрышная стратегия для марковской игры $\ M(n).$

Теорема Для любого натурального числа$\ n\ $ выполняются следующие два свойства:

• Игрок $\ \omega(n)\ $ может выиграть каждую игру $\ M(n)\ $ выбрав все свои ходы так, чтобы $\ d(k)\le 3;$

• $\ \omega(n+5) = \omega(5).\ $

Доказательство   игрока$\ \omega(n)\ $, во время игры $\ M(n+5)\ $, может прибыть на позицию $\ n\ $ при использовании таких ходов, что $\ d(k)\le 3\ $каждый раз. Особенно,$\ d(t)\le 3\ $ когда $\ J(t)=n.\ $ Таким образом, теперь у нас есть всего четыре расширения игры:

• $\ d(t+1)=4.\ $ Тогда игрок $\ \omega(n)\ $ пьесы $\ d(t+2)=1\ $ и побеждает (поскольку $\ J(t+2)=n+5\ \text{and}\ t+2\equiv t\mod 2)$;

• $\ d(t+1)=3.\ $ Тогда игрок $\ \omega(n)\ $ пьесы $\ d(t+2)=2\ $ и побеждает;

• $\ d(t+1)=2.\ $ Тогда игрок $\ \omega(n)\ $ пьесы $\ d(t+2)=3\ $ и побеждает;

• $\ d(t+1)=1.\ $ Тогда игрок $\ \omega(n)\ $ пьесы $\ d(t+2)=1;\ $ тогда другой игрок играет $\ d(t+3)= 1$ или же $2\ $, и игрок $\ \omega(n)\ $ пьесы $\ 2$ или же $1\ $ соответственно и выигрывает.

Остальные формальные аргументы совершенно рутинны и очевидны. Конец ДОКАЗАТЕЛЬСТВА.

Полное числовое описание $\ \omega\ $ дается теоремой выше, а начальная $5$ ценности:

$$ \omega(1)=1;\,\ \omega(2)=\omega(3)=0;\,\ \omega(4)=1, \,\ \omega(5)=0 $$

Например, $\ \omega(5)=0\ $ поскольку J (1) = 1, то player $0$ может сыграть d (2) = 1, т.е. J (2) = 2, то - после хода игрока $0$ - игрок $\ 0\ $ будет играть $\ J(4)=5.$