Széchenyi Plan Plus | Government of Hungary. Funded by the European Union. NextGeneration EU.

EN HU
  • Discover
    • News
    • Events
  • Research fields
  • Resources
    • Publications
    • Downloads
    • Brochure
  • About us
  • Partners
  1. Home
  2. Publications
(2022) SIAM JOURNAL ON DISCRETE MATHEMATICS 0895-4801 1095-7146

Piercing the chessboard

arxiv.org/abs/2111.09702v1
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=⌈n2⌉ 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.

Authors
Gergely Ambrus
Imre Barany
Peter Frankl
Dániel Varga
Institutes

Become a partner

Subscribe to newsletter

Send partnership request

Explore

  • News
  • Events
  • Publications
  • Downloads
  • Partners

Research fields

  • Foundations of AI
  • Human Language Processing
  • Machine perception
  • Medical, Health and Biology
  • Security and Privacy
  • Sensors, IoT and Telecommunications

Contact us

Hungary, H-1111 Budapest,
Kende u. 13-17.

+36 1 279 6000

milab@sztaki.hun-ren.hu

© 2020-2021 Artifical Intelligence National Laboratory, Budapest