2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Рассадка гостей за новогодним столом
Сообщение04.01.2019, 11:37 
Заслуженный участник
Аватара пользователя


28/07/09
1112
За прямоугольным столом $a \times b$ рассадить $N$ гостей так, чтобы сумма расстояний между соседями была минимальна. Чему равна эта сумма?

 Профиль  
                  
 
 Re: Рассадка гостей за новогодним столом
Сообщение04.01.2019, 12:49 


05/09/16
6443
Legioner93
Я не понял условие задачи: (
Садим всех на одно место,сумма расстояний ноль.
Что значит "соседи"?

 Профиль  
                  
 
 Re: Рассадка гостей за новогодним столом
Сообщение04.01.2019, 14:08 
Аватара пользователя


11/06/12
8851
calm.angel.driven
Disclaimer: я изложил первую идею, что пришла в голову, и не имею ни малейшего понятия, насколько это совпадает с идеей автора задачи. Аналогично, я совершенно не в курсе, насколько задача в такой постановке вообще решаема. Но моя интерпретация, насколько я вижу, вполне корректна.
Давайте, например, скажем, что гость это единичный отрезок, расположенный на стороне прямоугольника таким образом, что он полностью находится на ней. При этом отрезки не должны перекрываться, но их концы (локти ;-) могут совпадать. Расстоянием между гостями будем считать расстояния между центрами отрезков. Соседями гостя логично считать отрезки, расположенные на одной с данным гостем стороне стола слева и справа от него. При таком определении у данного гостя может оказаться лишь один сосед либо не оказаться их вовсе. Определение соседа можно модифицировать, считая соседом ближайший отрезок по пути следования по периметру стола.

(Оффтоп)

Когда писал, вспоминал это сообщение покойного Профессор Снэйп.

 Профиль  
                  
 
 Re: Рассадка гостей за новогодним столом
Сообщение04.01.2019, 16:31 
Заслуженный участник
Аватара пользователя


28/07/09
1112
wrest
Соседи это значит ближайший по левую руку и ближайший по правую руку.

С глобальным минимумом в "Садим всех на одно место,сумма расстояний ноль" вы совершенно правы, это я упустил! Условие нужно подкорректировать, надо подумать, как именно.

Расскажу, как именно я себе представляю задачу. Сажаем, например, 4 гостя за квадратный стол. Сажаем случайно, но примерно равномерно по периметру. Можно на углы, если хотите.

Будем считать, что гости могут двигаться только вдоль стола (как будто на рельсах). Дальше добавим между соседними гостями "упругие связи", и "потрясём" систему. Умозрительно кажется более-менее очевидно, что при наличии таких связей гости в итоге окажутся по центру сторон стола, правда? Хотя, если трясти систему слишком сильно, то она может "перещелкнуть" в менее интересный, но глобальный минимум -- как раз когда все гости сидят в одной точке. Как бы это только всё формализовать?.. И можно ли устроить связи так, чтобы в итоге минимизировать суммарное расстояние между всеми соседями, или это условие придётся поменять?..

Тем не менее, вопрос, куда в итоге придёт система уже для 5-6 человек даже для квадратного стола мне кажется достаточно интересным.

 Профиль  
                  
 
 Re: Рассадка гостей за новогодним столом
Сообщение04.01.2019, 19:09 
Аватара пользователя


11/06/12
8851
calm.angel.driven
Прошу прощения, моё предложение по интерпретации задачи, как вижу, со свистом пролетает мимо. Ну и пусть. А ваша, Legioner93, интерпретация, предложенная во втором сообщении, напоминает проблему Томсона чем-то.

 Профиль  
                  
 
 Re: Рассадка гостей за новогодним столом
Сообщение04.01.2019, 21:28 
Заслуженный участник
Аватара пользователя


28/07/09
1112
Aritaborian
Действительно, сходство есть. Обозначу отличия, они помогут понять условие тем, кто знаком с задачей Томсона.

1) Гости всё-таки не отталкиваются, а притягиваются, потому что мы хотим их рассадить как можно ближе. Противоположное (социофобное) условие рассматривать не будем.

2) Задача двумерная, в качестве кривой -- квадрат (прямоугольник). Для круглого стола всё слишком просто.

 Профиль  
                  
 
 Re: Рассадка гостей за новогодним столом
Сообщение04.01.2019, 22:32 
Заслуженный участник
Аватара пользователя


09/09/14
6104
Legioner93 в сообщении #1365846 писал(а):
За прямоугольным столом $a \times b$ рассадить $N$ гостей так, чтобы сумма расстояний между соседями была минимальна. Чему равна эта сумма?
Я после всех объяснений всё равно не понял. Подскажите на простом примере.

Пусть $ABCD$ -- квадратный стол со стороной 1, точки $M, K$ середины сторон $AB$ и $CD$, соответственно. В точках $M,K,C,D$ сидят гости. Чему равна искомая сумма? И кто считается соседями $M?$

 Профиль  
                  
 
 Re: Рассадка гостей за новогодним столом
Сообщение04.01.2019, 22:47 
Заслуженный участник


06/07/11
5570
кран.набрать.грамота
grizzly
Только после вашего сообщения дошло - сумма расстояний всегда равна периметру! :oops: Ну или я совсем ничего не понял.

Legioner93
Если гости - точки, чем квадратный стол отличается от круглого с тем же периметром?

-- 04.01.2019, 20:52 --

А, кажется, дошло, как переформулировать задачу, чтобы она имела чуть больше смысла. Нужно поставить условия:
1) каждый гость имеет ширину, допустим, $1$
2) перед каждым гостем на столе должно быть свободное пространство размером $1 \times 1$ (для тарелок, кружек и т. п).

