2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Камни и кучки
Сообщение27.09.2007, 12:09 
Заслуженный участник


26/06/07
1883
Tel-aviv
neo66 писал(а):
Эта задача предлагалась в свое время на вступительных экзаменах в НМУ. Хороша, а?

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

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

 Профиль  
                  
 
 Physical solution
Сообщение27.09.2007, 18:38 
Аватара пользователя


08/06/07
52
Киев
Вот так бы решал эту задачу физик. :)

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

 Профиль  
                  
 
 
Сообщение27.09.2007, 19:14 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение27.09.2007, 21:09 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение28.09.2007, 05:51 
Заслуженный участник
Аватара пользователя


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

Я решал так (отсутствие других циклов гарантировано)
Поместим камни $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$ взаимно простые, то обязательно наступит момент, когда камень и пустышка примут одинаковое положение по вертикали (камень непосредственно справа от пустышки), что повлечет сдвиг столбцов и уменьшение суммарной высоты камней.

 Профиль  
                  
 
 
Сообщение28.09.2007, 11:27 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение30.09.2007, 01:32 
Заслуженный участник


05/09/05
515
Украина, Киев
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

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

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

 Профиль  
                  
 
 
Сообщение30.09.2007, 07:27 
Заслуженный участник


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

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

 Профиль  
                  
 
 
Сообщение30.09.2007, 08:18 
Заслуженный участник
Аватара пользователя


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


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

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

 Профиль  
                  
 
 
Сообщение30.09.2007, 10:21 
Заслуженный участник


09/02/06
4342
Москва
По аналогии с 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) и для каких диаграмм достигается максимум?

 Профиль  
                  
 
 
Сообщение02.10.2007, 17:48 
Заслуженный участник


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


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

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


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

 Профиль  
                  
 
 
Сообщение05.10.2007, 10:49 
Заслуженный участник


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


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

 Профиль  
                  
 
 
Сообщение05.10.2007, 11:44 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение08.10.2007, 11:34 
Заслуженный участник


09/02/06
4342
Москва
До конца разобрался с этой задачей.
Вот некоторые результаты в виде задач.
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) только в случае, когда последний уровень заполнен полностью или без одного камня.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group