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 <math>N(k)</math> sich maximal erzeugen lassen, wenn man <math>k</math> Geraden in der Ebene zeichnet.<ref>Kobon Triangle bei Mathworld.</ref> 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 3 Geraden lässt sich 1 Dreieck erzeugen.

Aus 3 Geraden lässt sich 1 Dreieck erzeugen.
Aus 4 Geraden lassen sich 2 Dreiecke erzeugen.

Aus 4 Geraden lassen sich 2 Dreiecke erzeugen.
Aus 5 Geraden lassen sich 5 Dreiecke erzeugen.

Aus 5 Geraden lassen sich 5 Dreiecke erzeugen.
Aus 6 Geraden lassen sich 7 Dreiecke erzeugen.

Aus 6 Geraden lassen sich 7 Dreiecke erzeugen.
Aus 7 Geraden lassen sich 11 Dreiecke erzeugen.

Aus 7 Geraden lassen sich 11 Dreiecke erzeugen.

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

Obere Schranke

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

<math>\lfloor k\left(k-2\right)/3\rfloor</math>

eine obere Schranke für die maximale Anzahl an nicht-überlappenden Dreiecken aus <math>k</math> Geraden.

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

<math>\lfloor k\left(k-2\right)/3\rfloor - \chi_{\{ k | (k\mod 6) \in \{0,2\} \}}(k)</math>

