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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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}}}$

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

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

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

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

Подальше дослідження виявило конфігурації для ${\displaystyle n=14}$ - 53 трикутників (верхня межа дорівнює 56), ${\displaystyle n=16}$ - 72 трикутники (74), а також ${\displaystyle 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${\displaystyle ^{*}}$	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