On optimal piercing of a square

Abstract

© 2018 Elsevier B.V. We treat the following problem: given an n×n square ABCD, determine the minimum number of points that need to be chosen inside the square ABCD such that there does not exist a unit square inside the square ABCD containing none of the chosen points in its interior. In other words, we are interested to know how to most efficiently “destroy” a square-shaped object of side length n, where “destroying” is achieved by piercing as few as possible small holes, and the square is considered “destroyed” if no unpierced square piece of unit side length can be salvaged. This problem actually belongs to the family of problems centered about the so-called piercing number: indeed, if Un denotes the collection of all open unit squares that can be fitted inside a given n×n square, the value that we are looking for is the piercing number of the collection Un, denoted by π(Un). We show that π(Un)=n2 when n⩽7, and give an upper bound for π(Un) that is asymptotically equal to [Formula presented]n2, which we believe is asymptotically tight. We then generalize our reasoning in order to obtain a similar upper bound when ABCD is a rectangle, as well as an upper bound for π(Ux) when x is not necessarily an integer. Finally, we show that our results have an application to the problem of packing a given number of unit squares in the smallest possible square; it turns out that our results present a general “framework” based on which we are able to reprove many results on the mentioned problem (originally obtained independently of each other) and also obtain a new result on packing 61 unit squares.