Рассадка гостей за новогодним столом

[Legioner93]

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

[wrest]

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

[Aritaborian]

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

(Оффтоп)

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

[Legioner93]

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

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

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

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

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

[Aritaborian]

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

[Legioner93]

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

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

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

[grizzly]

Legioner93 в сообщении #1365846 писал(а):

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

Я после всех объяснений всё равно не понял. Подскажите на простом примере.

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

[rockclimber]

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

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

-- 04.01.2019, 20:52 --

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

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

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

[wrest]

rockclimber в сообщении #1366007 писал(а):

Только после вашего сообщения дошло - сумма расстояний всегда равна периметру! Ну или я совсем ничего не понял.

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

[rockclimber]

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

-- 04.01.2019, 21:22 --

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

[wrest]

rockclimber в сообщении #1366019 писал(а):

А, дошло. Берем деревяшку, рисуем стол, ставим точки (гостей), забиваем туда гвозди, на гвозди наматываем нитку. Минимизируем длину нитки. Так?

Да, типа того.

rockclimber в сообщении #1366019 писал(а):

Все равно гостям нужна ширина,

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

[grizzly]

wrest в сообщении #1366022 писал(а):

Да, типа того.

Да, спасибо, мне это не пришло в голову.

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

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

[rockclimber]

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

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

Здесь $l$ - искомое расстояние, $x$ - расстояния от ближайшего угла до гостя на той стороне, где сидят двое, $y$ - расстояние от того же угла до гостя с другой стороны.
Можно попробовать написать общую схему решения для произвольного числа гостей и произвольного размера стола.

[Legioner93]

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$ неизвестных.

[rockclimber]

Legioner93 в сообщении #1366120 писал(а):

Но как у вас получилась система из трёх уравнений и трёх неизвестных?

Дополнительным условием была симметрия относительно вертикальной оси. Вот как-то так:

-- 05.01.2019, 20:17 --

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