Задача Кобона про трикутник

Задача Кобона про трикутник — невирішена задача з комбінаторної геометрії, яку сформулював Кодзабуро Фудзмура (Кобон), японський математик (1903—1983). Задача полягає у з'ясуванні, яке максимальне число $K$ трикутників, що не перекриваються, сторони якого належать конфігурації n прямих, можна утворити. Варіант задачі розглядається в проєктивній площині, а не в евклідовій площині, в цьому випадку вимагається, щоб трикутники не перетиналися іншими прямими.

Ідеальна конфігурація — це розташування $n$ прямих, які попарно перетинаються і кожен відрізок є стороною, а дві відповідні прямі є частиною щонайбільше двох пар трикутників, що мають спільну сторону.

Кобон знайшов найбільшу кількість трикутників $K(n)$, які не перекриваються та їх можна побудувати за допомогою $n$ ліній, тому трикутник Кобона визначається як один із трикутників, побудованих таким чином. Кілька перших  — це 1, 2, 5, 7, 11, 15, 21, …

Аналітичний вираз для знаходження кількості трикутників вивів Сабуро Тамура.

Теорема Сабуро Тамура. $K(n)={\frac {n(n-2)}{3}}$ забезпечує верхню межу максимальної кількості трикутників. Тому для 2,3, … перші кілька верхніх меж — це 2, 5, 8, 11, 16, 21, 26, 33, … .

Лема 1. Якщо (n mod 3) ∈ {0, 2}, то всі конфігурації, які відповідають верхній межі $K(n)={\frac {n(n-2)}{3}}$, є ідеальними конфігураціями. В цих випадках $n(n-2)\equiv 0$ mod 3, а $K(n)=n(n-2)/3$.

Лема 2. У ідеальній конфігурації усі екстремальні точки мають степінь 2.

Лема 3. Ідеальна конфігурація існує лише для непарних $n$.

Г. Клемен та Дж. Бадер. знайшли більш чітку межу кількості трикутників Кобона:

Теорема Г. Клемена та Д. Бадера. Максимальна кількість $K(n)$трикутників Кобона для заданої кількості $n$ прямих в площині обмежені верхніми межами:

$K(n)\leq \lfloor {\frac {n(n-2)}{3}}\rfloor -I_{\{n|(n{\bmod {6}})\in \{0,2\}\}}(n)$, де $I_{A}(X)$ — індикатор функції. Тобто верхня межа за С.Тамури не можа бути досягнута для всіх з $n\equiv 0$ mod 6 $n\equiv 2$ mod 6.

Доведення. Відповідно до Леми 1 верхню межу можна досягти за допомогою конфігурацій, якщо $n\equiv 0$ mod 3 або $n\equiv 2$ mod 3. Але ці ідеальні конфігурації можливі тільки для непарного $n$ згідно Леми 3. Отже, для $n{\bmod {3}}\in \{0,2\}$ та $n\equiv 0{\bmod {2}}$ не може досягати верхньої межі. Ці дві умови можна узагальнити як $n{\bmod {6}}\in \{0,2\}$ . Тоді:

$B_{n}={\begin{cases}{\frac {n(n-2)}{3}},n{\bmod {6}}\in \{3,5\}\\{\frac {n(n-2)}{3}}-1,n{\bmod {6}}\in \{0,2\}\\{\frac {(n-1)^{2}}{3}},n{\bmod {6}}\in \{1,4\}\end{cases}}$

А. Вайнберг знайшов конфігурацію для $n=10$ - 25 трикутників.

В 1967 р. конфігурацію з $n=10$ - 25 трикутників знайшов Б.Грюнбаум, а іншу конфігурацію - С.Хонма. Верхня межа означає, що максимум повинно бути 25 або 26 (невідомо, який). С.Хонма ілюстрував конфігурацію для $n=11$ - 32 трикутники, де 33 трикутники - це теоретично можливий максимум.

У 1996 році С.Грабарчуком і В.Кабановичем були знайдені два інші окремі рішення. У 1999 році В.Кабанович знайшов для $n=12$ , 38-трикутну конфігурацію (верхня межа дорівнює 40) і $n=13$ конфігурацію з 47 трикутників (яка відповідає верхній межі 47 трикутників).

Т.Судзукі знайшов конфігурацію для $n=15$, яка є максимальною, оскільки вона задовольняє верхній межі $N(15)=65$ .

Подальше дослідження виявило конфігурації для $n=14$ - 53 трикутників (верхня межа дорівнює 56), $n=16$ - 72 трикутники (74), а також $n=17$ - 85 трикутників - нове рішення, яке відповідає верхній межі.

Останній рядок таблиці показує нову прив'язку. Зірочка у рядку вказує оптимальні конфігурації на додаток до вже відомих оптимальних рішень (жирним шрифтом).

n	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
(n mod 6)	3	4	5	0	1	2	3	4	5	0	1	2	3	4	5	0	1	2
К(n)	1	2	5	7$^{*}$	11	15	21	25	32	38	47	53	65	72	85	93	104	115
Верхня межа С.Тамури	1	2	5	8	11	16	21	26	33	40	47	56	65	74	85	96	107	120
Верхня межа Г.Клемена та Д.Бадера	1	2	5	7	11	15	21	26	33	39	47	55	65	74	85	95	107	119

Приклади

• 
  3 прямі дають один трикутник
• 
  4 прямі
• 
  5 прямих
• 
  6 прямих
• 
  7 прямих

Література

• K. Fujimura, The Tokyo Puzzle Charles Scribner's Sons, New York, 1978.
• M. Gardner, Wheels, Life, and Other Mathematical Amusements. W. H. Freeman, New York, pp. 170—171 and 178, 1983. [4] E. Pegg, Math Games: Kobon Triangles
• Weisstein, Eric W. Трикутники Кобона(англ.) на сайті Wolfram MathWorld.
• https://sop.tik.ee.ethz.ch/publicationListFiles/cb2007a.pdf [Архівовано 24 червня 2019 у Wayback Machine.]
• https://oeis.org/A006066 [Архівовано 24 листопада 2021 у Wayback Machine.]