Задачка.

[intriga123]

Сегодня скучал на лекции и придумал задачку.

Как можно разместить на плоскости девять (жирных) точек, чтобы максимизировать количество непересекающихся линий между ними?
Я придумал конфигурацию с 20-ю connections. Интересно, а можно больше?

И еще интересно, наверняка у такой задачки есть какое-нибудь умно-математическое решение, а не просто рисунки

Comments

[kompleksovnet]

Я тоже сразу подумал о теории графов. Но графы рассматривают связи, то есть там прямые, которые пересекаются. Тем не менее, можно просто нарисовать линию и поставить на ней 9 точек - прямые не пересекаются, а накладываются (мы выполняем поставленное условие). Тогда умно-математическое решение возможно, количество отрезков считается по формуле x = n(n-1)/2, и при 9 точках это 36 отрезков

[intriga123]

Не, ну так не честно. Я это придумывал, рсиуя настоящие черточки! :) Поэтому "накладываются" тоже не принимается. Считаем, что прямые, проведенные нормальной шариковой ручкой, не должны касаться друг друга. И сразу: пространство чисто двумерное, пространственно-временной континуум не задействовать, с другой стороны странички не рисовать, ленты Мебиуса не задействовать, и вообще решать то, что попросили! :)

36 - хорошая цифра, в том смысле, что это теоретический предел. То есть, теоретически решения моей задачи лежат в диапазоне от 8 (если по прямой) до 36 (если чисто умозрительно). А вот практически сколько можно максимум?

[kompleksovnet]

На промокашке и у меня больше 20 не выходит.

[intriga123]

Кстати, я вот вчера немножко дальше подумал над твоей формулой.
36 (для 9-ти точек) - это теоретический максимум связей. Интересно, 3D пространство всегда позволяет его достичь? Или придется уходить в большую размерность?

Ну, или в еще общем виде, какова минимальная размерность пространства, которая позволит ВСЕГДА построить фигуру с количеством узлов n и связей n(n-1)/2? Является ли размерность величиной постоянной (например, 3D), или это тоже должна быть функция n?

Но это я рисовать не буду. Времени жалко :)

[ivan_ivan_ivan]

Линия проходящая через 3 точки участвует как одна? Или как 2 набора точек?

[intriga123]

Как два отрезка

DoctorIvanov

[anonymous]

Россия

Охота