Kobon triangle problem: close the gap on N(k), the max non-overlapping triangles from k lines
Statement
For an arrangement of $k$ lines in the plane, let $N(k)$ be the maximum number of non-overlapping (interior-disjoint) triangles whose three sides all lie on lines of the arrangement. Determine $N(k)$, or improve the best known constructions/bounds, for values of $k$ where it is unknown. Provide an explicit line arrangement (coordinates) realizing a record triangle count as a fully checkable certificate.
Acceptance. ADVANCES: for some $k$ where $N(k)$ is unknown, exhibit an explicit arrangement of $k$ lines (line equations or point coordinates) achieving strictly more non-overlapping triangles than the best previously recorded count — verified by a program that (a) confirms the lines are in general-enough position and (b) counts interior-disjoint triangles bounded by the lines. FULLY RESOLVES (for a given k): a construction meeting the Tamura / Bader–Clément upper bound together with a proof no arrangement does better, pinning $N(k)$ exactly. Deliver the arrangement + the triangle-counting/verification script and the count achieved.
Background
Posed by Kobon Fujimura; a classic unsolved problem in combinatorial geometry (see Croft–Falconer–Guy, 'Unsolved Problems in Geometry'; OEIS A006066). Upper bound: Tamura showed $N(k)\le \lfloor k(k-2)/3\rfloor$; Bader–Clément (2007) tightened this to $\lfloor k(k-2)/3\rfloor - 1$ whenever $k\equiv 0$ or $2 \pmod 6$. Exact optimal values are proven only for $k = 3,4,5,6,7,8,9,13,15,17$ and, more recently, $k=23,27$ (Savchuk 2025); for many other $k$ only a best-known construction is recorded, often below the upper bound (e.g. constructions for $k=10$ reaching 25 vs upper bound 26; $k=11$ reaching 32 vs 33; $k=12$; etc.). So for infinitely many $k$ it is open whether the upper bound is attainable and what $N(k)$ actually equals. The attacker's tool: this is a pure configuration-search problem — an arrangement of $k$ lines is a finite set of $2k$ real parameters, and the number of non-overlapping triangles is exactly computable from the arrangement, so candidate constructions are trivially machine-verifiable. Attack routes: symbolic/numeric optimization over line coefficients, symmetry-restricted search, SAT/ILP encodings of the triangle-selection, and local perturbation from near-optimal arrangements.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Kobon triangle problem (Wikipedia) | website |
| REF-02 | OEIS A006066 — Kobon triangle numbers | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.