Divide a rectangle into smaller rectangles with two criteria:

  1. All sub-rectangles must have different sizes.
  2. All sub-rectangles must have diagonals with length 1.

What is the smallest possible number of rectangles in a solution?

Here is a solution where a square is divided into 12 rectangles with unit diagonals. The $x$ values are 0., 0.126115, 0.45009, 0.767632, 1.12506, 1.43832, 1.74608, 1.885, and the $y$ values are 0., 0.04595, 0.783796, 0.992016, 0.990303, 1.73204, 1.885.

same diagonal dissection

Code for 100 digits of accuracy:

NMinimize[{(-1+(x1-x4)^2+y1^2)^2+(-1+(x2-x4)^2+(y1-y2)^2)^2+(-1+(x4-x6)^2+y2^2)^2+(-1+(x1-x2)^2+(y1-y3)^2)^2+(-1+x1^2+y3^2)^2+(-1+(x3-x6)^2+(y2-y4)^2)^2+(-1+(x6-x7)^2+y4^2)^2+(-1+(x2-x3)^2+(y2-y5)^2)^2+(-1+(x3-x5)^2+(y4-y5)^2)^2+(-1+x2^2+(y3-y6)^2)^2+(-1+(x5-x7)^2+(y4-y6)^2)^2+(-1+(x2-x5)^2+(y5-y6)^2)^2, 1/9<x1<x2<x3<x4<x5<x6<x7,0<y1<y2<y3<y5<y6, y2<y4<y5, y6==x7},{x1,x2,x3,x4,x5,x6,x7,y1,y2,y3,y4,y5,y6}, PrecisionGoal->100, AccuracyGoal->100, MaxIterations->100, WorkingPrecision->100]

The below is a earlier, slightly flawed version of the same dissection that was found by hand. The diagonals form two connected sets, colored red and green here.

Same Diagonal Dissection

Is there a solution with a fewer number of rectangles? Can a rectangle be divided into 11 or fewer different unit-diagonal rectangles?

  • What is the algorithm you have used for this construction? – астон вілла олоф мэллбэрг Oct 8 '16 at 1:03
  • My algorithm -- geometry expressions, lots of experimentation, hundreds of parallel lines and circles. Nothing elegant. – Ed Pegg Oct 8 '16 at 15:50
  • You really need to provide more context. Is this about arbitrary rectangles, or a particular one? What exactly is your dissection - either algorithm, or sizes? Do the two different colors indicate anything? The picture alone doesn't mean a thing. For example, you have a green line in the top-left rectangle which is not a diagonal. Then, the top-right rectangle looks bigger than the top-left one in both directions, but you claim that the diagonals are equal. – dxiv Oct 9 '16 at 0:02
  • Long geometric constructions often have errors, looks like that happened here. It's likely fixable for this set of rectangles, I could make a list of dozens of rectangle configurations it won't work for. But a good enough construction to give an idea of the problem. – Ed Pegg Oct 9 '16 at 19:34
  • dvix -- I figured out how to find a working solution with 100 digits of accuracy. The two colors merely indicate diagonals that are connected. – Ed Pegg Oct 10 '16 at 16:02
up vote 3 down vote accepted

First, I'll show example of such $9$-tiling with more comfortable side lengths:

Tiling:
enter image description here
its pattern:
enter image description here
its sub-rectangles sizes:
$x_1 = 0.884, y_1 \approx 0.46748690;$
$x_2 \approx 0.84923220, y_2 \approx 0.52801957;$
$x_3 \approx 0.99816622, y_3 \approx 0.06053267;$
$x_4 \approx 0.11416622, y_4 \approx 0.99346166;$
$x_5 \approx 0.85050017, y_5 \approx 0.52597476;$
$x_6 \approx 0.88273202, y_6 \approx 0.46987676;$
$x_7 \approx 0.06482983, y_7 \approx 0.99789633;$
$x_8 \approx 0.94756185, y_8 \approx 0.31957242;$
$x_9 \approx 0.96466638, y_9 \approx 0.26347442.$
(here $x_1=0.884$ is chosen arbitrarily from the $(0.8686, 0.8946)$ $-$ see below).

And note that there are no "fixed"/unique tiling; they exist as $1$-parametric families of tilings:
enter image description here


Now wider description:

It seems there exists "regular" (maybe elegant :) algorithm.

Step 1:
let's call $n$-tiling "irreducible" if any removing (of $1$ or more sub-rectangles) makes this tiling non-rectangular (excluding trivial $n-1$ sub-rectangles removing).

For considered $n$ we'll find all possible "irreducible" tiling patterns, which allow construct all sub-rectangles of different sizes:

$n=5$: 1 possible pattern:
enter image description here

$n=6$: there are no "irreducible" tilings:
enter image description here

$n=7$: $2$ possible patterns:
enter image description here

