TOTALОбратимость ходов - нетривиальная часть задачи.
Я скоро набросаю доказательство.
-- Mon Jun 01, 2009 02:35:13 --Доказательство.
Позицией назовем вектор
![$p=(k,q_1,q_2,\dots,q_n)$ $p=(k,q_1,q_2,\dots,q_n)$](https://dxdy-01.korotkov.co.uk/f/4/c/c/4cc7f584759c3f223070ba39b50682e582.png)
, где
![$q_i$ $q_i$](https://dxdy-02.korotkov.co.uk/f/9/2/9/9294da67e8fbc8ee3f1ac635fc79c89382.png)
количество карт в
![$i$ $i$](https://dxdy-04.korotkov.co.uk/f/7/7/a/77a3b857d53fb44e33b53e4c8b68351a82.png)
-й кучке и
![$k$ $k$](https://dxdy-03.korotkov.co.uk/f/6/3/b/63bb9849783d01d91403bc9a5fea12a282.png)
- номер кучки из которой предстоит сделать ход, причем
![$q_1+q_2+\dots+q_n = m$ $q_1+q_2+\dots+q_n = m$](https://dxdy-04.korotkov.co.uk/f/f/4/4/f440c62df0d8d32fb11741e7ec00430b82.png)
,
![$1\leq k\leq n$ $1\leq k\leq n$](https://dxdy-03.korotkov.co.uk/f/6/1/7/617f2785d1a0fcf6962a316633edc39082.png)
и
![$q_j>0$ $q_j>0$](https://dxdy-01.korotkov.co.uk/f/c/a/2/ca27e5f8f83eff51cff9fa4cb5a354d382.png)
для всех
![$j\leq k$ $j\leq k$](https://dxdy-04.korotkov.co.uk/f/3/9/2/392847ce976de00edb493098ff565c4282.png)
.
Пусть
![$f(p)$ $f(p)$](https://dxdy-02.korotkov.co.uk/f/d/9/7/d977278e7805a6056c67cbd625a04ad282.png)
- это функция, которая позицию
![$p=(k,q_1,q_2,\dots,q_n)$ $p=(k,q_1,q_2,\dots,q_n)$](https://dxdy-01.korotkov.co.uk/f/4/c/c/4cc7f584759c3f223070ba39b50682e582.png)
переводит в новую позицию, раскидывая карты из кучки
![$k$ $k$](https://dxdy-03.korotkov.co.uk/f/6/3/b/63bb9849783d01d91403bc9a5fea12a282.png)
согласно правилам.
Докажем, что для каждой позиции
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
найдется по крайней мере одна позиция
![$p'$ $p'$](https://dxdy-01.korotkov.co.uk/f/4/a/e/4ae3393b40dfbbbc0932cf55cbc55bc382.png)
, для которой
![$f(p')=p$ $f(p')=p$](https://dxdy-01.korotkov.co.uk/f/0/0/9/009e7ecf675745e8c688e8240a9c9a8182.png)
. Рассмотрим в
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
кучки с минимальным количеством карт, а среди них самую левую - пусть ее номер равен
![$t$ $t$](https://dxdy-01.korotkov.co.uk/f/4/f/4/4f4f4e395762a3af4575de74c019ebb582.png)
(таким образом, для
![$j<t$ $j<t$](https://dxdy-01.korotkov.co.uk/f/c/8/4/c8431f2ccc103786bfdcea002129ca1082.png)
мы имеем
![$q_j\geq q_t+1$ $q_j\geq q_t+1$](https://dxdy-02.korotkov.co.uk/f/9/2/2/9220285c01589ee3be6ae411934ec4b482.png)
, а для
![$j\geq t$ $j\geq t$](https://dxdy-01.korotkov.co.uk/f/c/a/9/ca9bd3eab716a157f833a08477d8482482.png)
- соответственно
![$q_j\geq q_t$ $q_j\geq q_t$](https://dxdy-01.korotkov.co.uk/f/0/8/5/0859c7513b4d09557a5c32b67c36945c82.png)
).
Возможны следующие случаи:
1) Если
![$k\geq t$ $k\geq t$](https://dxdy-03.korotkov.co.uk/f/2/0/2/2029dbe341425d68865015a3db14320982.png)
, то положим
![$$p' = (t,q_1 - q_t, \dots, q_{t-1} - q_t, k q_t + (n-k) (q_t - 1), q_{t+1} - q_t, \dots, q_{k} - q_t, q_{k+1} - (q_t - 1), \dots, q_n - (q_t - 1));$$ $$p' = (t,q_1 - q_t, \dots, q_{t-1} - q_t, k q_t + (n-k) (q_t - 1), q_{t+1} - q_t, \dots, q_{k} - q_t, q_{k+1} - (q_t - 1), \dots, q_n - (q_t - 1));$$](https://dxdy-02.korotkov.co.uk/f/d/0/8/d085c07b2646a77d7d82999ea31d952882.png)
2) если
![$k<t$ $k<t$](https://dxdy-04.korotkov.co.uk/f/b/4/0/b40f53551bfcc592b2a86d6c019f67cd82.png)
и существует такое
![$j\leq k$ $j\leq k$](https://dxdy-04.korotkov.co.uk/f/3/9/2/392847ce976de00edb493098ff565c4282.png)
, что
![$q_j = q_t + 1$ $q_j = q_t + 1$](https://dxdy-02.korotkov.co.uk/f/d/a/0/da020e4eb7105f5af532ab7aa38e2f8482.png)
, то переопределим
![$t$ $t$](https://dxdy-01.korotkov.co.uk/f/4/f/4/4f4f4e395762a3af4575de74c019ebb582.png)
равным минимальному такому
![$j$ $j$](https://dxdy-04.korotkov.co.uk/f/3/6/b/36b5afebdba34564d884d347484ac0c782.png)
, попадая таким образом в случай 1) рассмотренный выше;
3) если
![$k<t$ $k<t$](https://dxdy-04.korotkov.co.uk/f/b/4/0/b40f53551bfcc592b2a86d6c019f67cd82.png)
и для всех
![$j\leq k$ $j\leq k$](https://dxdy-04.korotkov.co.uk/f/3/9/2/392847ce976de00edb493098ff565c4282.png)
выполняется
![$q_j > q_t + 1$ $q_j > q_t + 1$](https://dxdy-04.korotkov.co.uk/f/7/7/6/776a8da7c3a194e3c430e22d93720bfe82.png)
, то положим
![$$p' = (t,q_1 - (q_t + 1), \dots, q_k - (q_t + 1), q_{k+1} - q_t, \dots, q_{t-1} - q_t, k (q_t + 1) + (n-k) q_t, q_{t+1} - q_t, \dots, q_n - q_t)$$ $$p' = (t,q_1 - (q_t + 1), \dots, q_k - (q_t + 1), q_{k+1} - q_t, \dots, q_{t-1} - q_t, k (q_t + 1) + (n-k) q_t, q_{t+1} - q_t, \dots, q_n - q_t)$$](https://dxdy-02.korotkov.co.uk/f/9/0/b/90b46188a82b8b5550ef58b3f841fc8782.png)
Обозначим это построение через
![$p' = g(p)$ $p' = g(p)$](https://dxdy-03.korotkov.co.uk/f/6/1/0/6107b3649b8f1319fa312f42690202ad82.png)
. Для заданной позиции
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
вектор
![$g(p)$ $g(p)$](https://dxdy-03.korotkov.co.uk/f/6/0/3/6033cf6a339f12568617b4cc4266fcdc82.png)
также является позицией. Причем, как нетрудно проверить,
![$f(g(p))=p$ $f(g(p))=p$](https://dxdy-04.korotkov.co.uk/f/b/a/5/ba5d02236a75f5b8169eff07037de90682.png)
.
Пусть
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
- произвольная позиция. Рассматривая последовательные итерации
![$g(\cdot)$ $g(\cdot)$](https://dxdy-03.korotkov.co.uk/f/a/0/3/a0377869f11bf54f0a0e8ac338ecea7982.png)
на
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
, из конечности числа различных позиций, заключаем, что либо
![$g^{(q)}(p)=p$ $g^{(q)}(p)=p$](https://dxdy-04.korotkov.co.uk/f/7/9/4/79415f34dc3d985f82c393abbd89423b82.png)
для некоторого натурального
![$q$ $q$](https://dxdy-02.korotkov.co.uk/f/d/5/c/d5c18a8ca1894fd3a7d25f242cbe889082.png)
, либо существует такие неотрицательные целые числа
![$q_1$ $q_1$](https://dxdy-01.korotkov.co.uk/f/0/7/d/07d7104fe13d9faea3e641ad3d05383282.png)
и
![$q_2$ $q_2$](https://dxdy-01.korotkov.co.uk/f/c/a/9/ca98959b0f9ec7100371b3aea8ad2ba482.png)
, что
![$g^{(q_1)}(p)\ne g^{(q_2)}(p)$ $g^{(q_1)}(p)\ne g^{(q_2)}(p)$](https://dxdy-02.korotkov.co.uk/f/d/e/2/de242ffdda9a23fb03fe48255d207cd182.png)
и
![$g^{(q_1+1)}(p)= g^{(q_2+1)}(p)$ $g^{(q_1+1)}(p)= g^{(q_2+1)}(p)$](https://dxdy-03.korotkov.co.uk/f/2/b/3/2b3026a2ad45b0bef6e866b739cc6afb82.png)
. Второй вариант, однако, невозможен, так как в нем получается противоречие:
![$$g^{(q_1)}(p) = f(g^{(q_1+1)}(p)) = f(g^{(q_2+1)}(p)) = g^{(q_2)}(p).$$ $$g^{(q_1)}(p) = f(g^{(q_1+1)}(p)) = f(g^{(q_2+1)}(p)) = g^{(q_2)}(p).$$](https://dxdy-04.korotkov.co.uk/f/3/3/4/33448662c91a7cb3cfb20e1ffaee99e582.png)
Итак, получаем, что
![$g^{(q)}(p)=p$ $g^{(q)}(p)=p$](https://dxdy-04.korotkov.co.uk/f/7/9/4/79415f34dc3d985f82c393abbd89423b82.png)
для некоторого натурального
![$q$ $q$](https://dxdy-02.korotkov.co.uk/f/d/5/c/d5c18a8ca1894fd3a7d25f242cbe889082.png)
, а значит и
![$f^{(q)}(p) = p$ $f^{(q)}(p) = p$](https://dxdy-01.korotkov.co.uk/f/c/7/4/c74459ed7525445581f778e0e3e6da5f82.png)
, то есть начав с произвольной позиции
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
мы обязаны в нее же и вернуться при итерациях
![$f(\cdot)$ $f(\cdot)$](https://dxdy-01.korotkov.co.uk/f/8/8/2/8824595f458085fe3bf467c4228300fc82.png)
.
Другими словами, мы доказали, что
![$f$ $f$](https://dxdy-02.korotkov.co.uk/f/1/9/0/190083ef7a1625fbc75f243cffb9c96d82.png)
и
![$g$ $g$](https://dxdy-04.korotkov.co.uk/f/3/c/f/3cf4fbd05970446973fc3d9fa3fe3c4182.png)
являются взаимно-обратными перестановками на множестве позиций.