Проблема треугольника Кобона

Треугольники Кобона, состоящие из 3, 4 и 5 отрезков прямых.

Нерешенная задача по математике :

Сколько непересекающихся треугольников можно образовать, расположив

k

линии?

(еще нерешенные задачи по математике)

Проблема треугольника Кобона — нерешенная проблема комбинаторной геометрии, впервые сформулированная Кобоном Фудзимурой (1903–1983). Задача требует наибольшего числа N ( k ) непересекающихся треугольников, стороны которых лежат на наборе из k прямых . Вариации задачи рассматривают проективную плоскость, а не евклидову плоскость, и требуют, чтобы треугольники не пересекались никакими другими линиями расположения. ^[1]

Известные верхние границы

Сабуро Тамура доказал, что количество непересекающихся треугольников, реализуемых формулой $k$ линии не более $\lfloor k(k-2)/3\rfloor$ . Г. Клеман и Ж. Бадер убедительнее доказали, что эта граница не может быть достигнута, когда $k$ конгруэнтно 0 или 2 (по модулю 6). ^[2] Таким образом, максимальное количество треугольников в этих случаях не более чем на один меньше. Те же границы можно эквивалентно сформулировать без использования функции пола следующим образом: ${\begin{cases}{\frac {1}{3}}k(k-2)&{\text{when }}k\equiv 3,5{\pmod {6}};\\{\frac {1}{3}}(k+1)(k-3)&{\text{when }}k\equiv 0,2{\pmod {6}};\\{\frac {1}{3}}(k^{2}-2k-2)&{\text{when }}k\equiv 1,4{\pmod {6}}.\end{cases}}$

Решения, дающие такое количество треугольников, известны, когда $k$ это 3, 4, 5, 6, 7, 8, 9, 13, 15 или 17. ^[3] Для k = 10, 11 и 12 лучшие известные решения достигают количества треугольников на один меньше верхней границы.

Известные конструкции

Известны следующие границы:

к	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	ОЭИС
Верхняя граница Тамуры для N ( k )	1	2	5	8	11	16	21	26	33	40	47	56	65	74	85	96	107	120	133	А032765
Верхняя граница Клемана и Бадера	1	2	5	7	11	15	21	26	33	39	47	55	65	74	85	95	107	119	133	-
самое известное решение	1	2	5	7	11	15	21	25	32	38	47	53	65	72	85	93	104	115	130	А006066

В проективной плоскости

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

обычные треугольники среди остальных линий, ограниченные тремя конечными отрезками,
треугольники, ограниченные двумя лучами, встречающимися в общей вершине, и отрезком линии, находящимся на бесконечности, и
треугольники, ограниченные конечным отрезком прямой и двумя параллельными лучами, пересекающимися в вершине бесконечной прямой.

Например, расположение пяти конечных линий, образующих пентаграмму , вместе с шестой линией, находящейся на бесконечности, имеет десять треугольников: пять в пентаграмме и еще пять, ограниченные парами лучей.

Д. Фордж и Дж. Л. Рамирес Альфонсин предложили метод перехода от расположения в проективной плоскости с $k>3$ линии и ${\tfrac {1}{3}}k(k-1)$ треугольники (максимально возможный для $k>3$ ), с некоторыми дополнительными свойствами, к другому решению с $K=2k-1$ линии и ${\tfrac {1}{3}}K(K-1)$ треугольники (опять же максимум), с теми же дополнительными свойствами. По их наблюдениям, этот метод можно начать с описанного выше проективного расположения шести линий и десяти треугольников, создавая оптимальные проективные расположения, число линий которых равно