16
$\begingroup$

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.

$\endgroup$
11
  • 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, 2013 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$ Jul 21, 2013 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$ Jul 21, 2013 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$ Jul 21, 2013 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$ Jul 21, 2013 at 15:17

2 Answers 2

10
$\begingroup$

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$.
     Sq5Rects


And here is Wlodzimierz's much better partition. Each diagonal has length $\sqrt{2257}/72 \approx 0.660$:
     WK5Rects
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$:
   Sq8Rects62

$\endgroup$
8
  • $\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$ Jul 22, 2013 at 23:29
  • $\begingroup$ @WlodzimierzKuperberg: Did you mean that all diagonal lengths are square roots of rationals? $\endgroup$ Jul 22, 2013 at 23:58
  • $\begingroup$ Oops! I meant all sides of the rectangles are rational. Sorry. Correcting right away. $\endgroup$ Jul 23, 2013 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$ Jul 23, 2013 at 15:46
  • $\begingroup$ The two partitions under the heading "For $k=8$...," isn't the one on the left actually $k=6$? $\endgroup$ Nov 2, 2013 at 22:26
3
$\begingroup$

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}.$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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