Кащей, золото и шахматная доска

[Dave]

На шахматной доске лежит несколько стопок золотых монет, каждая стопка в определённой клетке. На каждом шаге Кащей Бессмертный берёт 3 или 4 монеты из одной клетки и перекладывает их в соседние по стороне клетки, каждую монету в свою клетку. Доказать, что этот процесс не может продолжаться бесконечно.

[zhoraster]

3 или 4 монеты -- из угловых, получается, не берет?

[Dave]

zhoraster в сообщении #516682 писал(а):

3 или 4 монеты -- из угловых, получается, не берет?

Совершенно верно.

[Cash]

У нас есть запрет на ходы с угловых клеток. Количество перекладываний из клеток, соседних с запрещенными, конечно. Пусть $N$ последний такой ход. Рассмотрим игру, начиная с хода $N+1$. Она идентична исходной, но с запретом уже на 12 клеток. Применив еще несколько раз наше рассуждение, мы придем к тому, что вся доска состоит из запрещенных клеток.

[Dave]

Хорошо. А если я переформулирую задачу так?

На шахматной доске лежит несколько стопок золотых монет, каждая стопка в определённой клетке. На каждом шаге Кащей Бессмертный берёт 3 или 4 монеты из одной клетки и перекладывает их в соседние по стороне клетки, каждую монету в свою клетку. Доказать, что Кащей ни при каком выборе порядка ходов не сможет осуществить их больше, чем $100n$ раз, где $n$ - количество монет на доске.

[Cash]

Пусть вес каждой монеты равен 1. Расставим в каждую клетку следующие весовые мультипликаторы (вес монеты становится равным значению соответствующего мультипликатора)
$\begin{vmatrix} 24&12&6&3&3&6&12&24 \\ 12&7&4&2&2&4&7&12\\ 6&4&2&1&1&2&4&6\\ 3&2&1&0&0&1&2&3\\ 3&2&1&0&0&1&2&3\\ 6&4&2&1&1&2&4&6\\ 12&7&4&2&2&4&7&12\\ 24&12&6&3&3&6&12&24 \\ \end{vmatrix}$
Можно проверить, что каждая операция Кащея приводит к увеличению веса, как минимум, на 1. Вес всех монет не может быть больше $24n$. А значит Кащей не сможет ходить более $24n$ раз.

[TOTAL]

Cash в сообщении #517545 писал(а):

Можно проверить, что каждая операция Кащея приводит к увеличению веса, как минимум, на 1.

Из клетки с цифрой 1 можно переложить 3 монеты без изменения веса.

[zhoraster]

Там практически отовсюду можно, и даже можно вес уменьшить. Но истина где-то рядом.

[Cash]

Я исходил из того, что 3 перекладывается из граничных, а из внутренних 4 - по числу соседей. Мне казалось, что иначе процесс можно сделать бесконечным.

-- Вт дек 20, 2011 17:07:50 --

Все-таки бесконечным не будет - все равно из внутренних квадратов будет накапливаться сначала на углы, потом уходить на квадрат побольше. Сейчас попробуем подогнать коэффициенты

-- Вт дек 20, 2011 17:38:18 --

Вот эта подходит
$\begin{pmatrix} 82&39&18&8&8&18&39&82 \\ 39&18&8&4&4&8&18&39 \\ 18&8&3&1&1&3&8&18 \\ 8&4&1&0&0&1&4&8 \\ 8&4&1&0&0&1&4&8 \\ 18&8&3&1&1&3&8&18 \\ 39&18&8&4&4&8&18&39 \\ 82&39&18&8&8&18&39&82\\ \end{pmatrix}$

[Dave]

Да, так подходит. В условии действительно не утверждалось, что из внутренних клеток нужно брать обязательно 4 монеты.