existence of $99$ lines in $\mathbb{R}^2$ passing through $100^2$ boxes

Question

Problem 5 from "Bernoulli Trials Problems for 2017" link

Prove or disprove the following: there exist $99$ lines in $\mathbb{R}^2$ so that for all $k,l \in \{1,2,\cdots, 100\}$, one of the lines passes through the interior of the square with vertices at $(k,l), (k-1, l), (k-1, l-1),$ and $(k, l-1)$.

I'm not sure which lines to choose; the statement may be true. It seems that the lines given by the equations $2x+4y = 3+6k$ for $1\leq k\leq 98$ skip a bunch of squares (they have slope $-1/2$ and intercepts at $y = \frac{3+6k}4$ for each $k$), so I might have to choose the lines differently. There are $10^4$ squares that the $99$ lines need to pass through, so on average each line should pass through over $100$ squares. So if the statement is false, perhaps the Pigeonhole argument might be useful?

Of course, one could just sketch out the lines in desmos, but that doesn't really demonstrate why the lines satisfy the given property.

Note: Ideally I'd want a formal proof of why the answer is correct (if you change $n$ to $100$ and the last equation to $2(n-1) x - 2(n-2) = y$). I think there should be one that isn't too tedious and likely uses induction.

Answer 1

Here is a formal write-up of Calvin Khor's solution. It is a little bit tedious, but I'm afraid that can't be helped.

I denote by $D_j$ the line defined by $2x+4y=6j+3$, for $1\leq j \leq n-2$, and by $D$ the line defined by $2(n-1)x-2(n-2)y=n$. Also I denote by $I_{k,l}$ the open square $(k-1,k)\times(l-1,l)$, which is the interior of the closed square $[k-1,k]\times[l-1,l]$.

If $M_j(y)$ is the unique point of $D_j$ with ordinate $y$, its abscissa is $x=\frac{3+6j}{2}-2y$. So $M_j(y)\in I_{k,l}$ iff we have both $l-1 \lt y \lt l$ and $k-1 \lt x \lt k \Leftrightarrow \frac{3+6j-2k}{4} \lt y \lt \frac{5+6j-2k}{4}$. So that

$$ M_j(y)\in I_{k,l} \Leftrightarrow \max\bigg(l-1,\frac{3+6j-2k}{4}\bigg) \lt y \lt \min\bigg(l,\frac{5+6j-2k}{4}\bigg) \tag{1} $$

and hence,

$$ \begin{array}{lcl} I_{k,l} \cap D_j \neq \emptyset &\Leftrightarrow& \max\bigg(l-1,\frac{3+6j-2k}{4}\bigg) \lt \min\bigg(l,\frac{5+6j-2k}{4}\bigg) \\ &\Leftrightarrow& \left\lbrace\begin{array}{l}\max\bigg(l-1,\frac{3+6j-2k}{4}\bigg) \lt l \\ \max\bigg(l-1,\frac{3+6j-2k}{4}\bigg) \lt \frac{5+6j-2k}{4}\end{array}\right.\\ &\Leftrightarrow& \left\lbrace\begin{array}{l}\frac{3+6j-2k}{4} \lt l \\ l-1 \lt \frac{5+6j-2k}{4}\end{array}\right.\\ &\Leftrightarrow& l-\frac{3}{2} \lt \frac{3+6j-2k}{4} \lt l \\ &\Leftrightarrow& \frac{2k+4l-9}{6} \lt j \lt \frac{2k+4l-3}{6} \\ \end{array}\tag{2} $$

This leads us to introduce the term $J=\frac{2k+4l-3}{6}$. Then,

$$ I_{k,l} \cap D_j \neq \emptyset \Leftrightarrow J-1 \lt j \lt J \Leftrightarrow j \lt J \lt j+1\tag{3} $$

Thus, $I_{k,l}$ intersects $D_1$ iff $1 \lt J \lt 2$, it intersects $D_2$ iff $2 \lt J \lt 3$, etc. Gluing thoses cases together, we see that $I_{k,l}$ intersects some $D_j$ for $1\leq j \leq n-2$ iff $1\leq J \leq n-1$ and $J$ is not an integer. Note that, since $J$ is a fraction with odd numerator and even denominator, it is never an integer.

We are therefore left with two cases : (a) $J \lt 1$, or (b) $J \gt n-1$.

