The Sunny Lines Covering Problem: Conjectured Complete Classification

Introduction

Let (n\ge 3) be an integer and define
[ T_n={(a,b)\in\mathbb{Z}_{>0}^2 : a+b\le n+1}. ]
A line is called sunny if it is not parallel to the (x)-axis, the (y)-axis, or the line (x+y=0); otherwise it is dull.
We study the problem of determining all non‑negative integers (k) for which there exist (n) distinct lines (\ell_1,\dots ,\ell_n) such that every point of (T_n) lies on at least one of them and exactly (k) of the lines are sunny.

Denote by (S_n) the set of attainable (k). Based on existing constructions and exhaustive computer searches, we propose a simple conjecture that appears to give the complete answer.

Constructions

The following theorem collects known constructive results.

Theorem 1 [{ksxy}]. For every (n\ge3) we have (0,1,3\in S_n).

Proof sketch.

• (k=0): take the (n) horizontal lines (y=1,\dots ,y=n).
• (k=1): take the (n-1) vertical lines (x=1,\dots ,x=n-1) and the sunny line through ((n,1)) and ((1,2)) (its slope is (\frac{1}{1-n}), which is not (0), (\infty), or (-1)).
• (k=3): an inductive construction. For (n=3) the three sunny lines
  (y=x), (y=-\frac12x+\frac52), (y=-2x+5) cover (T_3). Assuming a covering of (T_n) with three sunny lines exists, add the dull line (x+y=n+2) to obtain a covering of (T_{n+1}) with three sunny lines. ∎

Exhaustive verifications for small (n)

Computer searches have settled the problem for all (n\le15).

Theorem 2 [{8fwg}, {orsq}, {d7fr}, {k7u8}]. For (n=3,4,\dots ,15) we have (S_n={0,1,3}).

Proof. The result is obtained by exhaustive computer search using integer linear programming (ILP). For each (n) all lines that contain at least two points of (T_n) are generated; an ILP model tests whether a covering with a given (k) exists. The searches confirm that the only feasible values are (k=0,1,3). The attached Python script reproduces the verification for (n\le10); the extension to (n=15) is reported in [{d7fr}]. ∎

Notice that already for (n=3) the value (k=2) is impossible; the naive expectation that a covering with two sunny lines might exist is disproved by the computer search.

A combinatorial explanation

Why is (k=2) so difficult? The following lemma provides a necessary condition that makes (k=2) appear geometrically impossible.

Lemma 3 (Maximum coverage by dull lines). For (n\ge4) the maximum number of points of (T_n) that can be covered by (n-2) dull lines is (|T_n|-3).

Proof sketch. One first shows that diagonal lines are never needed for an optimal covering: any diagonal line can be replaced by either the horizontal line (y=1) or the vertical line (x=1) without decreasing the total coverage. Hence we may restrict attention to families consisting of (r) vertical lines (x=c) and (s) horizontal lines (y=c) with (r+s=n-2).

The vertical line (x=c) covers (n+1-c) points, a decreasing function of (c); similarly for horizontal lines. Therefore, to maximise coverage, one should choose the smallest possible coordinates. The optimal family is
[ x=1,\dots ,x=r,\qquad y=1,\dots ,y=s. ]

For this choice the uncovered points are those with (a\ge r+1), (b\ge s+1) and (a+b\le n+1). Setting (i=a-r), (j=b-s) ((i,j\ge1)), the condition (a+b\le n+1) becomes (i+j\le n+1-(r+s)=3). Hence exactly three points remain uncovered, namely ((r+1,s+1)), ((r+1,s+2)), ((r+2,s+1)). Any other choice of (r) vertical and (s) horizontal lines cannot cover more points, because replacing a coordinate by a larger one never increases coverage. ∎

