Kobon triangle problem

From Wikipedia, the free encyclopedia

The Kobon triangle problem is an unsolved problem in combinatorial geometry first stated by Kobon Fujimura. The problem asks for the largest number N(k) of nonoverlapping triangles that can be produced by k straight line segments.

Saburo Tamura proved that the largest integer not exceeding k(k − 2)/3 provides an upper bound on the maximal number of nonoverlapping triangles realizable by k lines.^[1] This sequence is captured in the On-Line Encyclopedia of Integer Sequences as A032765. In 2007, a tighter upper bound was found by Johannes Bader and Gilles Clément, by proving that Tamura's upper bound couldn't be reached for any k congruent to 0 or 2 (mod 6).^[2] The maximum number of triangles is therefore one less than Tamura's bound in these cases. Perfect solutions (Kobon triangle solutions yielding the maximum number of triangles) are known for k = 3, 4, 5, 6, 7, 8, 9, 13, 15 and 17.^[3] For other k-values the Kobon triangle solution numbers are not known. For k = 10, 11 and 12, the best solutions known reach a number of triangles one less than the upper bound.

k	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	...
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	...
Clément and Bader's upper bound	1	2	5	7	11	15	21	26	33	39	47	55	65	74	85	95	107	119	133	...
best known solution	1	2	5	7	11	15	21	25	32	38	47	53	65	72	85[4]	93	104	115	130	...

The known Kobon triangle solution numbers are captured in the On-Line Encyclopedia of Integer Sequences as A006066.

[edit] References

1. ^ Eric W. Weisstein, Kobon Triangle at MathWorld.
2. ^ G. Clément and J. Bader. Tighter Upper Bound for the Number of Kobon Triangles. Draft Version, 2007.
3. ^ Ed Pegg Jr. on Math Games
4. ^ Maximal solution for k = 17