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.
Known upper bounds Saburo Tamura proved that the number of nonoverlapping triangles realizable by k {\displaystyle k} lines is at most ⌊ k ( k − 2 ) / 3 ⌋ {\displaystyle \lfloor k(k-2)/3\rfloor } . G. Clément and J. Bader proved more strongly that this bound cannot be achieved when k {\displaystyle k} is congruent to 0 or 2 modulo 6. 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:
{ 1 3 k ( k − 2 ) when k ≡ 3 , 5 ( mod 6 ) ; 1 3 ( k + 1 ) ( k − 3 ) when k ≡ 0 , 2 ( mod 6 ) ; 1 3 ( k 2 − 2 k − 2 ) when k ≡ 1 , 4 ( mod 6 ) . {\displaystyle {\begin{cases}{\frac {1}{3}}k(k-2)&{\text{when }}k\equiv 3,5{\pmod {6}};\\{\frac {1}{3}}(k+1)(k-3)&{\text{when }}k\equiv 0,2{\pmod {6}};\\{\frac {1}{3}}(k^{2}-2k-2)&{\text{when }}k\equiv 1,4{\pmod {6}}.\end{cases}}}
Solutions yielding this number of triangles are known when k {\displaystyle k} is 3, 4, 5, 6, 7, 8, 9, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31 or 33. For k = 10, 11 and 12, the best solutions known reach a number of triangles one less than this upper bound. Furthermore, the upper bound for even values k {\displaystyle k} can be improved: ⌊ k ( k − 7 / 3 ) / 3 ⌋ {\displaystyle \lfloor k(k-7/3)/3\rfloor } . This bound can be reached for 10, 12 and 16. The upper bound for k = 11 has long been thought not to be reachable, which was shown to be correct in 2025 by Pavlo Savchuk with the use of a SAT solver.
Known constructions The following bounds are known:
In the projective plane
The version of the problem in the projective plane allows more triangles. In this version, it is convenient to include the line at infinity as one of the given lines, after which the triangles appear in three forms:
… excerpt ends here. Continue reading the full article.