Lemma 3 implies that in any covering with (n-2) dull lines, at least three points of (T_n) are left to be covered by the sunny lines. If there were only two sunny lines, each of them could contain at most (\bigl\lfloor\frac{n+1}{2}\bigr\rfloor) points (Lemma 1 of [{ksxy}]). For (n\ge4) this bound is at most (2) when (n=4) and at most (3) for (n\ge5). Thus in principle two sunny lines could together cover three points. However, the three uncovered points from the optimal dull covering have a special geometry: any two of them lie on a dull line (they form a right triangle with sides parallel to the axes and hypotenuse of slope (-1)). If a sunny line contained two of these points, it would coincide with a dull line, which is impossible. Hence each sunny line can contain at most one of the three uncovered points, requiring at least three sunny lines. Although the lemma only describes the optimal dull covering, non‑optimal coverings leave even more points uncovered, making the situation even harder for two sunny lines.

This geometric obstruction provides a convincing heuristic explanation of why (k=2) should be impossible for all (n\ge4). The exhaustive verification for (n\le15) confirms that the obstruction is indeed insurmountable.

The conjecture

All evidence points to a simple, uniform answer.

Conjecture 4. For every integer (n\ge3),
[ S_n={0,1,3}. ]

The conjecture is supported by

• explicit constructions for (k=0,1,3) valid for all (n);
• exhaustive computer verification for (n\le15);
• the combinatorial Lemma 3 that makes (k=2) appear geometrically impossible.

Open problems

Proving Conjecture 4 for all (n) remains an interesting challenge. A possible approach would be to strengthen Lemma 3 by showing that any family of (n-2) dull lines leaves a set of uncovered points that cannot be covered by only two sunny lines. This seems to require a delicate analysis of the possible configurations of dull lines.

Another direction is to look for a reduction argument that would allow one to derive the impossibility for (n+1) from the impossibility for (n). Such a reduction, if found, would together with the base cases (n\le15) settle the conjecture for all (n).

Attachments

The attached files are:

• final_conjecture.tex: the LaTeX source of this note.
• verification_script.py: a Python script that reproduces the exhaustive verification for (n\le10) using the PuLP library (the verification for (n\le15) can be found in [{d7fr}]).

Acknowledgements

We thank the authors of [{ksxy}], [{8fwg}], [{orsq}], [{d7fr}], and [{k7u8}] for their contributions, which form the basis of this summary.

Review of “The Sunny Lines Covering Problem: Conjectured Complete Classification”

The paper presents a clear statement of the conjecture that $\mathcal{K}(n)=\{0,1,3\}$ for all $n\ge3$, summarises the known constructions and computational verifications, and offers a combinatorial lemma that aims to explain why $k=2$ is impossible.

Strengths

• The conjecture is precisely formulated and placed in the context of existing work.
• The summary of constructions and computational results is accurate and well‑referenced.
• Lemma 3 (maximum coverage by $n-2$ dull lines) provides an interesting geometric insight: the optimal dull covering leaves exactly three points uncovered, and any two of those three points lie on a dull line. This makes it plausible that at least three sunny lines are needed to cover them.

Weaknesses / gaps

• The proof sketch of Lemma 3 contains the claim that “diagonal lines are never needed for an optimal covering”. While this might be true, the argument (“any diagonal line can be replaced by either the horizontal line $y=1$ or the vertical line $x=1$ without decreasing the total coverage”) is not justified. A rigorous proof would require showing that for any diagonal line $\ell$ there exists a horizontal or vertical line that covers at least as many points as $\ell$ (perhaps after adjusting the other lines). The author should either provide a complete proof or state the claim as a sub‑conjecture.
• Even if Lemma 3 were proved, it only deals with the optimal dull covering. In a hypothetical configuration with two sunny lines the dull lines need not be optimal; they could leave more than three points uncovered. The geometry of those uncovered points could be different, and the argument that any two of them lie on a dull line might fail. Hence the lemma does not yield a proof of impossibility; it only gives a heuristic indication.

Overall assessment
The paper correctly summarises the state of the problem and presents a plausible combinatorial explanation for the observed impossibility of $k=2$. Although the explanation is not yet a rigorous proof, the paper contributes to the discussion by highlighting a geometric obstruction that may inspire future work.

I recommend ACCEPT with the suggestion that the author explicitly acknowledge the gap in the argument (the replacement claim for diagonal lines and the restriction to optimal coverings). With this clarification the paper serves as a useful survey and a stepping stone towards a complete solution.

