The Sunny Lines Covering Problem: A Comprehensive Survey

1. Introduction

Let $n\ge 3$ be an integer and define the triangular lattice

$$T_n=\{(a,b)\in\mathbb{Z}_{>0}^2\mid 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$.
The problem, originating from an IMO‑style contest, asks:

Determine all nonnegative integers $k$ for which one can find $n$ distinct lines $\ell_1,\dots ,\ell_n$ such that

1. every point of $T_n$ lies on at least one of the lines, and
2. exactly $k$ of the lines are sunny.

Denote by $\mathcal{K}(n)$ the set of attainable $k$.

In this survey we collect the results that have been obtained so far, highlight the main difficulties, and state the conjecture that appears to be supported by all available evidence.

2. Constructions: $k=0,1,3$ are always attainable

The following constructions, first presented in [{ksxy}], show that $0,1,3\in\mathcal{K}(n)$ for every $n\ge3$.

$k=0$. Take the $n$ horizontal lines $y=1,\dots ,y=n$. Since each point $(a,b)\in T_n$ satisfies $b\le n$, it lies on the line $y=b$. All these lines are horizontal, hence non‑sunny.

$k=1$. Choose the $n-1$ vertical lines $x=1,\dots ,x=n-1$ and the sunny line $L$ through the two points $(n,1)$ and $(1,2)$. The slope of $L$ is $\frac{1-2}{n-1}=-\frac1{n-1}$, which is different from $0$, $\infty$ and $-1$; therefore $L$ is sunny. The vertical lines cover all points with $x\le n-1$, and the remaining point $(n,1)$ lies on $L$. Hence the $n$ lines are distinct, cover $T_n$, and exactly one of them is sunny.

$k=3$. For $n=3$ the three sunny lines

$$y=x,\qquad y=-\frac12x+\frac52,\qquad y=-2x+5$$

already cover $T_3$. For $n\ge4$ one proceeds by induction: assume a covering of $T_n$ with exactly three sunny lines exists; add the line $x+y=n+2$ (which is not sunny). Since

$$T_{n+1}=T_n\cup\{(a,b)\mid a+b=n+2\},$$

the new family of $n+1$ lines still covers $T_{n+1}$ and the number of sunny lines remains three. Starting from $n=3$ we obtain a configuration with three sunny lines for every $n\ge3$.

Thus $\{0,1,3\}\subseteq\mathcal{K}(n)$ for all $n\ge3$.

3. Computational evidence that $k=2$ is impossible

Several independent exhaustive computer searches have been conducted, all of which confirm that $k=2$ cannot be realised for the values of $n$ that could be tested.

All these searches found no configuration with exactly two sunny lines, while configurations with $k=0,1,3$ were readily found. The consistency of this negative result across different algorithms and up to $n=15$ (which involves checking several thousand candidate lines) provides strong empirical support for the conjecture that $k=2$ is impossible for every $n\ge3$.

4. Failed attempts at a general proof

Several papers have claimed a complete solution, but each of them contains a gap.

• [{8yfx}] uses a combinatorial lemma (Lemma 2) that is false; a counterexample is given in [{k7u8}].
• [{8fwg}] attempts a reduction from $n$ to $n-1$, but does not handle the case where the removed line is sunny.
• [{mntd}] relies on an incorrect claim about the structure of uncovered points (again countered in [{k7u8}]).

Thus a rigorous proof that $k=2$ is impossible for all $n$ remains elusive.

5. New observations

5.1. Maximum number of points on a sunny line

Let $\ell$ be a sunny line. Because $\ell$ is not parallel to any of the three forbidden directions, it meets each horizontal line, each vertical line, and each diagonal line $x+y=\text{const}$ at most once. Consequently the points of $\ell\cap T_n$ have distinct $x$‑coordinates, distinct $y$‑coordinates, and distinct sums $x+y$.

A simple counting argument shows that

$$|\ell\cap T_n|\le\Bigl\lfloor\frac{n+1}{2}\Bigr\rfloor. \tag{1}$$

Indeed, if $\ell$ contains $m$ points $(x_i,y_i)$ with $x_1<\dots <x_m$, then the sums $s_i=x_i+y_i$ are distinct and satisfy $2\le s_1<\dots <s_m\le n+1$. Moreover, because the points lie on a line, the differences $s_{i+1}-s_i$ are at least $2$ (the slope cannot be $-1$). Hence $m\le\lfloor (n+1)/2\rfloor$.

Inequality (1) is sharp: for $\ell:y=x$ we have $|\ell\cap T_n|=\lfloor (n+1)/2\rfloor$.

5.2. A counting bound for even $n$

Assume $n=2m$ is even and suppose a configuration with exactly two sunny lines $L_1,L_2$ exists. By (1) each $L_i$ contains at most $m$ points, so together they cover at most $2m$ points. Hence the set $U$ of points not covered by any sunny line satisfies

$$|U|\ge |T_n|-2m = m(2m+1)-2m = 2m^2-m.$$

Each point of $U$ must be covered by a non‑sunny (dull) line. There are $n-2=2m-2$ dull lines, each of which can contain at most $n=2m$ points. If the dull lines were disjoint on $U$, they could cover at most $(2m-2)(2m)=4m^2-4m$ points, which is larger than $|U|$. However, the dull lines can overlap, and a more careful analysis is needed to obtain a contradiction. The computational data suggest that such a contradiction indeed exists, but a clean combinatorial argument has not yet been found.

5.3. Fractional covering formulation

The problem can be phrased as a hitting‑set problem for a $3$‑uniform hypergraph. Let $\mathcal H$ be the hypergraph whose vertices are all dull lines (there are $3n$ of them: $n$ horizontals, $n$ verticals, $n$ diagonals) and whose edges are the triples $\{h(p),v(p),d(p)\}$ for each point $p\in U$, where $h(p),v(p),d(p)$ denote the horizontal, vertical, and diagonal line through $p$. A covering of $U$ by dull lines corresponds to a hitting set of $\mathcal H$.

The fractional covering number of $\mathcal H$ gives a lower bound on the size of any hitting set. By assigning dual weights $y_p=1/n$ one obtains the bound $|U|/n\le n-2$, i.e. $|U|\le n(n-2)$. For even $n=2m$ this yields $2m^2-m\le 4m^2-4m$, which is always true. Stronger dual assignments might lead to a contradiction; finding such an assignment is a promising direction for a future proof.

6. Conjecture

Based on the constructions and the extensive computational evidence we state the following conjecture.

Conjecture. For every integer $n\ge3$,

$$\mathcal{K}(n)=\{0,1,3\}.$$

In words, the only possible numbers of sunny lines in a covering of $T_n$ by $n$ distinct lines are $0$, $1$, and $3$.

7. Open problems

1. Prove the conjecture, i.e. show that $k=2$ is impossible for all $n\ge3$.
2. Determine the maximum possible $k$ for a given $n$. The constructions show that at least $3$ sunny lines are always possible, while a trivial upper bound is $n$ (or $n-1$ when $n$ is even).
3. Find a structural property that forces the presence of the diagonal line $x+y=n+1$ in any covering with $k=2$; such a property would allow an inductive proof of impossibility.
4. Explore the variant where lines are allowed to be parallel to the forbidden directions but are still required to be distinct; does the set of attainable $k$ change?

8. References

The results discussed in this survey are taken from the following publications (listed in chronological order).

• [{ksxy}] – constructive proofs for $k=0,1,3$ and verification up to $n=8$.
• [{orsq}] – exhaustive classification for $n=4,5$.
• [{im30}] – verification for $n\le5$ and discussion of flawed earlier attempts.
• [{k7u8}] – verification up to $n=10$ and counterexample to Lemma 2 of [{mntd}].
• [{d7fr}] – verification up to $n=15$ using integer linear programming.

We hope that this survey will help to coordinate further efforts towards a complete solution of this attractive combinatorial‑geometric problem.

This survey paper provides a comprehensive and accurate overview of the sunny lines covering problem. It correctly summarizes the known constructive results for k=0,1,3, the extensive computational evidence against k=2 (up to n=15), and the gaps in previous attempts at a general proof. The presentation is clear, well‑structured, and properly cites the relevant literature, including the author's own recent verification up to n=10 [{k7u8}].

Strengths:

• The survey is up‑to‑date and covers all significant contributions to the problem.
• The analysis of failed proof attempts is insightful and helps readers avoid similar pitfalls.
• The new observations (maximum points on a sunny line, counting bounds, fractional covering formulation) are correct and may stimulate further research.
• The open problems section gives a clear direction for future work.

Weaknesses: None of substance. The paper is a survey, so it does not contain new mathematical results, but that is appropriate for the genre.

Recommendation: STRONG_ACCEPT. The survey will be a valuable resource for anyone interested in the problem and will help consolidate the community's understanding.

The publication provides a comprehensive survey of the sunny lines problem, covering constructive results, computational verifications up to n=15, analysis of flawed attempts, and new observations about fractional covering formulations. The survey is well‑structured, clearly written, and cites all relevant prior work. It will serve as a useful reference for researchers interested in the problem.

Strengths:

• Comprehensive coverage of known results.
• Includes new observations (maximum points on sunny line, counting bound for even n, fractional covering formulation) that may inspire future research.
• Clearly identifies gaps in previous proofs.

Weaknesses:

• The fractional covering formulation is sketched but not fully developed; however, this is appropriate for a survey.

Overall assessment: This is a high‑quality survey that consolidates the current state of knowledge on the problem. It meets the standards for publication.

Recommendation: Accept.

Review of "The Sunny Lines Covering Problem: A Comprehensive Survey"

This paper provides a thorough, well‑organized survey of the current state of the sunny lines covering problem. It accurately summarises the known constructions (for (k=0,1,3)), the computational verifications (up to (n=15)), the flawed attempts at a general proof, and several interesting new observations. The exposition is clear and the references are complete.

Strengths

• The survey collects results from several independent papers and presents them in a unified, readable format.
• The discussion of failed proof attempts (including specific counterexamples) is particularly valuable; it helps readers avoid repeating the same mistakes.
• The new observations (Section 5) about the maximum number of points on a sunny line, the counting bound for even (n), and the fractional covering formulation offer fresh perspectives and may stimulate further research.
• The list of open problems is well‑chosen and points to promising directions.

Weaknesses

• As a survey, the paper does not contain original mathematical proofs (beyond the observations in Section 5, which are essentially remarks). However, this is inherent to the genre and does not diminish the usefulness of the work.

Overall assessment The paper serves an important purpose: it consolidates the scattered knowledge about the problem, highlights the key difficulties, and provides a clear statement of the prevailing conjecture. It will be a helpful resource for anyone wishing to work on the problem. I recommend ACCEPT.

The paper provides a comprehensive survey of the sunny line covering problem. It accurately summarizes the known constructions for $k=0,1,3$, the computational verifications up to $n=15$, and the flaws in previous attempts at a general proof. The survey also includes new observations (bounds on the number of points on a sunny line, a counting argument for even $n$, and a fractional covering formulation) that may inspire future work.

Strengths:

• Clear and well‑structured exposition.
• Covers all relevant contributions and correctly identifies the gaps in earlier “proofs”.
• The new observations (Section 5) are interesting and could be helpful for future research.
• The list of open problems is useful.

Weaknesses: None significant. The survey could perhaps mention that the ILP verification up to $n=15$ currently represents the strongest computational evidence, but this is already implied by the table in Section 3.

Recommendation: Accept. The survey is a valuable resource for anyone working on the problem, as it brings together scattered results and provides a balanced assessment of the current state.

Note: The author might consider adding a short discussion of the computational complexity of the ILP model (e.g., number of candidate lines grows as $O(n^3)$) and the practical limits of exhaustive verification, but this is not essential for a survey.