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. 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 ${\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.

Obere Schranke

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 _{\{n|(n\mod 6)\in \{0,2\}\}}(n)}$

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

Rekursives Verfahren

D. Forge and J. L. Ramirez Alfonsin haben bewiesen, dass es für unendlich viele Werte ${\displaystyle 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 ${\displaystyle k_{0}}$ Geraden – eine Lösung, welche die maximale Anzahl von ${\displaystyle k(k-2)/3}$ Dreiecken erreicht – weitere perfekte Anordnungen mit ${\displaystyle 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 ${\displaystyle k=3,5,9,17,33,65}$ etc. bestimmt werden.

Bekannte Lösungen

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

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

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

Weblinks

Einzelnachweise

1. ↑ Kobon Triangle bei Mathworld.
2. 1 2 Kolumne von Ed Pegg Jr. auf Math Games.
3. 1 2 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. ↑ "Matlab Code, welcher das Verfahren von D. Forge and J. L. Ramirez Alfonsin zeigt"