Как доказать, что карты соберутся в первой кучке?

[zbl]

Вот начало задачи, которая давалась на первом курсе физфака по программированию.
$m$ карт раскладывается на $n$ кучек, затем берётся та кучка, в которую упала последняя карта и раскладывается в те же кучки в том же порядке, затем снова та кучка, в которую упала последняя карта раскладывается и так далее.
Например, если имеется три кучки и три карты, то процесс выглядит так (указано текущее число карт в кучках, подчёркнута кучка, в которую упала последняя карта): 1 1 1, 2 1 0, 1 2 0, 2 1 0, 3 0 0.
Вопрос: обязательно ли настанет такой момент, когда все карты соберутся в первой кучке?
Как это доказать для любых $m$ и $n$ ($m\ge n$)?

[maxal]

zbl в сообщении #218757 писал(а):

Например, если имеется три кучки и три карты, то процесс выглядит так (указано текущее число карт в кучках, подчёркнута кучка, в которую упала последняя карта): 1 1 1, 2 1 0, 1 2 0, 2 1 0, 3 0 0.

А разве тут такой расклад: 1 1 1, 2 1 0, 1 2 0, 0 3 0 ?
Или я не понял как вы раскладываете карты из позиции 2 1 0 ?

zbl в сообщении #218757 писал(а):

Вопрос: обязательно ли настанет такой момент, когда все карты соберутся в первой кучке?

В первой или все-таки одной? В примере выше у меня получается, что все карты попадают во вторую кучку.

Вот тут была похожая задачка: http://www.nsu.ru/phorum/read.php?f=29&i=5624&t=5467

[zbl]

maxal в сообщении #218759 писал(а):

zbl в сообщении #218757 писал(а):

Например, если имеется три кучки и три карты, то процесс выглядит так (указано текущее число карт в кучках, подчёркнута кучка, в которую упала последняя карта): 1 1 1, 2 1 0, 1 2 0, 2 1 0, 3 0 0.

А разве тут такой расклад: 1 1 1, 2 1 0, 1 2 0, 0 3 0 ?
Или я не понял как вы раскладываете карты из позиции 2 1 0 ?

Из 2 1 0 (последняя лежит в первой кучке, берём её) раскладываем снова точно так же: берём две в руку из первой кучки, кладём в первую одна, во второй уже одна есть -- туда идёт ещё одна.
Получается 1 2 0 -- последняя упала во вторую кучку.

-- 01 июн 2009 01:31 --

maxal в сообщении #218759 писал(а):

zbl в сообщении #218757 писал(а):

Вот тут была похожая задачка: http://www.nsu.ru/phorum/read.php?f=29&i=5624&t=5467

Похожая; но решения там не вижу.
Тут, конечно, тоже интересно количество шагов, и даже больше скажу -- интересна финальная перестановка карт в колоде в зависимости от числа кучек.
Но в данный момент интересен только факт, соберутся или нет при любых числах карт и кучек -- как это строго показать?

[TOTAL]

Не соберутся в одной кучке.
Например, 4 карты кидаем в 2 кучки: 1, 2, 1, 1 (это в какую кучку кидаем карту)

[maxal]

TOTAL
Как я понял, для 4-х карт и 2-х кучек получаются такие расклады:
2 2
3 1
4 0

[TOTAL]

maxal
Если раскладывать в указанном мною порядке, то получаются расклады
3 1
2 2
1 3
3 1
.............

[maxal]

TOTAL
Игра начинается с разложения $m$ по $n$ кучкам, то есть по сути с позиции:

$$m \underbrace{0\ 0\ \dots\ 0}_{n-1}$$

и нужно доказать, что начав с этой позиции, мы в нее же рано или поздно вернемся.

[TOTAL]

Я не так понимаю задачу. В условии не сказано про порядок раскладки в кучки. Я считал порядок раскладки произвольным. Главное, чтобы при последующих раскладках этот порядок соблюдался. Пусть автор уточняет условие.

[maxal]

TOTAL
А по-моему все понятно. Раскладывая 4 карты по 2-м кучкам, получаем 2 2; а 7 карт по 3-м кучкам - 3 2 2 и т.д.
См.:

zbl в сообщении #218757 писал(а):

$m$ карт раскладывается на $n$ кучек, затем берётся та кучка, в которую упала последняя карта и раскладывается в те же кучки в том же порядке

[TOTAL]

maxal в сообщении #218784 писал(а):

Игра начинается с разложения $m$ по $n$ кучкам, то есть по сути с позиции:

$$m \underbrace{0\ 0\ \dots\ 0}_{n-1}$$

