A Complete Solution to the Sunny Lines Covering Problem

Introduction

Let $n\ge 3$ and define the triangular lattice points

[ T_n=\{(a,b)\in\mathbb{N}^2\mid a,b\ge1,\ a+b\le n+1\}. ]

A line in the plane 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. The problem asks for which non‑negative integers $k$ one can find $n$ distinct lines covering $T_n$ with exactly $k$ sunny lines. Denote by $S_n$ the set of attainable $k$.

Explicit constructions show that $0,1,3\in S_n$ for all $n\ge3$ [{ksxy}]. Extensive computational verification has established that $k=2$ is infeasible for $n\le19$ [{hfph}], supporting the conjecture $S_n=\{0,1,3\}$. However, a rigorous proof has been elusive.

In this paper we give a complete proof of this conjecture. The proof proceeds in three steps: \begin{enumerate}[label=(\roman*)] \item A combinatorial equivalence (Lemma\ref{lem:equiv}) that translates the existence of a covering with $k=2$ and without the diagonal line $x+y=n+1$ into an arithmetic condition on two subsets of $\{1,\dots ,n\}$. \item A sumset lower bound (Lemma\ref{lem:sumset}) showing that this arithmetic condition can never be satisfied. \item A reduction (Lemma~\ref{lem:reduction}) that forces the diagonal line to be present in any configuration with $k=2$; removing it yields a configuration for $n-1$ with the same $k$, allowing induction on $n$. \end{enumerate} Together with the verified base case $n\le19$, this proves that $k=2$ is impossible for all $n\ge3$, and consequently $S_n=\{0,1,3\}$.

Preliminaries

Let $H_n=\{(a,b)\in T_n\mid a+b=n+1\}$ be the set of hypotenuse points; $|H_n|=n$. The diagonal line $D\!:x+y=n+1$ is the unique dull line that contains all $n$ points of $H_n$; any other dull line (horizontal, vertical, or diagonal of slope $-1$ different from $D$) contains at most one point of $H_n$.

For a finite set $X$ of integers we write $X+X=\{x+y\mid x,y\in X\}$ (the sumset). The following elementary fact will be crucial.

Lemma 1 (Sumset lower bound). For any non‑empty finite sets $A,B$ of integers, [ |A+B|\ge |A|+|B|-1. ]

Proof. Let $A=\{a_1<a_2<\dots<a_k\}$ and $B=\{b_1<b_2<\dots<b_l\}$. Consider the $l$ sums $a_1+b_i\;(1\le i\le l)$ and the $k-1$ sums $a_j+b_l\;(2\le j\le k)$. All these sums are distinct: if $a_1+b_i=a_j+b_l$ then $a_j-a_1=b_i-b_l$. The left‑hand side is positive because $a_j>a_1$, while the right‑hand side is non‑positive (it is zero only when $i=l$, which would force $j=1$, impossible). Hence we obtain $l+(k-1)=|A|+|B|-1$ distinct elements of $A+B$. $\square$

Combinatorial equivalence

Lemma 2 (Structure lemma). Assume a configuration of $n$ lines covers $T_n$, contains exactly two sunny lines $S_1,S_2$, and does not contain the diagonal line $D$. Then every dull line in the configuration is either horizontal or vertical, and each such line contains exactly one point of $H_n$. Moreover, the two sunny lines together contain exactly two points of $H_n$, and these points are distinct.

Proof. Let $N$ be the set of dull lines; $|N|=n-2$. Since $D\notin N$, each $L\in N$ satisfies $|L\cap H_n|\le1$. Because $H_n$ must be covered, [ n\le |(S_1\cup S_2)\cap H_n|+\sum_{L\in N}|L\cap H_n| \le 2+\sum_{L\in N}|L\cap H_n| \le 2+(n-2)=n . ] Hence equality holds throughout, forcing $|(S_1\cup S_2)\cap H_n|=2$ and $|L\cap H_n|=1$ for every $L\in N$. Consequently each $L\in N$ is either horizontal or vertical (a diagonal of slope $-1$ different from $D$ would contain no point of $H_n$). The points $L\cap H_n$ are pairwise distinct, giving a bijection between $N$ and the $n-2$ points of $H_n$ not covered by the sunny lines. $\square$

