Kobon triangles generated with 3, 4 and 5 straight line segments.
Unsolved problem in mathematics:

How many non-overlapping triangles can be formed in an arrangement of lines?

The Kobon triangle problem is an unsolved problem in combinatorial geometry first stated by Kobon Fujimura (1903-1983). The problem asks for the largest number N(k) of nonoverlapping triangles whose sides lie on an arrangement of k lines. Variations of the problem consider the projective plane rather than the Euclidean plane, and require that the triangles not be crossed by any other lines of the arrangement.[1]

Known upper bounds

Saburo Tamura proved that the number of nonoverlapping triangles realizable by lines is at most . G. Clément and J. Bader proved more strongly that this bound cannot be achieved when is congruent to 0 or 2 (mod 6).[2] The maximum number of triangles is therefore at most one less in these cases. The same bounds can be equivalently stated, without use of the floor function, as:

Solutions yielding this number of triangles are known when is 3, 4, 5, 6, 7, 8, 9, 13, 15 or 17.[3] For k = 10, 11 and 12, the best solutions known reach a number of triangles one less than the upper bound.

Known constructions

Given an optimal solution with k0 > 3 lines, other Kobon triangle solution numbers can be found for all ki-values where

by using the procedure by D. Forge and J. L. Ramirez Alfonsin.[1] For example, the solution for k0 = 5 leads to the maximal number of nonoverlapping triangles for k = 5, 9, 17, 33, 65, ....

k3456789101112131415161718192021OEIS
Tamura's upper bound on N(k)1258111621263340475665748596107120133A032765
Clément and Bader's upper bound1257111521263339475565748595107119133-
best known solution1257111521253238475365728593104115130A006066

Examples

See also

References

  1. 1 2 Forge, D.; Ramírez Alfonsín, J. L. (1998), "Straight line arrangements in the real projective plane", Discrete and Computational Geometry, 20 (2): 155–161, doi:10.1007/PL00009373.
  2. "G. Clément and J. Bader. Tighter Upper Bound for the Number of Kobon Triangles. Draft Version, 2007" (PDF). Archived from the original (PDF) on 2017-11-11. Retrieved 2008-03-03.
  3. Ed Pegg Jr. on Math Games
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.