Suppose first that (a) holds. Then $1\gt J \geq \frac{2k+4-3}{6}$ forces $k\leq 2$, while $1\gt J \geq \frac{2+4l-3}{6}$ forces $l = 1$. So either $(k,l)=(1,1)$ (in which case the point $(x=\frac{3n-2}{4n-4},y=\frac{1}{4})$ lies on $I_{k,l}\cap D$) or $(k,l)=(2,1)$ (in which case the point $(x=\frac{5n-6}{4n-4},y=\frac{3}{4})$ lies on $I_{k,l}\cap D$). This finishes case (a).

Suppose next that (b) holds. Then $n-1\lt J \leq \frac{2k+4n-3}{6}$ forces $k\geq n-1$, while $n-1\lt J \leq \frac{2n+4l-3}{6}$ forces $l=n$. So either $(k,l)=(n,n)$ (in which case the point $(x=n-\frac{3n-2}{4n-4},y=n-\frac{1}{4})$ lies on $I_{k,l}\cap D$) or $(k,l)=(n-1,n)$ (in which case the point $(x=n-\frac{5n-6}{4n-4},y=n-\frac{3}{4})$ lies on $I_{k,l}\cap D$). This finishes case (b) and the whole proof.

Answer 2

I found the solution here. The given solution is wrong, but becomes correct if you fix a typo: the final line $2(n − 1)x + 2(n − 2)y = n$ should instead be $2(n − 1)x \overset{\huge\color{red}\downarrow}- 2(n − 2)y = n.$ (and $n=100$)

The other 98 lines are as you defined them, $2x+4y=3+6k$ for $k=1,2,\dots, n-2=98$.

Here is a Desmos plot of all 99 lines:

and a zoom near $(0,0)$:

This final line similarly intersects the remaining two squares near $(100,100)$.

As pointed out by Jean-Claude Arbaut, this works for $n\ge 3$. In the above comments it was stated that the result is false for $n=3$. Here is this solution with $n=3$:

I'll leave formalizing this into a written proof to someone else...

Answer 3

I said I'd leave this to someone else, but here we are...this formalizes my other answer in a way that mimics how I understood the pictures.

1. The lines $2x +4y=3+6k$ ($k=1,2,\dots,n-2$) can be written in the geometric form $$ \binom {1/\sqrt5}{2/\sqrt5}\cdot \binom x y = \frac{3/2}{\sqrt5}+\frac{3k}{\sqrt5}, $$ showing that the perpendicular distance between consecutive lines is $3/\sqrt5$.

2. The projection in the direction $\binom {1/\sqrt5}{2/\sqrt5}$ of any unit length square parallel to the axes has length $$ \binom {1/\sqrt5}{2/\sqrt5}\cdot \binom 11 = \frac3{\sqrt 5}.$$ Corollary 1: No square can fit strictly between two consecutive lines.

3. For all $k$, $2x+4y=3+6k$ has no integer solutions in $x,y$. Proof: $3$ is odd, but $2x+4y-6k$ is even.

Corollary 2: All these $n-2$ lines pass through the interiors of the squares they touch.
Corollary 3: All the squares with points between the first and last line are covered.

Now we just check which squares do not have points between the first and last lines. Note that the region below the first line is given by $$ 2x+4y < 9.$$ We need to find integer solutions; this will give us the upper right corners of squares we left out. Clearly (as $x,y\ge1$) if $x>4$ or $y>3$, then they're too large. So we just need to check $x=1,2,3; \ y=1,2$.

| x | y | 2x+4y | <9? |
|---|---|-------|-----|
| 1 | 1 | 6     | yes |
| 1 | 2 | 10    |     |
| 2 | 1 | 8     | yes |
| 2 | 2 | 12    |     |
| 3 | 1 | 10    |     |
| 3 | 2 | 14    |     |

Similarly the upper-right corners of squares above the last line satisfy

$$2(x-1)+4(y-1)>3+6(n-2)=6n-9.$$ The minus ones are because the closest integer coordinates are from the square that contains the last line; see Corollary 3. Recall we are looking for $x,y\in\{1,2,\dots,n\}$. Make the transformation $X=n-(x-1)$ and $Y=n-(y-1)$. The inequality transforms to $$ 6n - 2X - 4Y > 6n -9,$$ which is the same inequality as before: $2X+4Y<9$. We are still looking for $X,Y\in \{1,2,\dots,n\}$. Hence, there are four boxes not included: $$ (x,y)= (1,1),\ (2,1), \ (n,n), \ (n-1,n).$$ Observe that these four boxes are 2 pairs of boxes that are adjacent. So we can choose as our final line a line that passes through the midpoints of each pair. Since $n\ge3$, this $(n-1)$th line is neither horizontal nor vertical, so it passes through all remaining four boxes. QED