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 $N(k)$ sich maximal erzeugen lassen, wenn man $k$ Geraden in der Ebene zeichnet. 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.

Kobon-Zahl

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 drei Geraden lässt sich ein Dreieck erzeugen.
• 
  Zwei Dreiecke aus vier Geraden
• 
  Fünf Dreiecke aus fünf Geraden
• 
  Sieben Dreiecke aus sechs Geraden
• 
  Elf Dreiecke aus sieben Geraden

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

Obere Schranke

Der folgende Beweis von Saburo Tamura ermöglicht es, für ein gegebenes $k$ eine obere Schranke der Kobon-Zahl zu bestimmen. Jede der $k$ Geraden schneidet die restlichen $k-1$ Linien höchstens einmal. Die $k-1$ Schnittpunkte bilden $k-2$ Liniensegmente (Zaunpfahlproblem), dadurch hat die Figur insgesamt maximal $k(k-2)$ Segmente (im oben gezeigten Beispiel für $k=5$ sind beispielsweise $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 $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

$\lfloor k(k-2)/3\rfloor$

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

Die Schranke wird jedoch nicht immer erreicht. So lassen sich mit $6$ Geraden maximal $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

$\lfloor k(k-2)/3\rfloor -{\chi }_{\{n|(nmod6)\in \{0,2\}\}}(n)$

von Clément und Bader hervorgeht. $\chi$ bezeichnet dabei die charakteristische Funktion.

Rekursives Verfahren

D. Forge and J. L. Ramirez Alfonsin haben bewiesen, dass es für unendlich viele Werte $k$ Anordnungen gibt, welche die obere Schranke von Tamura erreichen. Der Beweis beinhaltet ein rekursives Verfahren, mit dem für eine perfekte Lösung mit $k_0$ Geraden – eine Lösung, welche die maximale Anzahl von $k(k-2)/3$ Dreiecken erreicht – weitere perfekte Anordnungen mit $k_{n+1}=2\cdot k_n-1$ Geraden errechnet werden können. Zum Beispiel können aus der Lösung für 3 Geraden die perfekten Lösungen für $k=3,5,9,17,33,65$ etc. bestimmt werden.

Bekannte Lösungen

Größte bekannte perfekte Lösung (85 Dreiecke aus 17 Geraden)

Perfekte Lösungen, also Kobon-Dreiecke, welche die obere Schranke erreichen, sind bekannt für $k=3,4,5,6,7,8,9,13,15,17,29,33,57,65,\dots$ Außer für diese $k$ ist die maximale Anzahl an Dreiecken nicht bekannt. Für $k=10$ und $11$ enthält die beste bekannte Lösung ein Dreieck weniger als die obere Schranke, für $k=12,16$ und $18$ zwei Dreiecke weniger.

Die folgende Auflistung zeigt die obere Schranke sowie die beste bekannte Lösung für verschiedene $k$.

k	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	...
Obere Schranke für N(k)	1	2	5	7	11	15	21	26	33	40	47	55	65	74	85	95	107	119	133	...
Beste bekannte Lösung	1	2	5	7	11	15	21	25	32	38	47	53	65	72	85	93	104	115	130	...

Die bekannten Kobon-Dreieckszahlen sind fett gedruckt. Sie sind die Vorlage:OEIS.