и нужно доказать, что начав с этой позиции, мы в нее же рано или поздно вернемся.

Если карты раскладываются именно в таком порядке, т.е. по кругу, то мы вернемся в эту позицию потому, что (а) процесс обязан зациклиться и (б) ходы обратимы.

[maxal]

TOTAL
Обратимость ходов - нетривиальная часть задачи.
Я скоро набросаю доказательство.

-- Mon Jun 01, 2009 02:35:13 --

Доказательство.

Позицией назовем вектор $p=(k,q_1,q_2,\dots,q_n)$, где $q_i$ количество карт в $i$-й кучке и $k$ - номер кучки из которой предстоит сделать ход, причем $q_1+q_2+\dots+q_n = m$, $1\leq k\leq n$ и $q_j>0$ для всех $j\leq k$.

Пусть $f(p)$ - это функция, которая позицию $p=(k,q_1,q_2,\dots,q_n)$ переводит в новую позицию, раскидывая карты из кучки $k$ согласно правилам.

Докажем, что для каждой позиции $p$ найдется по крайней мере одна позиция $p'$, для которой $f(p')=p$. Рассмотрим в $p$ кучки с минимальным количеством карт, а среди них самую левую - пусть ее номер равен $t$ (таким образом, для $j<t$ мы имеем $q_j\geq q_t+1$, а для $j\geq t$ - соответственно $q_j\geq q_t$).

Возможны следующие случаи:
1) Если $k\geq t$, то положим

$$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));$$

2) если $k<t$ и существует такое $j\leq k$, что $q_j = q_t + 1$, то переопределим $t$ равным минимальному такому $j$, попадая таким образом в случай 1) рассмотренный выше;
3) если $k<t$ и для всех $j\leq k$ выполняется $q_j > q_t + 1$, то положим

$$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' = g(p)$. Для заданной позиции $p$ вектор $g(p)$ также является позицией. Причем, как нетрудно проверить, $f(g(p))=p$.

Пусть $p$ - произвольная позиция. Рассматривая последовательные итерации $g(\cdot)$ на $p$, из конечности числа различных позиций, заключаем, что либо $g^{(q)}(p)=p$ для некоторого натурального $q$, либо существует такие неотрицательные целые числа $q_1$ и $q_2$, что $g^{(q_1)}(p)\ne g^{(q_2)}(p)$ и $g^{(q_1+1)}(p)= g^{(q_2+1)}(p)$. Второй вариант, однако, невозможен, так как в нем получается противоречие:

$$g^{(q_1)}(p) = f(g^{(q_1+1)}(p)) = f(g^{(q_2+1)}(p)) = g^{(q_2)}(p).$$

Итак, получаем, что $g^{(q)}(p)=p$ для некоторого натурального $q$, а значит и $f^{(q)}(p) = p$, то есть начав с произвольной позиции $p$ мы обязаны в нее же и вернуться при итерациях $f(\cdot)$.
Другими словами, мы доказали, что $f$ и $g$ являются взаимно-обратными перестановками на множестве позиций.

[TOTAL]

Пусть после очередного хода последняя карта положена в кучку $K.$
Отложим в буфер по одной карте из кучки $K$ и изо всех кучек с меньшими номерами.

1 IF(одна из кучек пустая) THEN
на предыдущем ходе была разобрана пустая кучка с наименьшим номером,
а количество карт в ней было равно отложенному количеству карт
(восстановили предыдущую позицию)
ELSE
Изо всех кучек отложим в буфер по одной карте; GOTO 1
ENDIF

[zbl]

maxal в сообщении #218831 писал(а):

Доказательство.

Спасибо.
Это то, что было нужно.

maxal в сообщении #218831 писал(а):

причем $q_1+q_2+\dots+q_n = m$, $1\leq k\leq n$ и $q_j>0$ для всех $j\leq k$.

Опечатка? $q_j\ge 0$

[maxal]

zbl в сообщении #218887 писал(а):

maxal в сообщении #218831 писал(а):

причем $q_1+q_2+\dots+q_n = m$, $1\leq k\leq n$ и $q_j>0$ для всех $j\leq k$.

Опечатка? $q_j\ge 0$

Нет. $k$ - это кучка, куда легла последняя карта, поэтому в ней и во всех предыдущих кучках должна быть как минимум одна карта, то есть $q_j>0$.

[maxal]

В связи с этой задачкой добавил в OEIS последовательности A161135..A161138
Последние две, кстати, нуждаются в большем числе членов - может, найдутся желающие могут повычислять?