Kobon-Dreiecke

Kobon-Dreiecke sind Dreiecke, die durch Zeichnen mehrerer Geraden entstehen. Das dazugehörige Kobon-Dreiecke-Problem ist die Frage, wie viele nichtüberlappende Dreiecke ${\displaystyle N(k)}$ sich maximal erzeugen lassen, wenn man ${\displaystyle k}$ Geraden in der Ebene zeichnet.^[1] Der Namensgeber Kobon Fujimura, ein japanischer Mathematiklehrer und Rätselautor, veröffentlichte die Aufgabenstellung in seinem 1978 erschienenen Buch „The Tokyo Puzzle“.

Lösungen für die Problemstellung ergeben sich durch die Betrachtung von Geraden in der Projektiven Ebene, wobei aber nur affine Dreiecke gezählt werden.

Für bis zu sechs Geraden ist es einfach, durch Ausprobieren Anordnungen zu finden, bei denen möglichst viele Dreiecke entstehen. Während mit drei Geraden nur ein Dreieck gebildet werden kann, sind es für vier, fünf und sechs Geraden maximal 2, 5 bzw. 7.

• 
  Aus 3 Geraden lässt sich 1 Dreieck erzeugen.
• 
  Aus 4 Geraden lassen sich 2 Dreiecke erzeugen.
• 
  Aus 5 Geraden lassen sich 5 Dreiecke erzeugen.
• 
  Aus 6 Geraden lassen sich 7 Dreiecke erzeugen.
• 
  Aus 7 Geraden lassen sich 11 Dreiecke erzeugen.

Wie viele Dreiecke sich für eine beliebige Anzahl Geraden ${\displaystyle k}$ erzeugen lassen (die sogenannte Kobon-Zahl), ist ein bisher ungelöstes Problem der kombinatorischen Geometrie, dessen Lösung als sehr schwer vermutet wird^[2].

Der folgende Beweis von Saburo Tamura ermöglicht es, für ein gegebenes ${\displaystyle k}$ eine obere Schranke der Kobon-Zahl zu bestimmen. Jede der ${\displaystyle k}$ Geraden schneidet die restlichen ${\displaystyle k-1}$ Linien höchstens einmal. Die ${\displaystyle k-1}$ Schnittpunkte bilden ${\displaystyle k-2}$ Liniensegmente (Zaunpfahlproblem), dadurch hat die Figur insgesamt maximal ${\displaystyle k(k-2)}$ Segmente (im oben gezeigten Beispiel für ${\displaystyle k=5}$ sind beispielsweise ${\displaystyle 15}$ Segmente entstanden). Jedes freistehende Dreieck benötigt nun genau drei dieser Liniensegmente, außer es teilt eine oder mehrere Kanten mit einem weiteren Dreieck (im Beispiel ${\displaystyle k=6}$). In diesen Fällen müssen sich jedoch für je zwei Dreiecke drei Geraden in einen Punkt schneiden, was die Anzahl der Liniensegmente um drei verringert – mehr als die zwei eingesparten Liniensegmente.

Somit benötigt jedes Dreieck (mindestens) drei Segmente. Dadurch ist

${\displaystyle \lfloor k\left(k-2\right)/3\rfloor }$

eine obere Schranke für die maximale Anzahl an nicht-überlappenden Dreiecken aus ${\displaystyle k}$ Geraden.

Die Schranke wird jedoch nicht immer erreicht. So lassen sich mit ${\displaystyle 6}$ Geraden maximal ${\displaystyle 7}$ Dreiecke – ein Dreieck weniger als die obere Schranke – bilden. Dies lässt sich mit weiterführenden Überlegungen erklären, aus welchen die engere obere Schranke

${\displaystyle \lfloor k\left(k-2\right)/3\rfloor -\chi _{\{k|(k\mod 6)\in \{0,2\}\}}(k)}$

von Clément und Bader hervorgeht^[3]. ${\displaystyle \chi }$ bezeichnet dabei die charakteristische Funktion.

