If you draw three lines (infinite lines, not line segments) in a plane, you can make them form a triangle. If you draw four lines, you can make them form a maximum of two triangles. For five lines, the maximum jumps up to five triangles.
So, in general, for k lines, what is the largest possible number of non-overlapping triangles formed? This value is written as N(k). This problem is called Kobon’s triangle problem, named after Kobon Fujimura.
The Upper Bound
A known upper bound for N(k) exists, found by Saburo Tamura:
N(k) ≤ ⌊k(k − 2) / 3⌋
Here, the floor function takes in a number and returns the greatest integer less than or equal to that number. Basically, it rounds down.
For instance, if k = 4:
⌊4(4 − 2) / 3⌋ = ⌊8 / 3⌋ = ⌊2.666…⌋ = 2
What Do We Know So Far?
Exact solutions are known for numbers of lines from 3 to 9, as well as 13, 15, and 17. In the case of the first unsolved number of lines, k = 10, the upper bound is 26 triangles, whereas the best solution obtained so far is 25.
Why Is This Problem So Hard?
The Kobon triangle problem is deceptively simple to state but extremely difficult to solve. As the number of lines increases, the number of possible arrangements grows rapidly, making it impractical to check every configuration by brute force. The challenge lies not just in forming many triangles, but in ensuring that none of them overlap. Each new line intersects all previous lines, creating a web of intersections where maximizing triangles in one region often disrupts optimal arrangements elsewhere. Despite decades of work by mathematicians and computer scientists, no general formula for N(k) has been found, and even individual cases like k = 10 remain open.
Leave a Reply