Камни и кучки

[arqady]

neo66 писал(а):

Эта задача предлагалась в свое время на вступительных экзаменах в НМУ. Хороша, а?

Это было сказано по поводу задачи про стеклянные шарики.
Примерно в то же время появилась следующая задача:

Имеются 45 камней, разделенных на несколько непустых кучек.
Из каждой кучки берём по камню, образуем новую кучку и т. д.
Докажите, что начиная с некоторого момента образуются 9 кучек со следующим количеством камней: 1, 2, 3, 4, 5, 6, 7, 8 и 9.

[Sasha Rybak]

Вот так бы решал эту задачу физик. :)

Заменим камни на квадратики 1*1. :) В каждой кучке поставим квадратики друг на друга. Теперь поставим башенки вплотную - по убыванию высоты при просмотре слева направо. {Такая конструкция называется диаграммой Юнга.} Повернём конструкцию на 45 градусов против часовой стрелки. Рассмотрим её потенциальную энергию как сумму энергий всех квадратиков, а для квадратика энергией будет сумма его координат: номер башенки + номер квадратика в башенке.
Не очень сложно показать, что в результате преобразования, указанного в условии задачи, потенциальная энергия не увеличивается. Осталось показать, что время от времени она будет уменьшаться. Для этого рассмотрим верхнюю границу диаграммы (уже после поворота на 45 градусов). На этой границе, если она не соответствует набору кучек (1, 2, ..., 9), будет или сторона длины не менее 3, или хотя бы две стороны длины 2 (хотя бы две именно потому, что 45=m(m+1)/2). В обоих случаях после одного или нескольких преобразований происходит падение энергии.

[Руст]

Лучше диаграмму сразу повернуть на 45 градусов, направив основания по оси x=y. Тогда указанная сумма действительно является потенциальной энергией кубиков. При этом преобразование является вырыванием правых кубиков и сложением их слева по симмметрии, передвижением остальных на один шаг право-вверх и лево вниз (при этом потенциальная энергия не меняется) и упорядочением образованного ряда за счёт чего уменьшается потенциальная энергия, если образованный ряд не является максимальным по длине. Только доказать, что рано или поздно потенциальная энергия уменьшится уже не является физической задачей. Она математическая и требуется математический подход. Хотя факт не увеличения потенциальной энергии поддается физическому объяснению.
Математический подход заключается в задании отображения из множества диаграмм в множества диаграмм f указанного вида и найти цикловые орбиты при повторении этого отображения. 1-циклом является тривиальная неподвижная точка (9,8,7,..,1). Для доказательства отсутствия других циклов надо выбрать сжимающую функцию типа указанной потенциальной. Но мне это не удалась.

[maxal]

Руст
Вспомнилась другая твоя задача про камни и кучки:
http://www.nsu.ru/phorum/read.php?f=29&i=5467&t=5467
Ее решение в общем виде так никто и не озвучил.

[TOTAL]

Руст писал(а):

Для доказательства отсутствия других циклов надо выбрать сжимающую функцию типа указанной потенциальной. Но мне это не удалась.

Я решал так (отсутствие других циклов гарантировано)
Поместим камни $k$-ой кучки в точки с координатами $(k, 1), (k, 2)$ и т.д. без пропусков. Кучки по высоте не упорядочиваем ни сразу, ни потом; это произойдет само собой.

Один ход соответствует перемещению камня из точки $(i, j)$ в точку $(i+1, j-1)$. (Исключение составляют камни в точках вида $(i, 1)$; такой камень будем перемещать в точку $(1, i)$.) При таком перемещении высота (это сумма координат) каждого камня и всех камней вместе не изменится. Если правее опустевшего столбца останутся непустые столбцы, то сдвинем их влево, устранив промежутки. Суммарная высота камней при таком сдвиге уменьшится.

Остается показать, что суммарная высота камней обязана достигнуть минимально возможной величины. Пусть имеется точка без камня (пустышка) на высоте $N$ и пусть имеется камень на высоте большей, чем $N$. Тогда найдется камень на высоте ровно $N+1$ (это потому, что в столбцах камни расположены без пропусков, а столбцы стоят вплотную друг к другу). По мере ходов этот камень и пустышка совершают циклические движения по своим диагоналям с периодами соответственно $N$ и $N-1$. Так как $N$ и $N-1$ взаимно простые, то обязательно наступит момент, когда камень и пустышка примут одинаковое положение по вертикали (камень непосредственно справа от пустышки), что повлечет сдвиг столбцов и уменьшение суммарной высоты камней.

[Руст]

