Kobon triangle problem

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

k

lines?

(more unsolved problems in mathematics)

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 $k$ lines is at most $\lfloor k(k-2)/3\rfloor$ . G. Clément and J. Bader proved more strongly that this bound cannot be achieved when $k$ 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: ${\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$ is 3, 4, 5, 6, 7, 8, 9, 13, 15, 17, 19, 21, 25 or 29.^[3] ^[4] ^[5] 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$ can be improved: $\lfloor k(k-7/3)/3\rfloor$ .^[4] This bound can be reached for 10, 12 and 16.^[3]

Known constructions

The following bounds are known:

k	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	...	25	...	29	OEIS
Tamura's upper bound on N(k)	1	2	5	8	11	16	21	26	33	40	47	56	65	74	85	96	107	120	133	...	191	...	261	A032765
Improvements on Tamura's ^[2]^[4]	1	2	5	7	11	15	21	25	33	38	47	54	65	72	85	94	107	117	133	...	191	...	261	-
best known solution	1	2	5	7	11	15	21	25	32	38	47	53	65	72	85	93	107	115	133	...	191	...	261	A006066

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:

ordinary triangles among the remaining lines, bounded by three finite line segments,
triangles bounded by two rays that meet at a common apex and by a segment of the line at infinity, and
triangles bounded by a finite line segment and by two parallel rays that meet at a vertex on the line at infinity.

For instance, an arrangement of five finite lines forming a pentagram, together with a sixth line at infinity, has ten triangles: five in the pentagram, and five more bounded by pairs of rays.

D. Forge and J. L. Ramirez Alfonsin provided a method for going from an arrangement in the projective plane with $k>3$ lines and ${\tfrac {1}{3}}k(k-1)$ triangles (the maximum possible for $k>3$ ), with certain additional properties, to another solution with $K=2k-1$ lines and ${\tfrac {1}{3}}K(K-1)$ triangles (again maximum), with the same additional properties. As they observe, it is possible to start this method with the projective arrangement of six lines and ten triangles described above, producing optimal projective arrangements whose numbers of lines are