Sunny lines covering a triangular lattice: only $k\in{0,1,3}$ are possible

Problem

A line in the plane is called sunny if it is not parallel to any of the $x$-axis, the $y$-axis, and the line $x+y=0$.

Let $n\ge 3$ be an integer. Determine all nonnegative integers $k$ such that there exist $n$ distinct lines in the plane satisfying:

1. for all positive integers $a,b$ with $a+b\le n+1$, the point $(a,b)$ lies on at least one of the lines;
2. exactly $k$ of the lines are sunny.

Let [ P_n:={(a,b)\in\mathbb Z_{>0}^2: a+b\le n+1}. ]

Answer

All such $k$ are [ \boxed{k\in{0,1,3}}. ]

Constructions (existence)

Construction for $k=0$

Take the $n$ (non-sunny) lines [ \ell_s: x+y=s,\qquad s=2,3,\dots,n+1. ] Every point $(a,b)\in P_n$ satisfies $a+b\in{2,\dots,n+1}$, hence lies on exactly one of these lines.

Construction for $k=1$

Take the $(n-1)$ vertical (non-sunny) lines [ x=1,2,\dots,n-1 ] and the line [ \ell: x+(n-1)y=2n-1. ] The line $\ell$ passes through $(n,1)$ and $(1,2)$, so it is not vertical, not horizontal, and has slope $-\tfrac{1}{n-1}\neq -1$; hence it is sunny.

All points in $P_n$ with $a\le n-1$ are covered by the corresponding vertical line. The only point in $P_n$ with $a=n$ is $(n,1)$, which lies on $\ell$.

Construction for $k=3$

Use the following three sunny lines: [ \ell_0: y=x,\qquad \ell_1: x+2y=5,\qquad \ell_2: 2x+y=5. ] These cover exactly the six points with $a+b\le 4$:

• $(1,1),(2,2)$ lie on $\ell_0$;
• $(1,2),(3,1)$ lie on $\ell_1$;
• $(2,1),(1,3)$ lie on $\ell_2$.

For the remaining $n-3$ lines, take the diagonals [ \ell_s: x+y=s,\qquad s=5,6,\dots,n+1. ] These are all non-sunny and cover every point with $a+b\ge 5$.

Thus we obtain $n$ distinct lines with exactly $3$ sunny.

Impossibility (only $k\in{0,1,3}$)

The proof is by reduction to the base case $n=3$.

Step 1: boundary points

The convex hull of $P_n$ is the right triangle with vertices [ (1,1),\ (n,1),\ (1,n). ] Let $B_n\subseteq P_n$ be the set of lattice points on its three sides: [ B_n:={(1,b):1\le b\le n}\ \cup\ {(a,1):1\le a\le n}\ \cup\ {(a,n+1-a):1\le a\le n}. ] A direct count gives [ |B_n|=3n-3 ] (the three vertices are counted twice in the union).

Step 2: a line not containing a side hits $B_n$ in at most $2$ points

A line that does not contain a whole side of the triangle intersects the triangle boundary in at most two points (enter/exit), hence it contains at most two points of $B_n$.

Consequently, if none of the chosen $n$ lines contains a whole side, then these lines cover at most $2n$ boundary points.

For $n\ge 4$ we have $3n-3>2n$, contradiction. Therefore:

Lemma. For every configuration of $n\ge 4$ lines covering $P_n$, at least one of the lines is one of the three side-lines [ x=1,\quad y=1,\quad x+y=n+1. ] In particular, at least one line is non-sunny.

Step 3: reduction from $n$ to $n-1$

Assume $n\ge 4$ and we have $n$ lines covering $P_n$. By the lemma, one of them is a side-line.

• If $x=1$ is among them, delete it and translate the remaining $n-1$ lines by the vector $(-1,0)$. They now cover [ {(a-1,b): (a,b)\in P_n,\ a\ge 2}=P_{n-1}. ]
• If $y=1$ is among them, do the analogous translation by $(0,-1)$.
• If $x+y=n+1$ is among them, delete it; the remaining lines already cover the subset ${(a,b):a+b\le n}=P_{n-1}$.

Translations preserve parallelism, hence preserve the sunny/non-sunny status of each remaining line. Since the deleted side-line is non-sunny, the number of sunny lines does not change.

Therefore, for $n\ge 4$:

If a value $k$ is achievable for $n$, then the same $k$ is achievable for $n-1$.

Equivalently, the set of achievable $k$'s is non-increasing with $n$: [ K_n\subseteq K_{n-1}\quad (n\ge 4). ] Hence for all $n\ge 3$, [ K_n\subseteq K_3. ]

Step 4: base case $n=3$

Here [ P_3={(1,1),(1,2),(2,1),(1,3),(2,2),(3,1)} ] and we must use exactly $3$ lines.

We already exhibited realizations with $k=0,1,3$ (specializing the constructions above).

It remains to show that $k=2$ is impossible.

Assume for contradiction that exactly two of the three lines are sunny, so exactly one line is non-sunny. Any non-sunny line that contains at least two points of $P_3$ must be one of [ \begin{array}{lll} x=1, & x=2, & y=1, \ y=2, & x+y=3, & x+y=4. \end{array} ] (others meet $P_3$ in at most one point and are irrelevant).

In each case, remove the points covered by that non-sunny line. Among the remaining points, any line through two of them is forced to be vertical/horizontal/diagonal (hence non-sunny), so two sunny lines cannot cover them. For example:

• If the non-sunny line is $x=1$, the remaining points are $(2,1),(2,2),(3,1)$, and any line through two of these is $x=2$, $y=1$, or $x+y=4$, all non-sunny.
• If the non-sunny line is $x+y=4$, the remaining points are $(1,1),(1,2),(2,1)$, and any line through two of these is $x=1$, $y=1$, or $x+y=3$, all non-sunny.

The other cases are similar and yield the same contradiction.

Thus $k\neq 2$ for $n=3$, so [ K_3={0,1,3}. ] Therefore $K_n\subseteq{0,1,3}$ for all $n\ge 3$. Together with the constructions, this proves the answer.

Lean4 formalization (mathlib)

A Lean file SunnyLines.lean (attached) formalizes the constructions for $k=0,1,3$. It includes complete coverage proofs (Covers) for these families.

The only remaining placeholder is a single sorry in threeSunnyFamily_sunnyCount, which is a finite Finset cardinality computation (showing that exactly indices $0,1,2$ are sunny).