Дальше задача в том, чтобы для $N$ гостей подобрать стол оптимального размера... Например, еще и с дополнительным условием на соотношение сторон стола.

Хотя не, вроде бы тоже ерунда какая-то.

 Профиль  
                  
 
 Re: Рассадка гостей за новогодним столом
Сообщение04.01.2019, 23:13 


05/09/16
6443
rockclimber в сообщении #1366007 писал(а):
Только после вашего сообщения дошло - сумма расстояний всегда равна периметру! :oops: Ну или я совсем ничего не понял.

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

 Профиль  
                  
 
 Re: Рассадка гостей за новогодним столом
Сообщение04.01.2019, 23:21 
Заслуженный участник


06/07/11
5570
кран.набрать.грамота
wrest
А, дошло. Берем деревяшку, рисуем стол, ставим точки (гостей), забиваем туда гвозди, на гвозди наматываем нитку. Минимизируем длину нитки. Так? Все равно гостям нужна ширина, иначе гостей всегда будет максимум 4, по одному в центре каждой стороны.

-- 04.01.2019, 21:22 --

Или минимизировать надо среднеквадратическое отклонение, например.

 Профиль  
                  
 
 Re: Рассадка гостей за новогодним столом
Сообщение04.01.2019, 23:31 


05/09/16
6443
rockclimber в сообщении #1366019 писал(а):
А, дошло. Берем деревяшку, рисуем стол, ставим точки (гостей), забиваем туда гвозди, на гвозди наматываем нитку. Минимизируем длину нитки. Так?

Да, типа того.
rockclimber в сообщении #1366019 писал(а):
Все равно гостям нужна ширина,

Ну ессно, какая-то нужна. Причем, если ширина гостя $\varepsilon$, то должно быть очевидно $N\varepsilon \le P$, где $P$ -- длина кривой (периметр стола), $N$ -- количество гостей.

 Профиль  
                  
 
 Re: Рассадка гостей за новогодним столом
Сообщение04.01.2019, 23:52 
Заслуженный участник
Аватара пользователя


09/09/14
6104
wrest в сообщении #1366022 писал(а):
Да, типа того.
Да, спасибо, мне это не пришло в голову.

Тогда я предлагаю для определённости считать задачу дискретной: допустимые места за столом фиксированы, включают угловые точки (не будем суеверными :) и распределены равномерно на расстоянии 1 друг от друга. В этих единицах длины сторон стола заданы целыми числами.

Хотел бы услышать комментарий ТС по этому предложению.

 Профиль  
                  
 
 Re: Рассадка гостей за новогодним столом
Сообщение05.01.2019, 01:35 
Заслуженный участник


06/07/11
5570
кран.набрать.грамота
grizzly
Мне другой вариант нравится. Места не фиксированы, но фиксировано расстояние между гостями - оно должно быть одинаковое для любой пары соседей. Например, для квадратного стола со стороной $2$ и пяти гостей получаем систему уравнений:

$$
\begin{cases}
2x + l = 2 \\
x^2 + y^2 = l^2 \\
(1 - y)^2 + 1 = l^2
\end{cases}
$$
Здесь $l$ - искомое расстояние, $x$ - расстояния от ближайшего угла до гостя на той стороне, где сидят двое, $y$ - расстояние от того же угла до гостя с другой стороны.
Можно попробовать написать общую схему решения для произвольного числа гостей и произвольного размера стола.

 Профиль  
                  
 
 Re: Рассадка гостей за новогодним столом
Сообщение05.01.2019, 10:08 
Заслуженный участник
Аватара пользователя


28/07/09
1112
grizzly в сообщении #1366027 писал(а):
Тогда я предлагаю для определённости считать задачу дискретной: допустимые места за столом фиксированы, включают угловые точки (не будем суеверными :) и распределены равномерно на расстоянии 1 друг от друга. В этих единицах длины сторон стола заданы целыми числами.

Хотел бы услышать комментарий ТС по этому предложению


Я пока не вижу, чем тут помогут дискретные места вместо непрерывных? Всё равно гости могут захотеть собраться в одном месте или, если мы это запретим, максимально рядом на одной стороне.

-- Сб янв 05, 2019 10:24:13 --

rockclimber в сообщении #1366059 писал(а):
Мне другой вариант нравится. Места не фиксированы, но фиксировано расстояние между гостями - оно должно быть одинаковое для любой пары соседей.


rockclimber в сообщении #1366059 писал(а):
Например, для квадратного стола со стороной $2$ и пяти гостей получаем систему уравнений:

$$
\begin{cases}
2x + l = 2 \\
x^2 + y^2 = l^2 \\
(1 - y)^2 + 1 = l^2
\end{cases}
$$


Я тоже думал над таким вариантом условия, можно попробовать. Но как у вас получилась система из трёх уравнений и трёх неизвестных? Из общих соображений должно быть $N-1$ уравнений и $N$ неизвестных.

 Профиль  
                  
 
 Re: Рассадка гостей за новогодним столом
Сообщение05.01.2019, 22:16 
Заслуженный участник


06/07/11
5570
кран.набрать.грамота
Legioner93 в сообщении #1366120 писал(а):
Но как у вас получилась система из трёх уравнений и трёх неизвестных?
Дополнительным условием была симметрия относительно вертикальной оси. Вот как-то так:

-- 05.01.2019, 20:17 --

Ой, третье уравнение неправильное! Должно быть $(2 - y)^2 + 1 = l^2$.


Вложения:
guests.JPG
guests.JPG [ 73.97 Кб | Просмотров: 0 ]
 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу 1, 2  След.

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



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

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


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

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