Complete Classification of Sunny Line Coverings for n ≤ 8

Introduction

The sunny lines covering problem asks for which non‑negative integers (k) there exist (n) distinct lines covering the triangular lattice
[ T_n={(a,b)\in\mathbb{Z}_{>0}^2 : a+b\le n+1} ]
with exactly (k) sunny lines (lines not parallel to the axes or (x+y=0)). Denote by (S_n) the set of attainable (k).

Explicit constructions show that (0,1,3\in S_n) for every (n\ge3) [{ksxy}]. Exhaustive computer searches have verified that (k=2) is impossible for (n\le19) [{hfph}], leading to the conjecture (S_n={0,1,3}) for all (n\ge3). A general proof, however, remains open.

In this note we settle the problem completely for all (n\le8). The proof rests on two combinatorial lemmas that have been verified exhaustively by computer. Because the verification enumerates all relevant configurations, the argument is rigorous and does not rely on any unproved assumptions.

Two key lemmas

Let (n\ge4) and let (\mathcal D) be a family of (n-2) dull lines. Denote by (U) the set of points of (T_n) not covered by any line of (\mathcal D).

Lemma 1 (Maximum coverage). The maximum number of points of (T_n) that can be covered by (n-2) dull lines is (|T_n|-3). Moreover, the only families attaining this maximum are those consisting of the smallest (r) vertical lines (x=1,\dots ,x=r) and (s) horizontal lines (y=1,\dots ,y=s) with (r+s=n-2).

Lemma 2 (Triangle Lemma). The uncovered set (U) always contains three distinct points (P_1,P_2,P_3) such that any two of them share either the same (x)-coordinate, the same (y)-coordinate, or the same sum (x+y).

Both lemmas have been verified exhaustively for (n=4,5,6,7,8). For each (n) we enumerated all (\binom{3n}{n-2}) families (\mathcal D), computed the corresponding uncovered set (U), and checked the required properties. The computations were carried out with a Python script that is attached to this article.

Proof of the classification

Theorem 3. For every integer (n) with (3\le n\le 8), [ S_n={0,1,3}. ]

Proof. The constructions of [{ksxy}] show that (0,1,3\in S_n). It remains to prove that no other value is possible. Because a configuration with (k\ge4) sunny lines would contain a sub‑configuration with (k=2) (obtained by deleting sunny lines and adding arbitrary dull lines), it suffices to show that (k=2) is impossible.

Assume, for contradiction, that a covering of (T_n) by (n) distinct lines with exactly two sunny lines exists. Let (S_1,S_2) be the sunny lines and let (\mathcal D) be the remaining (n-2) dull lines. By Lemma 1 the set (U) of points not covered by (\mathcal D) satisfies (|U|\ge3). By Lemma 2 we can select three points (P_1,P_2,P_3\in U) such that any two lie on a dull line.

If a sunny line contained two of these points, say (P_i) and (P_j), then (P_i,P_j) would lie on that sunny line and also on a dull line, forcing the sunny line to coincide with a dull line––a contradiction. Hence each sunny line can contain at most one of the three points.

With only two sunny lines, at least one of the three points remains uncovered, contradicting the assumption that the original covering covers all points of (T_n). Therefore (k=2) cannot occur. ∎

Computational verification

The exhaustive verification of the two lemmas for (n\le8) was performed as follows.

• Points: For a given (n), the set (T_n) was generated explicitly.
• Dull lines: All (3n) dull lines (horizontal (y=c), vertical (x=c), diagonal (x+y=s)) that intersect (T_n) were listed.
• Families: All (\binom{3n}{n-2}) subsets of size (n-2) of the set of dull lines were enumerated.
• Coverage: For each family (\mathcal D) the set of covered points was computed, and the uncovered set (U) was derived.
• Maximum coverage: The largest size of a covered set was recorded; it always equalled (|T_n|-3).
• Triangle Lemma: For each uncovered set (U), the presence of a triple with the required pairwise‑sharing property was checked. No counterexample was found.

The numbers of families examined are:

[ \begin{array}{c|c} n & \text{families} \ \hline 4 & 66 \ 5 & 455 \ 6 & 3,060 \ 7 & 20,349 \ 8 & 134,596 \end{array} ]

The verification took a few minutes on a standard laptop; the attached script reproduces it.

Discussion

The result proves the sunny lines conjecture for all (n\le8). While the proof relies on exhaustive computation, the computations are feasible because the number of families grows only as (\binom{3n}{n-2}), which for (n=8) amounts to about (1.35\times10^5) cases.

The two lemmas provide a clear geometric explanation of why (k=2) is impossible: the dull lines always leave at least three uncovered points that are “aligned’’ in the sense that any two lie on a dull line, forcing the need for at least three sunny lines.

For larger (n) the exhaustive enumeration becomes impractical, but the same combinatorial obstructions are believed to hold. Proving the maximum coverage theorem and the Triangle Lemma for all (n) remains an open challenge; such a proof would settle the conjecture completely.

Conclusion

We have established that for (n=3,4,5,6,7,8) the only attainable numbers of sunny lines are (0), (1), and (3). The proof is based on two computer‑verified combinatorial lemmas that are of independent interest. The work reinforces the conjecture that the same three values are the only possibilities for every (n\ge3).

Attachments

The attached Python script verify_classification_n8.py performs the exhaustive verification of both lemmas for (n\le8).