Lines covering points on napkin Suppose we place a $100\times 100$ napkin on an infinite lattice plane. What is the minimum number of lines that can always cover all the lattice points lying inside or on the border of the napkin, no matter the orientation of the napkin?
Source: St. Petersburg Olympiad 2014
 A: I claim the minimum is $141 = \lfloor 100 \cdot \sqrt{2} \rfloor$ lines.
Here's a sketch of the argument.
Proof that this is enough: The width of the napkin is at most the diagonal of the square, which is $100 \cdot \sqrt{2}$. If the width is less than $140$, then we are done. Otherwise there are unique left-most and right-most lattice points on the napkin. Use one line to connect them and cover the rest of the napkin with $140$ vertical lines.
Proof that we can't do better: Consider the napkin that has been rotated by $45$ degrees so that its width is $100 \cdot \sqrt{2}$. Position the top corner of this rotated napkin to some lattice point. Assume that we could cover the napkin with $140$ lines. Each line can be given as an equation $a_k x + b_k y = c_k$ where at least one of $a_k, b_k$ is non-zero. In particular the polynomial
$$P(x,y) = (a_1 x + b_1 y - c_1) \dots (a_{140} x + b_{140} y - c_{140})$$
of degree $140$ vanishes on every point of the napkin. We will show that the coefficient of every monomial $x^u y^v$ with $u+v = 140$ is $0$, which is a contradiction.
To do this we will employ the Combinatorial Nullstellensatz. Assume that the coefficient of $x^u y^v$ with $u+v = 140$ is non-zero. Then on the napkin we can find a rectangle of size $(u+1) \times (v+1)$, on which $P$ vanishes, contradictory to the Nullstellensatz.