Вообщем мне понравилось идея потенциальной энергии, предложенная Sacha Rybak и развитая TOTAL. Ещё лучше представить это перевёрнутым на 45 градусов и течением камней с постоянной единичной скоростью вправо (не меняя своего уровня). Когда камни доходят до правого конца в следующем шаге они появляются в левом конце на том же уровне. При этом им разрешается сползти (всей строкой) лево-вниз, если повились пустые клетки, что соответствует переупорядочеванию и уменьшению потенциальной энергии при этом. Как показал TOTAL, если нижнее уровни не заполнены полностью, рано или поздно туда сползёт камень, стоящий уровнем выше и так заполнятся все уровни первый уровень всегда заполнен (угловой камень), второй уровень имеющий 2 места (одно место всегда заполнено)заполнится полностью всегда через 2 хода и. т.д.

[Macavity]

TOTAL писал(а):

Руст писал(а):
Для доказательства отсутствия других циклов надо выбрать сжимающую функцию типа указанной потенциальной. Но мне это не удалась.

Я решал так (отсутствие других циклов гарантировано)

В этой задаче как раз самое главное это доказательство отсутствия других циклов. Если это доказать, то и доказывать больше нечего. Случай n=45 (общее количество камней кажется искусственным). Для этого количества камней, аттрактором является точка - 1,2,3,4,5,6,7,8,9. А если n=10? Тогда аттрактор - 1,2,3,4.
А что для других значений n? Нетрудно заметить, что учитывая наличие прогрессии, точка-аттрактор появляется еcли выражение k=${\frac 1 2}$ (-1+\sqrt{1+8n}) является целым числом. В этом случае аттрактор - 1,2,3,....,k. А если k не является целым числом? Как ни странно - аттрактор все равно существует. Только это не точка, а цикл точек. Несколько примеров:
$n=4: цикл-аттрактор (1,1,2) \to (1,3) \to (2,2) \to (1,1,2) \to ...$ (итого три точки в аттракторе)
$n=5: цикл-аттрактор (2,1,2) \to (1,1,3) \to (2,3) \to (2,1,2) \to ...$ (итого три точки в аттракторе)
$n=6: точка-аттрактор (1,2,3) $ (в аттракторе одна точка)
$n=7: цикл-аттрактор (1,2,3,1) \to (1,2,4) \to (1,3,3) \to (2,2,3) \to (1,2,3,1) \to ...$ (итого четыре точки в аттракторе)

Можно сделать несколько предположений (которые наверное не очень сложно доказать).

1) Несмотря на то,что аттрактор при нецелом k состоит из нескольких точек, в него входит точка наиболее близкая к одноточеному аттрактору. Из четырех вышеприведенных примеров - (1,1,2), (2,1,2), (1,2,3), (1,2,3,1).

Или
n=3, точка-аттрактор (1,2) можно и так записать: (1,2,0)
n=4, цикл-аттрактор, в который входит точка (1,2,1)
n=5, цикл-аттрактор, в который входит точка (1,2,2)
n=6, точка-аттрактор (1,2,3) можно и так записать: (1,2,3,0)
n=7, цикл-аттрактор, в который входит точка (1,2,3,1)

2) Второе предположение - длина цикла-аттрактора (очевидно, для нецелого k) равна округлению k в большую сторону.

Пример нахождения цикла-аттрактора.
Пусть, допустим, n=53, тогда 9<k<10. Значит длина цикла-аттрактора равна 10. Дальше, так как 53=45+8, то в цикл входит точка:
1,2,3,4,5,6,7,8,9,8
Отталкиваясь от этой точки нетрудно найти и остальные точки цикла-аттрактора:
1,2,3,4,5,6,7,8,7,10
1,2,3,4,5,6,7,6,9,10
1,2,3,4,5,6,5,8,9,10
1,2,3,4,5,4,7,8,9,10
1,2,3,4,3,6,7,8,9,10
1,2,3,2,5,6,7,8,9,10
1,2,1,4,5,6,7,8,9,10
1,3,4,5,6,7,8,9,10
2,3,4,5,6,7,8,9,9
и опять получаем
1,2,3,4,5,6,7,8,9,8

Посмотрите на динамику изменения цифр - каккие ещё нужны доказательства.

Главный нерешённый вопрос - это единственность аттрактора, вот это надо доказать.

[Руст]

Macavity писал(а):

Второе предположение - длина цикла-аттрактора (очевидно, для нецелого k) равна округлению k в большую сторону.
Главный нерешённый вопрос - это единственность аттрактора, вот это надо доказать.

Первое очевидно, после заполнения уровней с потенциальными энергиями 1,2,3,...m, остается столько камней на незаполненном уровне с потенциальной энергией m+1.
Единственность (для случая, когда число камней не равно m(m+1)/2) имеет место только в случае когда на верхнем уровне 1 камень или одно пустое место. Начните с любого расположения камней на верхнем уровне с заполненными нижними (уже аттрактор), и таких расположений больше 1, если камней на верхнем (m+1 -ом уровне) больше 1 и пустышек больше 1, если m>2.

[TOTAL]

Macavity писал(а):

Второе предположение - длина цикла-аттрактора (очевидно, для нецелого k) равна округлению k в большую сторону.
.......
Главный нерешённый вопрос - это единственность аттрактора, вот это надо доказать.

