For a given integer $k\ge3$, tile the unit square with $k$ rectangles so that the longest of the rectangles' diagonals be as short as possible. Call such a tiling optimal. The solutions are obvious in the easy cases when $k$ is the square of an integer and for a few small values of $k$ only (unpublished). In each of the solved cases, the sides of all rectangles turn out to be rational and their diagonals are equal.

Question. In an optimal tiling, must the sides of all rectangles be rational and their diagonals be equal?

The analogous question for tiling the $n$-dimensional cube with rectangular boxes can be asked for every $n\ge3$ as well.

  • 2
    $\begingroup$ Since this is not a site for random olympiad problems, it would be nice if the OP could give some background on where these questions come from and what is the state of the art (to the best of his knowledge)... $\endgroup$ – Igor Rivin Jul 20 '13 at 23:30
  • 6
    $\begingroup$ @IgorRivin: This problem is neither random nor olympiad. These questions come from my head, and I am not aware of any significant results on this topic. $\endgroup$ – Wlodek Kuperberg Jul 21 '13 at 3:52
  • 1
    $\begingroup$ Which are the few non-square values of $k$ for which this is known? I suspect that there may be counterexamples one $k$ gets large, as there are (if memory serves) there are for the conjecture that when $k$ unit squares are packed into a square of minimal side all are either parallel to the big square's sides or make $45^\circ$ angles with them. $\endgroup$ – Noam D. Elkies Jul 21 '13 at 4:08
  • 1
    $\begingroup$ Suppose an optimal cover uses unequal diagonal lengths. Could not another optimal cover be obtained by enlarging the short diagonals to the longest diagonal, so that all diagonals are of equal length? Or do you not mean cover in the sense of union, but rather partition in the sense that no interior points of the rectangles overlap? $\endgroup$ – Joseph O'Rourke Jul 21 '13 at 14:57
  • 1
    $\begingroup$ @JosephO'Rourke: Yes, Joe. Thanks! Originally I wanted the rectangles to tile the square, then carelessly decided to generalize...; The question has been edited. $\endgroup$ – Wlodek Kuperberg Jul 21 '13 at 15:17

For $k=5$, is this the optimal partition? Rectangle sides $x=\frac{1}{6} \left(3-\sqrt{3}\right) \approx 0.21$ and $1-x$, and (now corrected) all diagonals of length$^2$ of $\frac{2}{3}$, and so length $\sqrt{2/3} \approx 0.816$.

And here is Wlodzimierz's much better partition. Each diagonal has length $\sqrt{2257}/72 \approx 0.660$:
For $k=8$, the $4 \times 2$ partition has diagonal $\sqrt{5}/4 \approx 0.559$. Here is a better, irrational partition, $x=\frac{2}{3}-\frac{\sqrt{\frac{7}{3}}}{6} \approx 0.412$:

  • $\begingroup$ Cut the square with a vertical line into two rectangles, the left one of size $x\times1$ the right one $(1-x)\times1$, where $x=41/72$. Cut the left one into three congruent horizontal rectangles and the right one horizontally into two. The diagonals of all five rectangles come out equal and smaller than $0.66$. I believe this is the optimal tiling for $k=5$. (I don't know yet how to embed drawings here.) $\endgroup$ – Wlodek Kuperberg Jul 22 '13 at 23:29
  • $\begingroup$ @WlodzimierzKuperberg: Did you mean that all diagonal lengths are square roots of rationals? $\endgroup$ – Joseph O'Rourke Jul 22 '13 at 23:58
  • $\begingroup$ Oops! I meant all sides of the rectangles are rational. Sorry. Correcting right away. $\endgroup$ – Wlodek Kuperberg Jul 23 '13 at 0:18
  • 1
    $\begingroup$ This looks like the optimal tiling for $k=8$ - hence a counterexample to the conjecture. Very nice! Now, if the general solution looks "like this" (vertical blocks of congruent rectangles stacked forming strips of the square), then the general problem could be possibly reduced to a number theory question on expressing $k$ as the sum of a certain number, close to $\sqrt{k}$ I suppose, of positive integers that differ from each other by as little as possible. $\endgroup$ – Wlodek Kuperberg Jul 23 '13 at 15:46
  • $\begingroup$ The two partitions under the heading "For $k=8$...," isn't the one on the left actually $k=6$? $\endgroup$ – Gerry Myerson Nov 2 '13 at 22:26

In a new related question I give a conjecture for the unit square which agrees with the $k=5$ and $k=8$ solutions here.

If $s^2 \lt k \lt (s+1)^2$ then the optimal solution has $s$ or $s+1$ rows (depending on which square is closer) each with $s$ or $s+1$ rectangles. More specifically:

If $k=s^2+t$ with $0 \lt t \le s$ then the optimal solution has $s$ rows with $s-t$ rows having $s$ rectangles $b \times \frac1s $ and $t$ rows of $s+1$ rectangles $a \times \frac1{s+1}$ where $b^2+\frac{1}{s^2}=a^2+\frac1{(s+1)^2}$ and $(s-t)b+ta=1$

But if $k=s^2+t$ with $s \le t \lt 2s+1$ then the optimal solution has $s+1$ rows with $2s+1-t$ rows having $s$ rectangles $a \times \frac1s $ and $t-s$ rows of $s+1$ rectangles $\frac1{s+1} \times b$ where $a^2+\frac{1}{s^2}=b^2+\frac1{(s+1)^2}$ and $(2s-t+1)a+(t-s)b=1$

Note that in case $k=s^2+s,$ either description gives all rectangles $\frac1s \times \frac1{s+1}.$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.