Institute of Mathematics and Informatics Bulgarian Academy of Sciences
Citation:
Serdica Mathematical Journal, Vol. 21, No 3, (1995), 219p-230p
Abstract:
In this article we explore the so-called two-dimensional tree− search
problem. We prove that for integers m of the form m = (2^(st) − 1)/(2^s − 1) the
rectangles A(m, n) are all tight, no matter what n is. On the other hand, we prove
that there exist infinitely many integers m for which there is an infinite number
of n’s such that A(m, n) is loose. Furthermore, we determine the smallest loose
rectangle as well as the smallest loose square (A(181, 181)). It is still undecided
whether there exist infinitely many loose squares.
