Инвариант

[lexus c.]

Помогите, пожалуйста, найти в этой задаче инвариант. Т.е. решить её именно методом инвариантов:

На горе 1001 ступенька, на некоторых лежат камни, по одному на ступеньке. Сизиф берёт любой камень и переносит его на ближайшую сверху свободную ступеньку (то-есть, если следующая ступенька свободна то на неё, а если занята, то на несколько ступенек вверх до первой свободной). После этого Аид скатывает на одну ступеньку вниз один из камней, у которых предыдущая ступенька свободна. Камней 500, и первоначально они лежали на нижних 500 ступеньках. Сизиф и Аид действуют по очереди, начинает Сизиф. Его цель - положить камень на верхнюю ступеньку.
Может ли Аид ему помешать?

[TOTAL]

lexus c. писал(а):

Может ли Аид ему помешать?

Сможет, если захочет.
Инвариант: первая ступенька занята, между камнями не более одной свободной ступеньки подряд.

[lexus c.]

TOTAL писал(а):

lexus c. писал(а):

Может ли Аид ему помешать?

Сможет, если захочет.
Инвариант: первая ступенька занята, между камнями не более одной свободной ступеньки подряд.

Оригинальный инвариант. Спасибо )

[ddn]

lexus c. писал(а):

TOTAL писал(а):

lexus c. писал(а):

Может ли Аид ему помешать?

Сможет, если захочет.
Инвариант: первая ступенька занята, между камнями не более одной свободной ступеньки подряд.

Оригинальный инвариант. Спасибо )

Я так понял. Инвариант будет соблюдаться только при определенной стратегии Аида: при поднятии Сизифом наивысшего камня в группе подряд идущих ступеней с камнями (камень поднимается на одну ступень вверх) – скатить на эту ступень тот же камень, а поднятии Сизифом камня не наивысшего в группе подряд идущих - скатить на эту ступень камень со следующей за ней ступени из группы подряд идущих. То есть нужно всегда занимать освободившуюся ступень, если она критическая (об этом ниже).