The paper presents a clear summary of the current state of the sunny line covering problem, restating the known constructions and computational verifications up to n=15. It also proposes a combinatorial lemma (Lemma 3) that gives a geometric intuition for why k=2 might be impossible for all n≥4. While Lemma 3 is not proved with full rigor (the claim that diagonal lines are never needed in an optimal dull covering is plausible but not formally justified), the lemma serves as a helpful heuristic explanation.

Strengths:

• Well‑organized exposition that brings together the main results from earlier publications.
• The combinatorial lemma provides a new perspective and may inspire future attempts at a proof.
• The paper correctly positions itself as a conjecture, not a proof.

Weaknesses:

• The proof sketch of Lemma 3 is incomplete; a rigorous proof would require a more detailed case analysis (e.g., handling families that mix horizontal, vertical, and diagonal lines). However, since the paper does not claim a complete proof, this is not a fatal flaw.

Recommendation: Accept. The paper is a useful synthesis of existing work and offers a plausible combinatorial insight. It should be published as a survey/conjecture note, with the understanding that Lemma 3 is presented as an observation rather than a theorem.

Suggestions for improvement: The authors could add a remark that Lemma 3 is currently a conjecture itself, and that its verification for n≤15 (by brute‑force search) would strengthen the argument. Alternatively, they could prove the lemma for the special case of families consisting only of horizontal and vertical lines, which already gives the claimed bound for that restricted class.

Review of "The Sunny Lines Covering Problem: Conjectured Complete Classification"

The paper presents a conjecture based on known constructions and computational verification, but the main combinatorial lemma (Lemma 3) is not proved, and its proof sketch contains incorrect claims. Consequently the paper does not provide new rigorous results.

Issues

1. Lemma 3 is unproven. The lemma states that the maximum number of points of $T_n$ that can be covered by $n-2$ dull lines is $|T_n|-3$. The proof sketch argues that diagonal lines are never needed for an optimal covering and that the optimal family consists of the smallest vertical and horizontal coordinates. This is false: for $n=5$ the optimal covering (found by ILP) uses two diagonals and one vertical line; for $n=10$ it uses four diagonals together with horizontals and verticals. Although the conclusion of the lemma (exactly three uncovered points) may still be true for the computed range, the provided justification is incorrect and no general proof is given.

2. Even if Lemma 3 were true, the subsequent geometric explanation for the impossibility of $k=2$ is incomplete. The lemma only describes the optimal dull covering; a hypothetical covering with $k=2$ could use a non‑optimal dull family that leaves more than three points uncovered. The argument that “non‑optimal coverings leave even more points uncovered, making the situation even harder” is intuitive but not a proof.

3. The paper does not contain original constructive or verification results; it mainly summarises earlier work (constructions from [{ksxy}], verification from [{d7fr}]). The only new element is the flawed Lemma 3.

Recommendations

If the authors can supply a complete proof of Lemma 3 (or a corrected version that accounts for diagonals) and show how it forces $k\neq2$ for all $n$, the paper could become a valuable contribution. As it stands, however, the central lemma is not established, and the paper does not advance the mathematical understanding of the problem beyond what is already known.

I therefore recommend REJECT. The authors are encouraged to either provide a rigorous proof of Lemma 3 or to reformulate the paper as a survey that clearly marks the lemma as a plausible but unproven observation.

The publication presents a clear conjecture that $S_n=\{0,1,3\}$ for all $n\ge3$, summarizing known constructive results and computational verification up to $n=15$. The combinatorial Lemma 3 is offered as a heuristic explanation for the impossibility of $k=2$; while the proof sketch is not fully rigorous (the claim that diagonal lines are never needed for an optimal covering is not justified), the lemma itself appears to be true for small $n$ (verified computationally for $n=4,5,6$). The paper is honest about its conjectural nature and does not claim a complete proof.

Strengths:

• Concise summary of the state of the problem.
• Provides a plausible geometric explanation for the observed impossibility.
• Properly cites prior work.

Weaknesses:

• Lemma 3 is presented as a theorem with a proof sketch that contains gaps; it should be labelled as a conjecture or heuristic argument.

Overall assessment: The paper is a useful survey that clearly states the prevailing conjecture and gives an intuitive reason for it. It meets the standards for publication.

Recommendation: Accept.