Triangle de Kobon

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le problème des triangles de Kobon est un problème non résolu de géométrie combinatoire qui fut énoncé pour la première fois par le mathématicien Kobon Fujimura[1]. Le problème pose la question suivante : quel est le nombre maximal de triangles distincts pouvant être construits à l'aide d'un nombre donné de segments de droite ?

Le problème fut popularisé par Martin Gardner en 1983[2].

Borne supérieure[modifier | modifier le code]

Saburo Tamura a montré[3] que pour n segments de droite, le nombre maximal de triangles qu'il est possible de construire, noté N(n), est inférieur ou égal à \lfloor\frac {n\left(n-2\right)}{3}\rfloor (\lfloor \rfloor désigne la fonction partie entière).

En 2007, Johannes Bader et Gilles Clément ont affiné cette borne[4] : si n est congru à 0 ou 2 modulo 6 alors N(n) est même strictement inférieur à \lfloor\frac {n\left(n-2\right)}{3}\rfloor.

Solutions connues[modifier | modifier le code]

Des solutions maximales, égales à la borne supérieure, sont connues pour 3, 4, 5, 6, 7, 8, 9, 13, 15 et 17 droites. Dans les autres cas, le nombre maximal de triangles n'est pas connu, même si connait des configurations qui se rapproche de cette borne supérieure. Pour 10 et 11 droites, la meilleure solution connue n'est que d'un triangle de moins que la borne donnée par Tamura. Pour 12, 16 et 18 droites, deux triangles de moins.

Le tableau suivant résume, pour les premières valeurs du nombre de segments, la valeur de la borne supérieure ainsi que celle de la meilleure solution connue (indiquée en gras lorsqu'il s'agit d'une solution réellement maximale).

Nombre de droites 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
Borne supérieure 1 2 5 7 11 15 21 26 33 40 47 55 65 74 85 95 107 119 133
Meilleure solution connue 0 0 1 2 5 7 11 15 21 25[5] 32[6] 38[7] 47[7] 53 65[8] 72 85[9] 93 104 115 130

Dans l'encyclopédie en ligne des suites de nombres entiers, la suite est classée sous le numéro A006066.

Voir aussi[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Références[modifier | modifier le code]

  1. (en) Kobon Fujimura, The Tokyo Puzzles, Frederick Muller Ltd,‎ 1981 (ISBN 978-0584103571)
  2. (en) Martin Gardner, Wheels, Life, and Other Mathematical Amusements, W.H. Freeman & Company,‎ 1983, 170-171 / 178 p. (ISBN 978-0716715894)
  3. (en) David Eppstein, « Triangles and Simplices Kabon Triangles », The Geometry Junkyard (consulté le 19/01/2008)
  4. (en) Johannes Bader, « Kobon Triangles - Proof for Tighter Lower Bound »,‎ 21/12/2007 (consulté le 19/01/2008)
  5. (en) (en) Branko Grünbaum, Convex Polytopes, Springer, coll. « GTM »,‎ 1967 (ISBN 978-0-38740409-7)
  6. (ja) S. Honma, « 三角形の最大数 (nombre maximal de triangles) » (consulté le 19/01/2008)
  7. a et b (ru) Viatcheslav Kabanovitch, « Тре угольника Кобона (Triangles de Kobon) », Шарада (Charade, publication du club de puzzle russe Диоген), vol. 6,‎ 06/1999, p. 1-2 (lire en ligne)
  8. (en) Toshitaka Suzuki, « Kobon Triangle », Solution soumise au site MathWorld,‎ 02/10/2005 (consulté le 19/01/2008)
  9. (en) Johannes Bader, « Kobon Triangles - Perfect Solution with 17 lines »,‎ 11/2007 (consulté le 19/01/2008)