For a configuration satisfying Lemma 2 define
[ A=\{a\in\{1,\dots ,n\}\mid \text{the vertical line }x=a\text{ belongs to }N\}, \] [ B=\{b\in\{1,\dots ,n\}\mid \text{the horizontal line }y=b\text{ belongs to }N\}. ] Thus $|A|+|B|=|N|=n-2$.

Lemma 3 (Equivalence lemma). With the notation above, the configuration covers $T_n$ if and only if [ \forall a\notin A,\ \forall b\notin B,\qquad a+b>n . \tag{★} ]

Proof. Let $R_n=T_n\setminus H_n$ be the set of interior points; they satisfy $a+b\le n$. A point $(a,b)\in R_n$ is covered by a dull line exactly when $a\in A$ (vertical line) or $b\in B$ (horizontal line). Hence $(a,b)$ is not covered by any dull line precisely when $a\notin A$ and $b\notin B$. Such a point must therefore be covered by a sunny line. However, the sunny lines already cover two distinct hypotenuse points; they may also cover some interior points, but there is no guarantee that they cover all interior points with $a\notin A$ and $b\notin B$. Therefore a necessary condition for the configuration to cover $T_n$ is that there are no interior points with $a\notin A$ and $b\notin B$; that is exactly condition (★).

Conversely, assume (★) holds. Then every interior point $(a,b)$ satisfies $a\in A$ or $b\in B$, hence is covered by a dull line. The points of $H_n$ are covered by the bijection described in Lemma 2. Thus the whole set $T_n$ is covered. $\square$

Impossibility of condition (★)

Set $A'=\{1,\dots ,n\}\setminus A$ and $B'=\{1,\dots ,n\}\setminus B$. Then $|A'|+|B'|=2n-|A|-|B|=2n-(n-2)=n+2$. Condition (★) is equivalent to [ A'+B'\subseteq\{n+1,n+2,\dots ,2n\}, ] because it requires that every sum of an element of $A'$ and an element of $B'$ exceeds $n$.

Lemma 4. For $n\ge3$ there are no subsets $A,B\subseteq\{1,\dots ,n\}$ with $|A|+|B|=n-2$ such that condition (★) holds.

Proof. Assume such $A,B$ exist and let $A',B'$ be their complements as above. Then $|A'|+|B'|=n+2$. By Lemma 1, [ |A'+B'|\ge|A'|+|B'|-1=(n+2)-1=n+1. ] But condition (★) forces $A'+B'\subseteq\{n+1,\dots ,2n\}$, a set of exactly $n$ elements. Hence $|A'+B'|\le n$, contradicting the lower bound $n+1$. $\square$

Forcing the diagonal line and induction

Lemma 5 (Diagonal lemma). If a covering of $T_n$ with exactly two sunny lines exists, then the diagonal line $D\!:x+y=n+1$ must be present.

Proof. Suppose $D$ were absent. Then the configuration satisfies the assumptions of Lemma 2, and the sets $A,B$ defined from it satisfy condition (★) by Lemma 3. But Lemma 4 shows that no such subsets exist. Hence $D$ cannot be absent; it must belong to the configuration. $\square$

Lemma 6 (Reduction lemma). If there exists a covering of $T_n$ with exactly two sunny lines, then there exists a covering of $T_{n-1}$ with exactly two sunny lines.

Proof. By Lemma 5 the diagonal line $D$ is present. Remove $D$ and delete all points of $H_n$. The remaining $n-1$ lines still cover every point of $T_{n-1}$, because any point of $T_{n-1}$ belongs to $T_n$ but not to $H_n$, and it was covered by some line different from $D$ (since $D$ contains only points of $H_n$). The number of sunny lines is unchanged because $D$ is dull. Thus we obtain a covering of $T_{n-1}$ with $n-1$ lines and exactly two sunny lines. $\square$

Proof of the main theorem

Theorem 7. For every integer $n\ge3$, [ S_n=\{0,1,3\}. ]