Проанализировав стратегию, можно ввести такой полуинвариант (не увеличивающаяся - пока Аид не споховал, и не уменьшающаяся – пока Сизиф не сплоховал, величина) равный, это будет доказано ниже, номеру наивысшей ступени, на которую Сизиф может поднять камень в первой части некоторого хода (до ответа Аида):
$inv=inv(N,\chi)=\max\limits_{i=1..N}\phi(i)$
- это максимум по всем ступеням от функции, равной на данной ступени - число ступеней ниже данной (номер данной вычесть один) плюс удвоенное число камней, расположенных на данной ступени и выше:
$\phi(i)=\left\{ \begin{array}{l} i-1+2\sum\limits_{j=i}^N\chi(j), \sum\limits_{j=i}^N\chi(j)>0\\ -\infty, \sum\limits_{j=i}^N\chi(j)=0\end{array} \right.$
где $N$ - число ступеней, $\chi$ - характеристическая функция занятости(=1)-незанятости(=0) ступени на множестве $\{1..N\}$, и $K=\sum\limits_{i=1}^N\chi(i)$ - общее число камней.

Замечу, что требования: первая ступень занята, между камнями не более одной свободной ступени подряд - справедливы лишь при соотношении $2\cdot K+1=N$.

Критические ступени те, для которых имеет место $\phi(i)=inv$, всегда существует хотя бы одна такая ступень.
Если $\chi(i)=0$, то $\phi(i+1)=1+\phi(i)$ и значит $\phi(i)<inv$ - значит критические ступени заняты камнями.

Пусть $i_*=\max\limits_{i=1..N,\chi(i)=1}(i)$ - наивысшая ступень, занятая камнем.
$i_c=\max\limits_{i=1..N,$\phi(i)=inv}(i)$ - наивысшая критическая ступень. Очевидно $i_c\leqslant i_*$
$\tilde i_c=\max\limits_{i=1..N,\phi(i)=inv,\chi(i+1)=1}(i)$ - наивысшая ступень, среди критических ступеней, у которых непосредственно следующая за ними ступень, занята камнем. Очевидно $\tilde i_c\leqslant i_c$ и $\tilde i_c<i_*$.

Когда ступень $i$ занята камнем, то $\phi(i+1)=\phi(i)+1-2\cdot 1=\phi(i)-1$ - значение $\phi$ следующей ступени уменьшается на единицу, когда ступень не занята камнем, то $\phi(i+1)=\phi(i)+1-2\cdot 0=\phi(i)+1$ - значение $\phi$ следующей ступени увеличивается на единицу (если в обоих случаях выше ступени $i$ есть камни!).
Отсюда следует другая формула $\phi(i)=i-1+2\sum\limits_{j=i}^N\chi(j)=2\cdot K+\sum\limits_{j=1}^{i-1}(1-chi(j))-\sum\limits_{j=1}^{i-1}chi(j)$ - удвоенное общее число камней плюс число свободных ступеней ниже данной и вычесть число камней ниже данной ступени (если $\sum\limits_{j=i}^N\chi(j)>0$).

Если Сизифом поднят камень с $i$-ой ступени на $j$-ю ($j>i$), то значит было $\chi(k)=1$ при $k=i..(j-1)$ и $\chi(j)=0$. Откуда $\phi(k)=\phi(i)-(k-i)$ для $k=i..j$, то есть $\phi(k)\leqslant inv-(k-i)$. При таком действии $\phi(k)$ для $k=1..i$ и $k=(j+1)..N$ не меняется, а для $k=(i+1)..j$ увеличивается на 2 (но если выше ступени $j-1$ совсем не было камней, $\phi(j)$ увеличивается неограниченно, от $-\infty$ до $j+1$!)
Если Аид скатил камень с $k$-ой ступени на $k-1$-ю, то значит перед этим было $\chi(k)=1$ и $\chi(k-1)=0$. Такое действие уменьшает $\phi$ на 2 для $k$-ой ступени и оставляет неизменным для остальных ступеней (но если выше $k$-ой ступени совсем не было камней, $\phi(k)$ уменьшается неограниченно, от $k+1$ до $-\infty$!).


Докажем, что стратегия Аида не позволяет повышать инвариант по окончании его хода.
Скатывая камень с $i+1$-ой ступени на $i$-ю, Аид уменьшает $\phi(i+1)'=\phi(i+1)+2$ до прежнего значения $\phi(i+1)$ и в конце хода остаются увеличенными (на 2) значения $\phi(k)$ лишь для $k=(i+2)..j$, но $\phi(k)'=\phi(k)+2\leqslant inv-(k-i)+2=inv+(i+2)-k\leqslant inv$ - они не увеличивают инвариант.
Если Сизиф поднимает камень с критической ступени, то Аиду просто необходимо скатить камень со следующей за ней ступени – в противном случае это бы уменьшило $\phi$ у другой ступени, а новое значение $\phi(i+1)'=\phi(i+1)+2=\phi(i)+1=inv+1$ тогда увеличило бы инвариант $inv'=\phi(i+1)'=inv+1$.
Если $i$-ая ступень критическая, а на $i+1$-ой ступени не лежал камень (то есть $j=i+1$), то конфигурация возвращается в прежнее положение после хода Сизифа и Аида.
Если $i$-ая ступень критическая и на $i+1$-ой ступени лежал камень (то есть $j\geqslant i+2$), то значение $\phi(k)$ увеличивается (на 2) для $j-i-1\geqslant 1$-го числа ступеней, то есть $\phi(k)'=\phi(k)+2=inv-(k-i)+2=inv+(i+2)-k$ для $k=(i+2)..j$ - тогда и $i+2$-ая ступень становится критической. При этом сумма $\sum\limits_{i=1}^N\phi(i)$ строго возрастает на $2(j-i-1)\geqslant 2$. (если выше ступени $j-1$ совсем не было камней, $\phi(j)$ увеличивается неограниченно, от $-\infty$ до $j+1$!)

Из того, что инвариант не возрастает, следует, что сумма $\sum\limits_{i=1}^{i_*}\phi(i)$ всегда ограничена, например $\leqslant N\cdot inv$.

Если же Сизиф поднимает камень не с критической ступени $\phi(i)<inv$, то Аид может скатить камень не на нее, а на другую ступень, ибо тогда $\phi(i+1)'=\phi(i)+1\leqslant inv$ и $\phi(k)'=\phi(k)+2\leqslant inv-(k-i)+2=inv+(i+2)-k<inv$ для $k=(i+2)..j$ - здесь может образоваться новая критическая ступень $i+1$ если $\phi(i)=inv-1$, но повышения инварианта нет. В этом случае, если Аид скатил камень с некоторой критической ступени, уменьшая ее значение $\phi$ на 2, то он тем самым или убивает ее критичность (если она не единственная критическая), или уменьшает инвариант (если она единственная критическая). Поэтому Сизифу, чтобы не допустить уменьшения инварианта, необходимо и достаточно всегда, когда критическая ступень единственна, порождать новую критическую ступень, то есть или поднимать камень с критической ступени $\phi(i)=inv$ или с почти критической $\phi(i)=inv-1$.
Значит, у Сизифа есть стратегия, не позволяющая Аиду уменьшать инвариант.


Теперь покажем, что данный инвариант действительно равен номеру наивысшей ступеньки, на которую Сизиф может поднять камень, пока Аид не сделал ответный ход.
Сизиф не может поднять камень на ступень с номером выше инварианта при указанном противодействии Аида. Действительно, пусть для наивысшей ступени $i_*$, занятой камнем, имеем $\phi(i_*)=i_*-1+2\cdot 1=i_*+1\leqslant inv$, а поскольку в начале следующего хода Сизиф может занять камнем ступени с номером, не превышающим $i_*+1$, то номер ступени занятой камнем никогда не превышает $inv$.

Сизиф может, не уменьшая инварианта, сделать критической, наивысшую из ступеней, занятых камнем $\phi(i_*)=inv$ (откуда $i_*=i_c$).
Для этого Сизифу, не допуская уменьшения инварианта, достаточно время от времени поднимать камень с некоторой критической ступени, у которой непосредственно следующая ступень также занята камнем - если такая ступень найдется. При этом сумма $\sum\limits_{i=1}^{i_*}{\phi(i)$ возрастает не меньше, чем на 2 (Если Аид не скатывает камень с наивысшей занятой ступени $i_*$). Если такая ступень найдется, это будет порождать критическую ступень с более высоким номером $i\to i+2$ и число вышележащих камней $\sum\limits_{j=i+2}^N\chi(j)$ у нее будет меньше на 1,
Так как эта сумма ограничена, то с некоторого хода ее невозможно будет увеличить таким способом (если номер наивысшей занятой ступени не уменьшился) - это означает, что у всех критических ступеней, непосредственно следующие за ними ступени свободны. Если следующая за критической ступенью $i$ ступень $i+1$ не занята, то последующая $i+2$-ая ступень также будет критической: $\phi(i+2)=\phi(i)+2-2\cdot 1=\phi(i)=inv$ и, значит, занятой. Значит, если нет совсем критических ступеней, у которых непосредственно следующая за ними ступень занята камнем, то все ступени, занятые камнем и расположенные выше некоторой критической - сами критические. И наивысшая из занятых ступеней, тоже является критической $\phi(i_*)=inv$.
Это можно получить несколько по другому.
Поскольку если следующая за критической ступенью $i$ ступень $i+1$ не занята, то либо $i+2$-ая ступень также будет критической, либо выше ступени $i$ совсем нет камней – из это следует, что у наивысшей критической ступени $i_c$ либо занята непосредственно следующая за ней ступень, либо она наивысшая занятая ступень (то есть либо $i_c\leqslant\tilde i_c$ либо $i_c=i_*$). Значит, пока наивысшая из ступеней, занятых камнем $i_*$, не критическая, поднятие камня с наивысшей критической ступени $i_c$ порождает критическую ступень со все более высоким номером $i\to i+2$. Поскольку номер занятой камнем ступени ограничен $inv$, и в одинаковой степени поскольку число вышележащих камней $\sum\limits_{j=i_*}^N\chi(j)$ у наивысшей критической ступени неуклонно убывает 1, то процесс завершится за конечное число шагов, когда наивысшая из ступеней, занятая камнем $i_*$, тоже окажется критической.

Пусть $i_*=\max\limits_{i=1..N,\chi(i)=1}(i)$ - наивысшая ступень, занятая камнем, тогда $\phi(i_*)=i_*-1+2\cdot 1=i_*+1$. Если она является критической $\phi(i_*)= inv$, то $inv=i_*+1$, но $i_*$-ая ступень занята камнем, значит, в начале следующего хода Сизиф может занять камнем $i_*+1$-ую ступень, пока Аид не сделал ответный ход.
Значит, Сизиф может, исходя из произвольной начальной конфигурации, за конечное число шагов поднять камень на ступень с номером, равным ее инварианту.

Сизиф не может поднять камень на ступень с номером выше инварианта при указанном противодействии Аида. Действительно, пусть $i_*=\max\limits_{i=1..N,\chi(i)=1}(i)$ - номер наивысшей ступени, занятой камнем, тогда $\phi(i_*)=i_*-1+2\cdot 1=i_*+1\leqslant inv$, а поскольку в начале следующего хода Сизиф может занять камнем ступени с номером, не превышающим $i_*+1$, то номер ступени занятой камнем никогда не превышает $inv$.


Для нашего случая, у начальной конфигурации было $inv=\max\limits_{i=1..K}\phi(i)=\max\limits_{i=1..K}(i-1+2(K-i+1))=$
$=\max\limits_{i=1..K}(2\cdot K+1-i))=2\cdot K=2\cdot 500=1000$, в то время как число ступеней $N=1001>1000=inv$. Аид, действуя по указанной стратегии, помешает Сизифу.

[TOTAL]

ddn писал(а):

Докажем, что стратегия Аида не позволяет повышать инвариант.

Во-первых, вся стратегия Аида (при любом начальном расположении камней) состоит в том,
чтобы положить камень на ступеньку, с которой Сизив только что снял камень.

Во-вторых, разве не очевидно, что после выкладывания верхних камней
(опирающихся на камень с наибольшим

$$I+2K+1$$

) с разрядкой в одну пустую ступень
Сизив сможет двигать камень только на 1 ступень, как и Аид?
Это и означает, что лучшего результата Сизив не добьется.

[ddn]

TOTAL писал(а):

ddn писал(а):

Докажем, что стратегия Аида не позволяет повышать инвариант.

Во-первых, вся стратегия Аида (при любом начальном расположении камней) состоит в том,
чтобы положить камень на ступеньку, с которой Сизив только что снял камень.

Во-вторых, разве не очевидно

Для меня ничего не очевидно, пока я не доказал все самым строгим образом.