Kobon-Dreiecke

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[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.

Kobon-Zahl[Bearbeiten]

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.

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[2].

Obere Schranke[Bearbeiten]

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 (z.B. 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\left(k-2\right)/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\left(k-2\right)/3\rfloor - \chi_{\{ n | (n\mod 6) \in \{0,2\} \}}(n)

von Clément und Bader hervorgeht [3]. \chi bezeichnet dabei die charakteristische Funktion.

Rekursives Verfahren[Bearbeiten]

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.[4] Der Beweis beinhaltet ein rekursives Verfahren[5], 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[Bearbeiten]

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, ...[2] 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[3] 93 104 115 130 ...

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

Weblinks[Bearbeiten]

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

Einzelnachweise[Bearbeiten]

  1. Kobon Triangle bei Mathworld
  2. a b Kolumne von Ed Pegg Jr. auf Math Games
  3. a b Verschiedene Lösungen und Beweis für obere Schranke
  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"