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

Задача Кобона про трикутник — невирішена задача з комбінаторної геометрії, яку сформулював Кодзабуро Фудзмура (Кобон), японський математик (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)\le \lfloor \frac{n(n-2)}{3}\rfloor -I_{\{n|(nmod6)\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. Отже, для $nmod3\in \{0,2\}$ та $n\equiv 0mod2$ не може досягати верхньої межі. Ці дві умови можна узагальнити як $nmod6\in \{0,2\}$ . Тоді:

$B_n=\{\begin{array}{c}\frac{n(n-2)}{3},nmod6\in \{3,5\}\\ \frac{n(n-2)}{3}-1,nmod6\in \{0,2\}\\ \frac{(n-1{)}^2}{3},nmod6\in \{1,4\}\end{array}$

А. Вайнберг знайшов конфігурацію для $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
• Шаблон:MathWorld
• https://sop.tik.ee.ethz.ch/publicationListFiles/cb2007a.pdf Шаблон:Webarchive
• https://oeis.org/A006066 Шаблон:Webarchive