(Let's focus on $7$-tilings.)

Step 2:
Enumerate sub-rectangles such that $1$th and $2$nd sub-rectangles are "free", and all further sub-rectangles depend on these two:

let we have $2$ free parameters: $$ a \in(0,1),\; b\in(0,1); $$

$7$-tiling A:
running forward, we mark such sides as "free", which would give us more comfort calculations:

$ y_1 = a, \; x_1 = \sqrt{1-a^2}; \\ x_2 = b, \; y_2 = \sqrt{1-b^2}; \\ x_3 = x_1-x_2, \; y_3 = \sqrt{1-x_3^2}; \quad (x_3>0); \\ y_4 = y_2-y_3, \; x_4 = \sqrt{1-y_4^2}; \quad (y_4>0); \\ x_5 = x_3-x_4, \; y_5 = \sqrt{1-x_5^2}; \quad (x_5>0); \\ y_6 = y_4-y_5, \; x_6 = \sqrt{1-y_6^2}; \quad (y_6>0); \\ x_7 = x_6-x_5, \; y_7 = \sqrt{1-x_7^2}; \quad (x_7>0); $

and close these dependencies by the equation:

$ y_1+y_3+y_5=y_7. $

Now, we have $16$ variables $a,b,x_1,y_1,\ldots,x_7,y_7$ and $15$ equations. It describes some $2D$-curve: $$ F_1(a,b)=0, \;\mbox{ or } b = f_1(a) \mbox{ in our case }, \; \; a\in (a_1,a_2). $$ for this pattern we'll have $a_1 = 0, a_2 \approx 0.0732518$.

Plot of the curve (Mathematica):

y1 := a;          x1 := Sqrt[1 - a^2];
x2 := b;          y2 := Sqrt[1 - b^2];
x3 := x1 - x2;    y3 := Sqrt[1 - x3^2];
y4 := y2 - y3;    x4 := Sqrt[1 - y4^2];
x5 := x3 - x4;    y5 := Sqrt[1 - x5^2];
y6 := y4 - y5;    x6 := Sqrt[1 - y6^2];
x7 := x6 - x5;    y7 := Sqrt[1 - x7^2];

ContourPlot[y1 + y3 + y5 == y7, {a, 0.000, 0.08}, {b, 0.000, 0.08}, 
   GridLines -> {0.01*Range[0, 10], 0.01*Range[0, 10]}]

enter image description here

A few points of this curve: $ (a,b)\approx (0, 0.004217507); \\ (a,b)\approx (0.01, 0.003927340); \\ (a,b)\approx (0.02, 0.003547516); \\ (a,b)\approx (0.03, 0.003077705); \\ (a,b) \approx (0.0307543, 0.00303861); \mbox{ see Ivan Neretin's answer} \\ (a,b)\approx (0.04, 0.002517544); \\ (a,b)\approx (0.05, 0.001866428); \\ (a,b)\approx (0.06, 0.001124581); \\ (a,b)\approx (0.07, 0.000290911); \\ (a,b)\approx (0.0732518, 0). $

So this kind of tiling must have shortest sub-rectangle side less than $\approx0.004$.


$7$-tiling B: similar way; but this pattern gives us tiling with pairs of equivalent sub-rectangles.


$5$-tiling: gives us tiling with pairs of equivalent sub-rectangles.


$8$-tilings:

there are a few patterns with successful tilings, but all them (which I considered) have too small (for viewing) smallest sidelength.


$9$-tilings:

The presented above tiling can be described by the system of equations:

$x_1 = a, \; y_1 = \sqrt{1-x_1^2};$
$x_2 = b, \; y_2 = \sqrt{1-x_2^2};$
$y_3 = y_2-y_1, \; x_3 = \sqrt{1-y_3^2}; \quad (y_3>0);$
$x_4 = x_3-x_1, \; y_4 = \sqrt{1-x_4^2}; \quad (x_4>0);$
$y_5 = y_4-y_1, \; x_5 = \sqrt{1-y_5^2}; \quad (y_5>0);$
$x_6 = x_2+x_3-x_4-x_5, \; y_6 = \sqrt{1-x_6^2}; \quad (x_6\in(0,1)\: );$
$y_7 = y_2+y_6, \; x_7 = \sqrt{1-y_7^2}; \quad (y_7<1);$
$x_8 = x_6+x_7, \; y_8 = \sqrt{1-x_8^2}; \quad (x_8<1);$
$y_9 = y_7+y_8-y_2-y_5, \; x_9 = \sqrt{1-y_9^2}; \quad (y_9\in(0,1)\:);$
and
$x_4+x_5=x_9$,
where $a\in(0,1)$, $b\in(0,1)$, and $(a,b)$ are linked therefore by certain dependency $F_2(a,b)=0$, or $b= f_2(a)$ in our case, where $a\in(a_1,a_2)$;

$a_1 \approx 0.868517092, a_2 \approx 0.8946$.

And a few points of the curve: $ (a,b) \approx (0.868517092, 0.868517091); \\ (a,b) \approx (0.870, 0.86678506); \\ (a,b) \approx (0.875, 0.86073752); \\ (a,b) \approx (0.880, 0.85443240); \\ (a,b) \approx (0.885, 0.84791329); \\ (a,b) \approx (0.890, 0.84122558); \\ (a,b) \approx (0.8946, 0.83497558). $

I believe that a rectangle with certain aspect ratio can be done in as few as 7 parts. Dissection - 7 parts

Note that the picture is not entirely accurate, otherwise the 7th rectangle would not be seen at all.

The dimensions of the rectangles (short side first) are: $$ \begin{array}{l|l} 1& 0.5959136\times0.8030486\\ 2& 0.0837313\times0.9964883\\ 3& 0.4005748\times0.9162641\\ 4& 0.1132155\times0.9935704\\ 5& 0.3976568\times0.9175342\\ 6& 0.0307543\times0.9995270\\ 7& 0.0030386\times0.9999954 \end{array} $$

  • Very nice. I'll need to check this by finding the exact solution. When I was looking in 7-space, I may have dismissed this one because I couldn't see all the rectangles. – Ed Pegg Oct 21 '16 at 18:37

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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