Skip to main content
ENHU
Home

Main navigation

  • Discover
    • News
    • Events
    • Tenders
  • Research fields
  • Resources
    • Publications
    • Downloads
  • 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
Széchenyi Plusz RRF
Abstract

We consider the minimum number of lines hn and pn 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 hn=⌈n2⌉ for each n≥1. Studying the piercing problem, we show that 0.7n≤pn≤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
Read more
Home

LinkedIn

Become a partner

Subscribe to newsletter

Send partnership request

Explore

  • News
  • Events
  • Tenders
  • 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
@email

© 2020-2021 Artifical Intelligence National Laboratory, Budapest