Piercing the chessboard

Abstract

We consider the minimum number of lines $h_n$ and $p_n$ needed to intersect or pierce, respectively, all the cells of the $n\times n$ chessboard. Determining these values can also be interpreted as a strengthening of the classical plank problem for integer points. Using the symmetric plank theorem of K. Ball, we prove that $h_n=\lceil \frac{n}{2}\rceil$ for each $n\ge 1$. Studying the piercing problem, we show that $0.7n\le p_n\le n-1$ for $n\ge 3$, where the upper bound is conjectured to be sharp. The lower bound is proven by using the linear programming method, whose limitations are also demonstrated.

15 pages, 7 figures. Final, accepted version. Color of figures modified in order to comply with BW print