Задача Кобона о треугольниках

Зада́ча Кобо́на о треуго́льниках — нерешённая задача комбинаторной геометрии, сформулированная Кодзабуро Фудзмурой (яп. 藤村幸三郎 фудзимура ко:дзабуро:), известным также как Кобон. В задаче спрашивается, каково максимальное число N(k) неперекрывающихся треугольников, стороны которых принадлежат конфигурации k прямых. Вариант задачи рассматривается в проективной плоскости, а не в евклидовой плоскости, и в этом случае требуется, чтобы треугольники не пересекались другими прямыми конфигурации[1].

Нерешённые проблемы математики:
Как много неперекрывающихся треугольников могут быть образованы конфигурацией k прямых?
Треугольники Кобона, образованные 3, 4 и 5 отрезками

Верхние границы

Сабуро Тамура доказал, что наибольшее целое, не превосходящее k(k − 2)/3, даёт верхнюю границу максимального числа неперекрывающихся треугольников, получаемых из k прямых[2]. В 2007 году Иоганес Бадер и Жиль Клеман (нем. Johannes Bader, фр. Gilles Clément) нашли более сильную границу, доказав, что верхняя граница Тамуры не может быть достигнута для любого k, сравнимого с 0 или 2 по модулю 6[3]. Поэтому максимальное число треугольников на единицу меньше границы Тамура для этих случаев. Совершенные решения (решение задачи Кобона, дающие максимальное число треугольников) известны для k = 3, 4, 5, 6, 7, 8, 9, 13, 15 и 17[4]. Для k = 10, 11 и 12 наилучшие известные решения на единицу меньше верхней границы.

Если дано совершенное решение с k0 прямыми, другие решения задачи Кобона о треугольниках могут быть найдены для всех значений ki, где

при помощи процедуры Д. Форжа и Дж. Л. Рамиреза Альфонсина[1][5]. Например, решение для k0 = 3 приводит к максимальному числу неперекрывающихся треугольников для k = 3, 5, 9, 17, 33, 65, …

k3456789101112131415161718192021OEIS
Верхняя граница Тамуры для N(k)1258111621263340475665748596107120133[6]
Верхняя граница Клемана и Бадера1257111521263339475565748595107119133—
Лучшие известные решения1257111521253238475365728593104115130[7]

Примеры
  • 3 прямых образуют треугольник
  • 4 прямых
  • 5 прямых
  • 6 прямых
  • 7 прямых

См. также

Примечания
  1. Forge, Ramírez Alfonsín, 1998, p. 155–161.
  2. Weisstein, Eric W. Kobon Triangle (англ.) на сайте Wolfram MathWorld.
  3. G. Clément and J. Bader. Tighter. Upper Bound for the Number of Kobon Triangles. Draft Version (недоступная ссылка) (2007). Дата обращения: 10 марта 2016. Архивировано 11 ноября 2017 года.
  4. Ed Pegg Jr. on Math Games.
  5. Matlab code illustrating the procedure of D. Forge and J. L. Ramirez Alfonsin. Retrieved on 9 May 2012.
  6. Последовательность A032765 в OEIS.
  7. Последовательность A006066 в OEIS.

Литература
  • Forge D., Ramírez Alfonsín J. L. . Straight line arrangements in the real projective plane // Discrete and Computational Geometry, 1998, 20 (2). — P. 155—161. — doi:10.1007/PL00009373.

Ссылки


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.