Piercing the Chessboard

DOI10.1137/21M146048XMaRDI QIDQ6170442zbMATH OpenOpenAlexFDO

Authors Gergely Ambrus, Imre Bárány, Peter Frankl, Dániel Varga

Publication date 10 August 2023

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2111.09702

zbMATH Keywords

cells in a latticediscrete plank problemslines

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Lattice packing and covering (number-theoretic aspects) (11H31) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30)

Abstract: We consider the minimum number of lines $h_n$ and $p_n$ needed to intersect or pierce, respectively, all the cells of the $nimesn$ 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=lceilfracn2ceil$ for each $ngeq1$. Studying the piercing problem, we show that $0.7nleq{p}_{n}leqn-1$ for $ngeq3$, 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.

Recommendations

• How (not) to cut your cheese
• On optimal piercing of a square
• An upper bound for the minimum number of queens covering the \(n {\times} n\) chessboard
• Cells in the box and a hyperplane
• scientific article; zbMATH DE number 436080

Cites work

• A Solution of the "Plank Problem"
• Cells in the box and a hyperplane
• Covering paths and trees for planar grids
• Covering paths for planar point sets
• Covering rectangles by few monotonous polyominoes
• Digital Straight Line Segments
• Discrete Representation of Straight Lines
• How (not) to cut your cheese
• scientific article; zbMATH DE number 2129318 (Why is no real title available?)
• scientific article; zbMATH DE number 1436417 (Why is no real title available?)
• On the lattice property of the plane and some problems of Dirac, Motzkin and Erdős in combinatorial geometry
• The plank problem for symmetric bodies

Cited in

(2)

• scientific article; zbMATH DE number 4134064 (Why is no real title available?)
• Plank theorems and their applications: a survey

This page was built for publication: Piercing the Chessboard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6170442)