Kobon triangles

Kobon triangles are triangles that are created by drawing multiple lines. The corresponding Kobon triangle problem is the question of how many non-overlapping triangles can be generated at most if you draw straight lines in the plane. The namesake Kobon Fujimura , a Japanese math teacher and puzzle author, published the task in his 1978 book "The Tokyo Puzzle". ${\ displaystyle N (k)}$ ${\ displaystyle k}$

Solutions to the problem result from the consideration of straight lines in the projective plane , whereby only affine triangles are counted.

Kobon number

For up to six straight lines, it is easy to try and find arrangements that create as many triangles as possible. While only a triangle can be formed with three straight lines, there are a maximum of 2, 5 and 7 for four, five and six straight lines.

A triangle can be created from three straight lines.
Two triangles made up of four straight lines
Five triangles made up of five straight lines
Seven triangles made up of six straight lines
Eleven triangles made up of seven straight lines

How many triangles can be generated for any number of straight lines (the so-called Kobon number) is a hitherto unsolved problem of combinatorial geometry , the solution of which is assumed to be very difficult. ${\ displaystyle k}$

Upper bound

The following proof by Saburo Tamura makes it possible to determine an upper bound of the Kobon number for a given . Each of the straight lines intersects the remaining lines at most once. The intersection points form line segments ( fence post problem ), so the figure has a maximum of segments (in the example shown above, segments were created , for example ). Every free-standing triangle now needs exactly three of these line segments, unless it shares one or more edges with another triangle (in the example ). In these cases, however, three straight lines must intersect in one point for every two triangles, which reduces the number of line segments by three - more than the two saved line segments. ${\ displaystyle k}$ ${\ displaystyle k}$ ${\ displaystyle k-1}$ ${\ displaystyle k-1}$ ${\ displaystyle k-2}$ ${\ displaystyle k (k-2)}$ ${\ displaystyle k = 5}$ ${\ displaystyle 15}$ ${\ displaystyle k = 6}$

So every triangle needs (at least) three segments. This is

{\ displaystyle \ lfloor k \ left (k-2 \ right) / 3 \ rfloor}

an upper bound for the maximum number of non-overlapping triangles made of straight lines. ${\ displaystyle k}$

However, the limit is not always reached. A maximum of triangles - one triangle less than the upper bound - can be formed with straight lines . This can be explained with further considerations, from which the narrower upper bound ${\ displaystyle 6}$ ${\ displaystyle 7}$

{\ displaystyle \ lfloor k \ left (k-2 \ right) / 3 \ rfloor - \ chi _ {\ {n | (n \ mod 6) \ in \ {0,2 \} \}} (n)}

by Clément and Bader. denotes the characteristic function . ${\ displaystyle \ chi}$

Recursive procedure

D. Forge and JL Ramirez Alfonsin have shown that there are arrangements for an infinite number of values which reach the upper bound of Tamura. The proof contains a recursive procedure with which for a perfect solution with straight lines - a solution which reaches the maximum number of triangles - further perfect arrangements with straight lines can be calculated. For example, the perfect solutions for etc. can be determined from the solution for 3 lines . ${\ displaystyle k}$ ${\ displaystyle k_ {0}}$ ${\ displaystyle k (k-2) / 3}$ ${\ displaystyle k_ {n + 1} = 2 \ cdot k_ {n} -1}$ ${\ displaystyle k = 3,5,9,17,33,65}$

Well-known solutions

Largest known perfect solution (85 triangles from 17 lines)

Perfect solutions, i.e. Kobon triangles that reach the upper bound, are known for. Except for these , the maximum number of triangles is not known. For and the best known solution contains one triangle less than the upper bound, for and two triangles less. ${\ displaystyle k = 3,4,5,6,7,8,9,13,15,17,29,33,57,65, \ ldots}$ ${\ displaystyle k}$ ${\ displaystyle k = 10}$ ${\ displaystyle 11}$ ${\ displaystyle k = 12.16}$ ${\ displaystyle 18}$

The following listing shows the upper bound as well as the best known solution for various . ${\ displaystyle k}$

k	3	4th	5	6th	7th	8th	9	10	11	12	13	14th	15th	16	17th	18th	19th	20th	21st	...
Upper bound for N ( k )	1	2	5	7th	11	15th	21st	26th	33	40	47	55	65	74	85	95	107	119	133	...
Best known solution	1	2	5	7th	11	15th	21st	25th	32	38	47	53	65	72	85	93	104	115	130	...

The well-known Kobon triangular numbers are printed in bold. They are the sequence A006066 in OEIS .

Web links

Commons : Kobon triangles - collection of images, videos and audio files

Individual evidence

^ Kobon Triangle at Mathworld .

^ ^A ^b Column by Ed Pegg Jr. on Math Games.

↑ ^a ^b Various solutions and evidence for the upper bound ( memento of the original from March 3, 2016 in the Internet Archive ) Info: The archive link was automatically inserted and not yet checked. Please check the original and archive link according to the instructions and then remove this notice. @1@ 2
^ "Straight line arrangements in the real projective plane" , D. Forge and JL Ramirez Alfonsin, Discrete and Computational Geometry, Volume 20, Number 2, Pages 155-161, 1998.
↑ "Matlab Code, which shows the method of D. Forge and JL Ramirez Alfonsin"

[1] Kobon Triangle at Mathworld .

[pegg-2] A ^b Column by Ed Pegg Jr. on Math Games.