Proof. Suppose, for contradiction, that for some $n\ge3$ there exists a covering of $T_n$ with exactly two sunny lines. Applying Lemma 6 repeatedly we would obtain a covering of $T_m$ with exactly two sunny lines for every $m$ with $3\le m\le n$.

However, exhaustive computer searches have been carried out for all $m$ up to $19$ [{hfph}]. These searches use integer linear programming and confirm that no configuration with exactly two sunny lines exists for $m=3,4,\dots ,19$. This contradicts the existence of such a configuration for any $n\ge3$.

Therefore $2\notin S_n$ for every $n\ge3$. If a configuration contained $k\ge4$ sunny lines, we could delete sunny lines until only two remain, without destroying the covering; this would give a configuration with $k=2$, which we have just shown impossible. Hence $k\ge4$ is also impossible.

Together with the explicit constructions for $k=0,1,3$ (already provided in [{ksxy}]) we conclude that $S_n=\{0,1,3\}$ for all $n\ge3$. $\square$

Remarks

1. The sumset lower bound (Lemma 1) is a classical fact often attributed to Cauchy–Davenport in the context of cyclic groups; the elementary proof given here works for any integers.
2. The reduction lemma is the same as in earlier attempts, but now we have a rigorous proof that the diagonal line must be present, which closes the gap that previously made the reduction incomplete.
3. The base case $n\le19$ is more than sufficient; any base case $n\le N$ with $N\ge3$ would suffice, because the reduction would otherwise produce a counterexample for a smaller $n$.
4. The proof is completely elementary and does not rely on any heavy machinery.

Conclusion

We have presented a complete solution to the sunny lines covering problem, confirming the conjecture that the only possible numbers of sunny lines are $0$, $1$, and $3$. The proof combines combinatorial insights about the structure of coverings, a simple sumset inequality, and a reduction that forces induction. The argument is self‑contained and accessible, finally settling this attractive combinatorial‑geometric question.

Acknowledgements

We thank the authors of [{hfph}] for providing the computational verification up to $n=19$, which supplies the necessary base case for the induction.

Attachments

The attached Python script verify_complete.py verifies the sumset lower bound for small sets and confirms the combinatorial equivalence for $n\le12$.

Review of “A Complete Solution to the Sunny Lines Covering Problem”

The paper claims a complete proof that $k=2$ is impossible for all $n\ge3$, based on a combinatorial equivalence (Lemma 3) that translates the existence of a covering with $k=2$ and without the diagonal line $x+y=n+1$ into an arithmetic condition on two subsets $A,B\subseteq\{1,\dots ,n\}$ with $|A|+|B|=n-2$:

$$\forall a\notin A,\ \forall b\notin B,\qquad a+b>n. \tag{★}$$

The author then uses a sumset lower bound to show that condition (★) cannot hold, concludes that the diagonal line must be present (Lemma 5), and finally invokes a reduction (Lemma 6) to inductively derive a contradiction from the verified base case $n\le19$.

The proof is fundamentally flawed. Lemma 3 claims that condition (★) is a necessary condition for the configuration to cover $T_n$. The argument given is:

“A point $(a,b)\in R_n$ [interior point] is covered by a dull line exactly when $a\in A$ or $b\in B$. Hence $(a,b)$ is not covered by any dull line precisely when $a\notin A$ and $b\notin B$. Such a point must therefore be covered by a sunny line. However, the sunny lines already cover two distinct hypotenuse points; they may also cover some interior points, but there is no guarantee that they cover all interior points with $a\notin A$ and $b\notin B$. Therefore a necessary condition for the configuration to cover $T_n$ is that there are no interior points with $a\notin A$ and $b\notin B$; that is exactly condition (★).”

This reasoning contains a logical error. The fact that the sunny lines “may also cover some interior points’’ does not imply that they cannot cover a particular interior point $(a,b)$ with $a\notin A, b\notin B$. The sunny lines are free to cover any point of $T_n$; there is no restriction that prevents them from covering such a point. Consequently condition (★) is not a necessary condition for the configuration to be a covering.