Про длину цикла неверно. Он может быть в целое число раз короче длины незаполненного уровня.
(Периодично расположенные камни плавают по незаполненному уровню.)

Какой нерешенный вопрос? Единственность аттрактора имеет место ровно в трех случаях:
когда количество камней дает целое число уровней и когда на единицу отличается от такого.

[Руст]

По аналогии с Macavity и я попробую определить оставшиеся открытыми вопросы относительно этой задачи. Пусть общее количество камней N и $m=-[\frac{\sqrt{8N+1}-1}{2}]$ (m - количество уровней в аттракторе, причём m -ый уровень может быть не до конца заполнен).
1. Можно ли по начальному разбиению N (по диаграмме Юнга) сразу вычислить аттрактор. Более тонко, можно ли определить расположение камней на верхнем m - ом уровне, когда только вошли в аттрактор (когда количество уровней стало не больше m и все уровни ниже m полностью заполнены).
2. Пусть M обозначает максимальное значение ходов до выхода в аттрактор по всем диаграммам с N камнями. Легко получить оценку $M<CN\sqrt N, \ C=\frac{2\sqrt 2 }{3}$. Нельзя ли получить более точную оценку M(N) и для каких диаграмм достигается максимум?

[Macavity]

TOTAL писал(а):

Macavity писал(а):

Второе предположение - длина цикла-аттрактора (очевидно, для нецелого k) равна округлению k в большую сторону.
.......
Главный нерешённый вопрос - это единственность аттрактора, вот это надо доказать.

Про длину цикла неверно. Он может быть в целое число раз короче длины незаполненного уровня.
(Периодично расположенные камни плавают по незаполненному уровню.)

Какой нерешенный вопрос? Единственность аттрактора имеет место ровно в трех случаях:
когда количество камней дает целое число уровней и когда на единицу отличается от такого.

Действительно, я ошибся, а Вы правы. Это видно уже для n=8.

[Macavity]

Руст писал(а):

2. Пусть M обозначает максимальное значение ходов до выхода в аттрактор по всем диаграммам с N камнями. Легко получить оценку $M<CN\sqrt N, \ C=\frac{2\sqrt 2 }{3}$. Нельзя ли получить более точную оценку M(N) и для каких диаграмм достигается максимум?

Руст.
А на основании чего Вы получили эту оценку?

[Руст]

Эта оценка получается, если суммировать числа ходов заполнения k уровня по k от 1 до m, Если в k уровне i дырок, а в k+1 уровне заполнены по крайней мере i позиций, то за k(k+1) ход заполнятся все дырки.
Однако эта оценка грубая. Я думаю, что имеет место линейная по N оценка, или чуть больше, типа N(ln N)^k.

[Руст]

До конца разобрался с этой задачей.
Вот некоторые результаты в виде задач.
0.0 Количество уровней выражается формулой

$$m(N)=-[\frac{1-\sqrt{8N+1}}{2}].$$

0.1 Минимальная и максимальная потенциальная энергия (потенциальная энергия камня на позиции (i,j) равна i+j-1) задаются формулой $U_{min}=Nm-\frac{(m-1)m(m+1)}{6}, m=m(N), \ U_{max}=\frac{N(N+1)}{2}$.
1.1 Максимальную потенциальную энергию имеют только две позиции (1,1,....,1) (из N единиц) и (N) (диаграмма с одной кучей), причём первая позиция стоит от аттрактора на 1 дальше, точнее на расстоянии N+2-m(N).Здесь большая куча равномерно расстекает до уровня m(N).
1.2 В случае, когда m чётно и N=(m^2+1)/2 или m чётная и N=m^2/2 или N=m^2/2-1, эти позиции самые дальние от аттрактора, причём количество аттракторов в этих случаях (верхний уровень заполнен наполовину) максимальные, т.е. M(N)=N+2-m(N) в этом случае.
2.1 Когда максимальный уровень заполнен полностью N=m(m+1)/2 среди позиций с потенциальной энергией Umin +1 на максимальном от (единственного) аттрактора расстоянии находится позиция (m-1,m-1,m-2,...,2,1,1) (получающейся снятием верхнего камня от аттрактора (m,m-1,...,2,1) и образованием от этого камня дополнительной кучи с одним камнем). При этом расстояние до аттрактора равна m(m-1)<2N=m(m+1).
2.2 На самом деле при больших m на таком расстоянии отаттрактора находятся много позиций (количество расстёт факториально от m) имеющих потенциальную энергию ,больше Umin+1.
2.3 M(N)=m(m-1) при N=m(m+1)/2.
2.4. M(N) убывает при заполнении нового уровня примерно до половины до N=[(m^2-1)/2], потом растёт. При этом M(N) с m+1 уровнем больше m(m-1)=M(m(m+1)/2) только в случае, когда последний уровень заполнен полностью или без одного камня.