Kobon triangle problem

Kobon triangles are triangles that arise from drawing multiple lines. The corresponding Kobon triangles problem is the question of how many non-overlapping triangles N ( k) can be generated at a maximum when to draw k lines in the plane. The namesake Kobon Fujimura, a Japanese math teacher and mystery writer, published the terms of reference in his 1978 book " The Tokyo Puzzle".

Solutions for the problem arising from the consideration of lines in the projective plane, but only affine triangles are counted.

Kobon number

For up to six lines, it is easy to find by trial arrangements in which as many triangles. While only a triangle with three straight lines can be formed, there are four, five and six straight lines more than 2, 5, and 7

Two triangles of four straight

Five triangles of five straight

Seven triangles of six straight

Eleven triangles of seven straight

How many triangles can be generated k for any number of straight lines ( the so-called Kobon number), is an unsolved problem in combinatorial geometry, the solution of which is thought to be very difficult.

The following proof of Saburo Tamura makes it possible to determine an upper bound on the number Kobon for a given k. Each of the k lines intersecting the remaining k-1 lines at most once. The k -1 points of intersection form k-2 line segments ( fence post problem), thereby having the figure of a maximum of k * (k -2) segments ( in the example shown above, for k = 5, for example, 15 segments originated ). Each free-standing triangle now requires exactly three of these line segments, except it shares one or more edges with another triangle (eg in the example k = 6). In these cases, however, must intersect each for two triangles, three straight lines in a point, which is the number of line segments is reduced to three - two more than the saved line segments.

Thus, each triangle requires (at least) three segments. This is

An upper bound on the maximum number of non- overlapping triangles of k lines.

The barrier is not always achieved. Thus, with 6 lines max 7 triangles - a triangle is less than the upper bound - form. This can be explained with further considerations from which the tighter upper bound

Seen by Clément and Bader. denotes the characteristic function.

Recursive method

D. Forge and JL Ramirez Alfonsin have proven that there are arrangements for infinitely many values ​​that reach the upper bound of Tamura. The proof involves a recursive procedure for a perfect solution with straight lines with the - a solution that reached the maximum number of triangles - another perfect arrangements can be calculated using straight line. For example, the perfect solution can be determined from the solution for etc. for 3 straight lines.

Known solutions

Perfect solution, so Kobon triangles, which reach the upper limit, are known for k = 3, 4, 5, 6, 7, 8, 9, 13, 15, 17, 29, 33, 57, 65, ... except for that k is the maximum number of triangles unknown. For k = 10 and 11, the best known solution contains a delta less than the upper bound, for k = 12, 16 and 18, two triangles less.

The following list shows the upper bound and the best known solution for different k

The known Kobon - triangular numbers are shown in bold. They are the result of A006066 in OEIS.