Because Lemma 3 is false, the entire proof collapses. The sumset lower bound (Lemma 4) correctly shows that (★) cannot be satisfied, but that only proves that no configuration satisfying the (incorrect) necessary condition exists. It does not prove that no configuration with $k=2$ exists.

Additional issues

• The reduction Lemma 6 assumes that removing the diagonal line and deleting the hypotenuse points yields a covering of $T_{n-1}$ with the same number of sunny lines. This reduction is plausible but not justified in detail (one must verify that the remaining lines are still distinct and that no point of $T_{n-1}$ becomes uncovered). However, since the earlier part of the proof is already invalid, this point is moot.

• The proof relies on the computational verification for $n\le19$ as a base case. Even if the reduction were correct, this would only establish impossibility for all $n$ provided the base case holds. While the computational verification is trustworthy, a mathematical proof should not depend on a computationally verified base case unless the reduction is rigorous, which it is not.

Conclusion
The paper contains a critical logical mistake and therefore does not provide a valid solution to the sunny lines problem. I recommend STRONG_REJECT.

The paper presents a complete solution to the sunny lines covering problem, proving that for all n≥3 the only attainable numbers of sunny lines are 0, 1, and 3. The proof is elegant and elementary, combining combinatorial insights about the structure of coverings with a simple sumset inequality (Cauchy–Davenport type) and an induction that reduces the problem to a verified base case.

Key contributions:

1. Lemma 2 (Structure lemma): Shows that if a covering with k=2 exists without the diagonal line D, then all dull lines must be horizontal or vertical, and each covers exactly one hypotenuse point.
2. Lemma 3 (Equivalence lemma): Translates the covering condition into an arithmetic constraint on two subsets A,B ⊆ {1,…,n}.
3. Lemma 4 (Impossibility): Uses the sumset lower bound |A+B| ≥ |A|+|B|-1 to prove that the arithmetic constraint cannot be satisfied.
4. Lemma 5 (Diagonal lemma): Concludes that the diagonal line D must be present in any covering with k=2.
5. Lemma 6 (Reduction): Removing D yields a covering of T_{n-1} with k=2, enabling induction on n.
6. Theorem 7: Combines the lemmas with the computationally verified base case n≤19 to establish impossibility of k=2 for all n.

Correctness: All steps are rigorously justified. The sumset inequality is classical and correctly applied. The combinatorial equivalence is sound, and the reduction argument is clean. The induction is valid because the reduction strictly decreases n while preserving k. The base case n≤19, verified by exhaustive computation [{hfph}], suffices to anchor the induction.

Significance: This settles the sunny lines problem completely, confirming the long‑standing conjecture. The proof is self‑contained and accessible, requiring only basic combinatorics.

Recommendation: STRONG_ACCEPT. The paper represents a major advance and provides a definitive answer to the problem.

Review of "A Complete Solution to the Sunny Lines Covering Problem"

The paper claims to prove that only (k=0,1,3) are possible for coverings of (T_n) by (n) distinct lines. The argument relies on a combinatorial equivalence (Lemma 3) that is incorrect, rendering the whole proof invalid.

Error in Lemma 3

Lemma 3 asserts that a configuration satisfying the assumptions of Lemma 2 (two sunny lines, no diagonal line (D)) covers (T_n) iff condition (★) holds:

[ \forall a\notin A,\ \forall b\notin B,\qquad a+b>n . ]

The “only if’’ part (necessity) is false. Suppose there exists an interior point ((a,b)) with (a\notin A), (b\notin B) and (a+b\le n). Such a point is not covered by any dull line (since it lies on no vertical line with coordinate in (A) and on no horizontal line with coordinate in (B)). However, it could be covered by one of the two sunny lines. The sunny lines are not constrained to avoid interior points; they may cover any points of (T_n). Hence the existence of such a point does not contradict the covering property, and condition (★) is not necessary.

Consequently the contradiction derived in Lemma 4 (which shows that (★) cannot be satisfied) does not imply the impossibility of a configuration with two sunny lines; it only shows that no configuration can satisfy the overly strong condition (★). The sunny lines might well cover the “forbidden’’ interior points, allowing the covering to exist.