Im Jahr 1998 bewiesen D. Forge and J. L. Ramirez Alfonsin, dass es für unendlich viele Werte ${\displaystyle k}$ Anordnungen gibt, die die obere Schranke von Tamura erreichen.^[4] Der Beweis beinhaltet ein rekursives Verfahren, mit dem aus einer perfekten Lösung für ${\displaystyle k_{0}}$ Geraden – d. h. eine Lösung, welche die maximale Anzahl von ${\displaystyle \,k(k-2)/3\,}$ Dreiecken erreicht – weitere perfekte Anordnungen für ${\displaystyle k_{n+1}\!=2k_{n}-1\,}$ Geraden berechnet werden können.

Tabelle der berechenbaren Lösungen für ${\displaystyle k\leq 5633}$

${\displaystyle {\boldsymbol {k}}}$ (Serien stehen jeweils untereinander)									Anzahl der Dreiecke ${\displaystyle {\boldsymbol {N(k)}}}$
				3									1
4				5					2				5
7				9					11				21
13		15		17	19	21	23		47		65		85	107	133	161
25	27	29	31	33	37	41	45		191	225	261	299	341	431	533	645
49	53	57	61	65	73	81	89		767	901	1045	1199	1365	1727	2133	2581
97	105	113	121	129	145	161	177		3071	3605	4181	4799	5461	6911	8533	10325
193	209	225	241	257	289	321	353		12287	14421	16725	19199	21845	27647	34133	41301
385	417	449	481	513	577	641	705		49151	57685	66901	76799	87381	110591	136533	165205
769	833	897	961	1025	1153	1281	1409		196607	230741	267605	307199	349525	442367	546133	660821
1537	1665	1793	1921	2049	2305	2561	2817		786431	922965	1070421	1228799	1398101	1769471	2184533	2643285
3073	3329	3585	3841	4097	4609	5121	5633		3145727	3691861	4281685	4915199	5592405	7077887	8738133	10573141
...	...	...	...	...	...	...	...		...	...	...	...	...	...	...	...

Perfekte Lösungen, also Kobon-Dreiecke, welche die obere Schranke erreichen, sind bekannt für ${\displaystyle k=3\ldots 13,\,15\ldots 17,\,19,\,21,\,23,\,25,\,27,\,29,\,31,\,33}$.^[5]

Die folgende Tabelle zeigt die kleinsten oberen Schranken sowie die besten bekannten Lösungen für ${\displaystyle k=3\ldots 33}$.

• 
  Größte bekannte perfekte Lösung (85 Dreiecke aus 17 Geraden)
• 
  Perfekte Lösung für 19 Geraden, die 107 Dreiecke generieren
• 
  Perfekte Lösung für 21 Geraden, die 133 Dreiecke generieren

Die bekannten Kobon-Dreieckszahlen sind fett gedruckt. Sie sind die Folge A006066 in OEIS.

Pavlo Savchuk zeigte 2025, dass mit 11 Geraden höchstens 32 Dreiecke gebildet werden können: ${\displaystyle N(11)=32}$.^[6]

Commons: Kobon triangles – Sammlung von Bildern, Videos und Audiodateien

1. ↑ Kobon Triangle bei Mathworld.
2. ↑ Kolumne von Ed Pegg Jr. auf Math Games
3. ↑ Verschiedene Lösungen und Beweis für obere Schranke (Memento vom 3. März 2016 im Internet Archive)
4. ↑ "Straight line arrangements in the real projective plane", D. Forge and J. L. Ramirez Alfonsin, Discrete and Computational Geometry, Jahrgang 20, Nummer 2, Seiten 155–161, 1998.
5. ↑ Tighter Upper Bound for the Number of Kobon Triangles, 2007
6. ↑ Constructing Optimal Kobon Triangle Arrangements via Table Encoding, SAT Solving, and Heuristic Straightening