von Clément und Bader hervorgeht<ref name="bader"><templatestyles src="Webarchiv/styles.css" />{{#if:20160303180311

      | {{#ifeq: 20160303180311 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: Verschiedene Lösungen und Beweis für obere Schranke | {{#invoke:WLink|getEscapedTitle|Verschiedene Lösungen und Beweis für obere Schranke}} | {{#invoke:Webarchiv|getdomain|http://www.tik.ee.ethz.ch/sop/people/baderj/?page=other.php}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20160303180311}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/DatumDer Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
         | {{#if: Verschiedene Lösungen und Beweis für obere Schranke | {{#invoke:WLink|getEscapedTitle|Verschiedene Lösungen und Beweis für obere Schranke}} | {{#invoke:Webarchiv|getdomain|http://www.tik.ee.ethz.ch/sop/people/baderj/?page=other.php}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20160303180311}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: Verschiedene Lösungen und Beweis für obere Schranke | {{#invoke:WLink|getEscapedTitle|Verschiedene Lösungen und Beweis für obere Schranke}} | {{#invoke:Webarchiv|getdomain|http://www.tik.ee.ethz.ch/sop/people/baderj/?page=other.php}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: Verschiedene Lösungen und Beweis für obere Schranke | {{#invoke:WLink|getEscapedTitle|Verschiedene Lösungen und Beweis für obere Schranke}} | {{#invoke:Webarchiv|getdomain|http://www.tik.ee.ethz.ch/sop/people/baderj/?page=other.php}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: Verschiedene Lösungen und Beweis für obere Schranke | {{#invoke:WLink|getEscapedTitle|Verschiedene Lösungen und Beweis für obere Schranke}} | {{#invoke:Webarchiv|getdomain|http://www.tik.ee.ethz.ch/sop/people/baderj/?page=other.php}} }} (Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: Verschiedene Lösungen und Beweis für obere Schranke | {{#invoke:WLink|getEscapedTitle|Verschiedene Lösungen und Beweis für obere Schranke}} | {{#invoke:Webarchiv|getdomain|http://www.tik.ee.ethz.ch/sop/people/baderj/?page=other.php}} }}  
                 }}}}}}}}{{#if:
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20160303180311|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://www.tik.ee.ethz.ch/sop/people/baderj/?page=other.php}}
    || {{#if:  || }} URL/Pfad ungültig.
  }}{{#if: Verschiedene Lösungen und Beweis für obere Schranke
    | {{#if: {{#invoke:WLink|isBracketedLink|Verschiedene Lösungen und Beweis für obere Schranke}}
        | {{#if:  || }} Linktext ungültig.
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt Linktext fehlt.
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://www.tik.ee.ethz.ch/sop/people/baderj/?page=other.php%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://www.tik.ee.ethz.ch/sop/people/baderj/?page=other.php%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://www.tik.ee.ethz.ch/sop/people/baderj/?page=other.php }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }}</ref>. <math>\chi</math> bezeichnet dabei die charakteristische Funktion.

Rekursives Verfahren

Im Jahr 1998 bewiesen D. Forge and J. L. Ramirez Alfonsin, dass es für unendlich viele Werte <math>k</math> Anordnungen gibt, die die obere Schranke von Tamura erreichen.<ref name="forge">"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.</ref> Der Beweis beinhaltet ein rekursives Verfahren, mit dem aus einer perfekten Lösung für <math>k_0</math> Geraden – d. h. eine Lösung, welche die maximale Anzahl von <math>\,k(k-2)/3\,</math> Dreiecken erreicht – weitere perfekte Anordnungen für <math>k_{n+1}\! = 2 k_{n} - 1\,</math> Geraden berechnet werden können.

Tabelle der berechenbaren Lösungen für <math>k \leq 5633</math>
<math>\boldsymbol k</math> (Serien stehen jeweils untereinander)								Anzahl der Dreiecke <math>\boldsymbol{N(k)}</math>
				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
...	...	...	...	...	...	...	...	...	...	...	...	...	...	...	...

Bekannte Lösungen

Perfekte Lösungen, also Kobon-Dreiecke, welche die obere Schranke erreichen, sind bekannt für <math>k = 3 \ldots 13,\, 15\ldots 17,\, 19,\, 21,\, 23,\, 25,\, 27,\, 29,\, 31,\, 33</math>.<ref>Tighter Upper Bound for the Number of Kobon Triangles, 2007</ref>

Die folgende Tabelle zeigt die kleinsten oberen Schranken sowie die besten bekannten Lösungen für <math>k = 3 \ldots 33</math>.

k	3	4	5	6	7	8	9	10	11	12
obere Schranke für N(k)	1	2	5	7	11	15	21	25	32	38
beste bekannte Lösung	1	2	5	7	11	15	21	25	32	38

k	13	14	15	16	17	18	19	20	21	22
obere Schranke für N(k)	47	54	65	72	85	94	107	117	133	144
beste bekannte Lösung	47	53	65	72	85	93	107	116	133	143

k	23	24	25	26	27	28	29	30	31	32
obere Schranke für N(k)	161	173	191	205	225	239	261	276	299	316
beste bekannte Lösung	161	172	191	?	225	?	261	?	299	?

k	33		37		41		45		49
obere Schranke für N(k)	341		431		533		645		767
beste bekannte Lösung	341		431		533		645		767

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

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 19 Geraden, die 107 Dreiecke generieren
Perfekte Lösung für 21 Geraden, die 133 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: <math>N(11)=32</math>.<ref>Constructing Optimal Kobon Triangle Arrangements via Table Encoding, SAT Solving, and Heuristic Straightening</ref>

Weblinks

[{{canonicalurl:Commons:Category:{{#if:Kobon triangles|Kobon triangles|Kobon-Dreiecke}}|uselang=de}} Commons: {{#if:|{{{2}}}|{{#if:Kobon triangles|Kobon triangles|{{#invoke:WLink|getArticleBase}}}}}}]{{#switch:1

|X|x= |0|-= |S|s= – Sammlung von Bildern |1|= – Sammlung von Bildern{{#if:

    | {{#switch: {{#invoke:TemplUtl|faculty|1}}/{{#invoke:TemplUtl|faculty|1}}
        |1/=  und Videos
        |1/1=, Videos und Audiodateien
        |/1=  und Audiodateien}}
    | , Videos und Audiodateien
  }}

|#default= – }}{{#if: Kobon triangles

   | {{#ifeq: {{#invoke:Str|left|kobon triangles|9}} 
       | category:

| FEHLER: Ohne Category: angeben!}}}}

Vorlage:Wikidata-Registrierung

Einzelnachweise

<references > <ref name="pegg">Kolumne von Ed Pegg Jr. auf Math Games</ref> </references >