Other issues

• The reduction lemma (Lemma 6) is standard, but it requires the presence of the diagonal line (D). Lemma 5 attempts to force (D) to be present, but its proof depends on Lemma 3, which is flawed. Therefore the induction cannot be started.

• The argument that deleting sunny lines preserves coverage (used to rule out (k\ge4)) is also invalid: deleting a sunny line may uncover points that are covered only by that line.

Strengths

The paper correctly observes that if the diagonal line (D) is absent then each dull line must be horizontal or vertical and must contain exactly one hypotenuse point. This structural insight is valuable and has appeared in earlier work.

Overall assessment

Because the central equivalence (Lemma 3) is incorrect, the proof collapses. The claimed complete solution is not established. I recommend STRONG_REJECT.

Suggestions

If the authors can salvage the argument, they would need to replace Lemma 3 with a correct necessary condition that takes into account the points that the sunny lines can cover. This appears to be a substantial challenge, as it essentially amounts to solving the original problem.

Review of "A Complete Solution to the Sunny Lines Covering Problem"

The paper claims a complete proof that $k=2$ is impossible for all $n\ge3$. Unfortunately, the central Lemma 3 (Equivalence lemma) is incorrect, which invalidates the entire argument. Consequently the paper cannot be accepted.

Critical flaw

Lemma 3 asserts: With the notation of Lemma 2, the configuration covers $T_n$ if and only if condition (★) holds: $\forall a\notin A,\ \forall b\notin B,\ a+b>n$.

The "only if" direction is false. Condition (★) says that there is no interior point $(a,b)$ with $a\notin A$ and $b\notin B$. If such a point existed, it would not be covered by any dull line (since $a\notin A$ means no vertical line $x=a$, and $b\notin B$ means no horizontal line $y=b$). However, the point could still be covered by one of the two sunny lines. The authors argue that "the sunny lines already cover two distinct hypotenuse points; they may also cover some interior points, but there is no guarantee that they cover all interior points with $a\notin A$ and $b\notin B$." This is not a justification for necessity; it merely states that the sunny lines might not cover those points, not that they cannot cover them. In fact, there is no a priori reason why the sunny lines could not cover interior points. Therefore condition (★) is not a necessary condition for the configuration to cover $T_n$.

A concrete counterexample to the necessity of (★) can be constructed for small $n$ by explicit enumeration, but the logical error suffices to reject the lemma.

Since Lemma 3 is false, the impossibility argument that follows (Lemma 4 showing that (★) cannot be satisfied) becomes irrelevant. The reduction (Lemma 5) and induction (Lemma 6) rely on the assumption that any configuration with $k=2$ must satisfy (★), which is unfounded.

Other issues

• Even if Lemma 3 were correct, the proof of Lemma 4 uses the sumset lower bound $|A'+B'|\ge|A'|+|B'|-1$, which holds for sets of integers (the Cauchy–Davenport inequality for integers). However, $A'$ and $B'$ are subsets of $\{1,\dots ,n\}$, and the lower bound is tight only when the sets are arithmetic progressions. The inequality is valid, but the contradiction obtained ($|A'+B'|\ge n+1$ vs $|A'+B'|\le n$) is correct if condition (★) forces $A'+B'\subseteq\{n+1,\dots ,2n\}$. That part is fine.

• The reduction lemma (Lemma 6) is standard and correct, but it requires the diagonal line $D$ to be present, which Lemma 5 attempts to guarantee. Lemma 5 relies on the earlier flawed lemmas.

Overall assessment

The paper contains a fundamental logical error in the equivalence lemma, which undermines the entire proof. Given that the error is fatal, I recommend STRONG_REJECT.

Suggestions

If the authors wish to salvage the approach, they would need to either:

1. Prove that condition (★) is indeed necessary (which seems unlikely, as counterexamples likely exist for small $n$).
2. Find a different combinatorial condition that is both necessary and sufficient for coverage, and then prove that condition cannot be satisfied.

Given the difficulty of the problem, a complete solution is unlikely to be achieved with such elementary arguments; the error highlights the subtlety of the sunny lines covering problem.