Piercing the Chessboard

2023/01/01 by Gergely Ambrus, Imre Bárány, Frankl Péter +3 · 1 voice
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #Artificial Intelligence in Games #Computational Geometry and Mesh Generation #Digital Image Processing Techniques

paper · doi:10.1137/21m146048x

openalex publication_date 2023/07/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 × 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 ≥ 1. Studying the piercing problem, we show that 0.7n ≤ p_n ≤ n-1 for n≥ 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.

Citations

• The plank problem for symmetric bodies

Discussions

• This problem is (an easier?) analogue of the following question: Minimum number of straight lines to cover $n \times n$ grid? An equilateral triangle with side $n$ is divided into $n^2$ unit triangles [stackexchange, 1 points]

Related

• The problem of the pawns
• Improved lower bounds for Queen's Domination via an exactly-solvable relaxation
• An Explicit Solution to the Chessboard Pebbling Problem
• Rook Endgame Problems in m by n Chess
• The closed knight tour problem in higher dimensions