Determine all integers $m$ for which the $m \times m$ square can be dissected into five rectangles, the side lengths of which are the integers $1,2,3,\ldots,10$ in some order.
Problem
Source: European Girl's MO 2013, Problem 2
Tags: geometry, rectangle, combinatorial geometry, EGMO, EGMO 2013
10.04.2013 21:27
Let rectangles $R_1,...,R_5$ have sides $(a_1, b_1)...(a_5,b_5)$ Then $m^2=a_1\cdot b_1+...+a_5\cdot b_5 \leq {a_1^2+b_1^2\over 2}+...+{a_5^2+b_5^2\over 2}={385\over 2}$ So $m\leq 13$. On the other hand we have $m^2 \geq 5 \sqrt[5]{a_1\cdot...\cdot b_5} = 5\sqrt[5]{10!} = 5\sqrt[5]{3628800}> 5\sqrt[5]{20^5} =100$ so $m\geq 11$.
10.04.2013 21:31
using that if $a>c$ and $b>d$ we have $(a-c)*(b-d)>0$ repeatedly we obtain that the smallest area formed by the rectangles is $1*10+2*9+..+5*6=110$ and the largest $10*9+8*7+..+2*1=190$ so all possible answers are $11,12,13$. for $11,13$ we can construct a model. for $12$ it is analizing cases and proving that there is no model.
26.10.2014 01:30
Another way to solve this easy problem.Consider four corner unit squares,now it is easy to notice that no rectangle can have $2$ corner unit squares(just use the fact that all lenghts are different),so the side of the square is less than $14$($max$ perimeter is $3+4+...+10$) and obviously the side of the square is bigger than $10$.Now,models for $11$ and $13$ are easy,and it is not hard to prove that the model for $12$ doesn't exist.
12.04.2015 22:22
It is obvious that the maximum number of fields is 10*9+8*7+6*5+4*3+2*1=190<14^2 => m<14, and minimum number of fields is 1*10+9*2+8*3+7*6+4*5=119<11^2 => m>10 We can find solutions for 11 and 13, but a little modulo 2 and 4 proves that m=12 is not possible
19.12.2018 19:32
Nice problem! v_Enhance wrote: Determine all integers $m$ for which the $m \times m$ square can be dissected into five rectangles, the side lengths of which are the integers $1,2,3,\ldots,10$ in some order. We will show that $m=11$ or $m=13$ are the only possibilities. Claim: We must have $m \in \{11, 12, 13\}.$ Proof: Let the rectangles have their lengths, breadths $(a_1, x_1), \cdots (a_5,x_5).$ Then $\{a_1, \cdots a_5, x_1, \cdots x_5\} \equiv \{1, \cdots 10\}.$ Hence $$m^2=a_1x_1+\cdots+a_5x_5 \le \frac{1}{2} \left( a_1^2+x_1^2+\cdots+a_5^2+x_5^2 \right)=\frac{1}{2} \left(1^2+\cdots +10^2 \right) <196$$and $$m^2=a_1x_1+\cdots+a_5x_5 \ge 5\sqrt[5]{a_1x_1\cdots a_5x_5}=5\sqrt[5]{10!}>100$$Hence $10<m<14,$ as claimed. $\square$ We will now show that $m=12$ is not possible. To do this, we try to investigate the structure of the tiling. If there are three rectangles on one side of the $m \times m$ square, then the remaining shape is a podium/staircase type octagon, which clearly can't be tilled using $2$ rectangles. Hence, all the sides of our square will share sides with exactly two rectangles. Consider the rectangle $R$ that shares a vertex with the top left vertex of the square, and assume without loss of generality that the longer side of this rectangle is along the upper side of the square. Firstly, the two rectangles $A,B$ adjacent to this one cannot obviously both be "longer" than this $R$. Also, they both cannot be shorter as the diagram shows (the blue region cannot be tilled by $2$ rectangles): [asy][asy] size(5cm); fill((1,-2.5)--(3,-2.5)--(3,-0.5)--(2,-0.5)--(2,-1)--(1,-1)--cycle,cyan); dot((0,0)); dot((2, 0)); dot((2, -1)); dot((0, -1)); draw((0,0)--(2,0)--(2,-1)--(0,-1)--(0,0)); dot((0, -2.5)); dot((1, -2.5)); dot((1, -1)); draw((0,-2.5)--(1,-2.5)--(1,-1)--(0,-1)--(0,-2.5)); dot((2, -0.5)); dot((3, 0)); dot((3, -0.5)); draw((2,0)--(3,0)--(3,-0.5)--(2,-0.5)--(2,0)); label("R",(1,-0.35), S); label("A",(2.5,-0.12), S); label("B",(0.5,-1.6), S); [/asy][/asy] $$\text{The case when both the adjacent squares are shorter than }R$$ Hence one of them is shorter and one of them is longer. So if $B$ is shorter, than $A$ is longer than $R.$ Thus, the remaining two squares can be filled in exactly one way. Thus, the tiling would form a "cycle" along the sides of the square and there would be a "core" square in the center. (see the construction for $m=11, 13$ to see this design) By a "cycle", I mean that 4 rectangles along the corners of the squares. Back to the case when $m=12,$ we note that none of the rectangles along the square's sides will have length $6,$ since it would force the adjacent rectangle to have the side length $12-6=6,$ but no number must be repeated as a side length. Similarly, it cannot have $1$ as a side length, since then the adjacent rectangle will have the side length $12-1=11>10.$ Hence $1 \times 6$ must be the dimensions of the "core" square. Now an easy case bash suffices since we can express everything in terms of just two side lengths (of the rectangles). The key idea which yields a contradiction in every case is that we will always find two equal side lengths. For $m=11,$ here is one such tilling: [asy][asy] size(5cm); //R1 dot((0,0)); dot((5,0)); dot((5,8)); dot((0,8)); draw((0,0)--(5,0)); label("5",(0,0)--(5,0),S); draw((5,0)--(5,8)); draw((5,8)--(0,8)); draw((0,8)--(0,0)); label("8",(0,8)--(0,0),W); //R2 dot((11,0)); dot((11,1)); dot((5,1)); draw((11,0)--(11,1)); label("1",(11,0)--(11,1),E); draw((11,1)--(5,1)); draw((5,1)--(5,0)); draw((5,0)--(11,0)); label("6",(5,0)--(11,0),S); //R3 dot((11,11)); dot((9,11)); dot((9,1)); draw((11,11)--(9,11)); label("2",(11,11)--(9,11),N); draw((9,11)--(9,1)); draw((9,1)--(11,1)); draw((11,1)--(11,11)); label("10",(11,1)--(11,11),E); //R4 dot((0,11)); dot((9,8)); draw((0,11)--(9,11)); label("9",(0,11)--(9,11),N); draw((9,11)--(9,8)); draw((9,8)--(0,8)); draw((0,8)--(0,11)); label("3",(0,8)--(0,11),W); //R5 label("4",(5,8)--(9,8),S); label("7",(5,1)--(5,8),E); [/asy][/asy] For $m=13,$ here is one such tilling: [asy][asy] size(5cm); //R1 dot((0,0)); dot((10,0)); dot((10,6)); dot((0,6)); draw((0,0)--(10,0)); label("10",(0,0)--(10,0),S); draw((10,0)--(10,6)); draw((10,6)--(0,6)); draw((0,6)--(0,0)); label("6",(0,6)--(0,0),W); //R2 dot((13,0)); dot((13,8)); dot((10,8)); draw((13,0)--(13,8)); label("8",(13,0)--(13,8),E); draw((13,8)--(10,8)); draw((10,8)--(10,0)); draw((10,0)--(13,0)); label("3",(10,0)--(13,0),S); //R3 dot((13,13)); dot((9,13)); dot((9,8)); draw((13,13)--(9,13)); label("4",(13,13)--(9,13),N); draw((9,13)--(9,8)); draw((9,8)--(13,8)); draw((13,8)--(13,13)); label("5",(13,8)--(13,13),E); //R4 dot((0,13)); dot((9,6)); draw((0,13)--(0,6)); label("7",(0,13)--(0,6),W); draw((0,6)--(9,6)); draw((9,6)--(9,13)); draw((9,13)--(0,13)); label("9",(9,13)--(0,13),N); //R5 label("2",(9,6)--(9,8),W); label("1",(9,6)--(10,6),S); [/asy][/asy] Hence, our claim has been proven. $\blacksquare$
15.02.2024 16:41
Difficult for P2... Step 1: bounding The minimum number of squares covered would be $1\times 10+2\times 9+3\times 8+4\times 7+5\times 6=110$ The maximum number of squares covered would be $1\times 2+3\times 4+5\times6+7\times8+9\times 10=190$ So $11\leq m\leq13$. Step 2: creating the shape Note that as the side length is greater than $10$, not a single rectangle can occupy two corners, so the four corners must be occupied by four different rectangles. Also if the other (fifth) rectangle touches the side, then one of the rectangles would share a side length with it, otherwise there would be $6$ rectangles. So the fifth rectangle must not touch the side of the square. Step 3: construction for $11$ and $13$ From now on a $m\times n$ rectangle means $m$ columns, $n$ rows. for $m=11$, $1\times 9$ on the bottom left, $8\times 2$ of the top left, $3\times 6$ on the top right, $10\times 5$ on the bottom right, leaving $7\times 4$ in the center. for $m=13$, $10\times 6$ on the bottom left, $9\times 7$ on the top left, $4\times 5$ on the top right, $3\times 8$ on the bottom right, leaving $1\times 2$ in the middle. Step 4: show that $12$ is impossible Note that if a rectangle with side length $6$ is on the edge then the other one on the edge would have a side length $6$, and if a rectangle with a side length $1$ is on edge then the other one would have a side length $11$. So the middle one (not touching the edge) would be $6\times 1$ (or $1\times 6$, but it's similar.) If so, we would need the rectangles right above/below this $6\times 1$ rectangle has row count add up to $11$. It can't be $5+6$ or $1+10$, so it's either $2+9, 3+8$ or $4+7$. and also the ones that's at the left/right would add up to $6$ If it's $4+7$ or $2+9$ then the only way then there's no way to make $6$ with the rest of the numbers. If it's $3+8$, then the left/right would be $2+4$. But by checking we know this won't work. Conclusion The only answers are $11$ and $13$.
14.09.2024 07:05
Solution from Twitch Solves ISL: The answer is that this is possible if and only if $m = 11$ or $m = 13$. Constructions for $m=11$ and $m=13$. See the figures below. [asy][asy] size(12cm); picture p11, p13; pen b = black+2.5; filldraw(p11, box((0,0), (11,11)), palegreen, b); filldraw(p11, box((0,0), (8,5)), palecyan, b); filldraw(p11, box((7,9), (11,11)), palecyan, b); filldraw(p11, box((8,0), (11,9)), palered, b); filldraw(p11, box((0,5), (7,11)), palered, b); for (int i=0; i<11; ++i) { for (int j=0; j<11; ++j) { draw(p11, shift(i,j)*unitsquare, black); } } add(p11); filldraw(p13, box((0,0), (13,13)), palegreen, b); filldraw(p13, box((0,0), (8,3)), palecyan, b); filldraw(p13, box((6,4), (13,13)), palecyan, b); filldraw(p13, box((8,0), (13,4)), palered, b); filldraw(p13, box((0,3), (6,13)), palered, b); for (int i=0; i<13; ++i) { for (int j=0; j<13; ++j) { draw(p13, shift(i,j)*unitsquare, black); } } add(shift(13,-1)*p13); [/asy][/asy] Proof the task is impossible unless $11 \le m \le 13$. The total area of the rectangles is of the form $A = a_1 b_1 + \dots + a_5 b_5$ for $(a_1, \dots, b_5)$ a permutation of $(1, \dots, 10)$. By applying the rearrangement inequality repeatedly one can prove that \[ A \le 1 \cdot 2 + 3 \cdot 4 + 5 \cdot 6 + 7 \cdot 8 + 9 \cdot 10 = 190. \]Analogously, we can get a matching lower bound \[ A \ge 1 \cdot 10 + 2 \cdot 9 + 3 \cdot 8 + 4 \cdot 7 + 5 \cdot 6 = 110. \]Since $A = m^2$ for integer $m$, it follows $11 \le m \le 13$. Proof the task is impossible for $m=12$. It remains to rule out such a tiling for a $12 \times 12$ square. We start with the following structure claim: Claim: Any tiling for $m > 10$ must either be the spiral pattern below or a reflection of it. [asy][asy] size(3cm); draw(box((0,0),(7,7)), black+1.5); draw((0,2)--(5,2), black+1); draw((5,0)--(5,4), black+1); draw((3,4)--(7,4), black+1); draw((3,7)--(3,2), black+1); [/asy][/asy] Proof. Label the square $ABCD$. Because $m > 10$, each corner of the square must be part of a different rectangle. Consider the rectangle covering $A$, and let the vertex opposite $A$ be $A'$. Define $B'$, $C'$, $D'$ similarly. We contend that no two of $A'$, $B'$, $C'$, $D'$ coincide. Indeed, if $A' = C'$, then we get the figure on the left where the two purple rectangles are part of the tiling. The remaining two ``quadrants'' must be dissected into three rectangles, but there is general a quadrant cannot be divided into either $2$ or $3$ rectangles in aw way that doesn't create two equal lengths. [asy][asy] size(7cm); picture pl; draw(pl, box((0,0),(7,7)), black+1.5); label(pl, "$A$", (0,0), dir(225)); label(pl, "$B$", (7,0), dir(315)); label(pl, "$C$", (7,7), dir(45)); label(pl, "$D$", (0,7), dir(135)); dotfactor *= 2; picture pr = rotate(0)*pl; filldraw(pl, box((0,0), (5,3)), mediummagenta, black+1.5); filldraw(pl, box((7,7), (5,3)), mediummagenta, black+1.5); filldraw(pr, box((0,0), (5,3)), mediummagenta, black+1.5); filldraw(pr, box((5,3), (7,0)), mediummagenta, black+1.5); label(pl, "$A'=C'$", (5,3), dir(135)); label(pr, "$A'=B'$", (5,3), dir(90)); dot(pl, (5,3)); dot(pr, (5,3)); add(shift(0,0)*pl); add(shift(11,0)*pr); [/asy][/asy] Meanwhile, if $A' = B'$, the two purple rectangles already obviously have a common dimension (right figure). Hence $A'$, $B'$, $C'$, $D'$ are all different points. They must each be part of some rectangle not using the corner. Moreover, every rectangle in the dissection has at least one vertex not on the boundary of the square. So the fifth rectangle must be $A'B'C'D'$ exactly. $\blacksquare$ Now on to the proof that $m = 12$ is impossible. Assume for contradiction a construction exists and refer to the spiral figure above. Note that because $12 > 1 + 10$, the side length $1$ cannot belong to any edge of the outer $12 \times 12$ square. This means that $1$ must be a side length of the center rectangle. Moreover, because the outer square has perimeter $48$, and we know $1+2+\dots+10 = 55$, the center rectangle has perimeter $7$. In other words, the inner rectangle must be $1 \times 6$ exactly. [asy][asy] size(5cm); draw(box((0,0),(12,12)), black+1.5); draw((0,2)--(5,2), black+1); draw((5,0)--(5,8), black+1); draw((4,8)--(12,8), black+1); draw((4,12)--(4,2), black+1); label("$6$", (5,4), dir(0)); label("$1$", (4.5,8), dir(90)); [/asy][/asy] Hence, we would need to partition the remaining numbers $\{2,3,4,5,7,8,9,10\}$ into eight pairs such that two pairs differ by $1$ and differ by $6$ (in the picture, the paired numbers are on opposite sides of the square). Note that $7$ must be paired with $8$ (since $7 \pm 6$ and $7-1$ are not available) and $5$ must be paired with $4$ (since $5 \pm 6$ and $5+1$ are not available). But then the remaining pairs need to have difference $6$, and there is no way to form two such pairs from $\{2,3,9,10\}$. This produces the desired contradiction.
14.09.2024 08:27
v_Enhance wrote: [asy][asy] size(12cm); picture p11, p13; pen b = black+2.5; filldraw(p11, box((0,0), (11,11)), palegreen, b); filldraw(p11, box((0,0), (8,5)), palecyan, b); filldraw(p11, box((1,9), (11,11)), palecyan, b); filldraw(p11, box((8,0), (11,9)), palered, b); filldraw(p11, box((0,5), (6,11)), palered, b); for (int i=0; i<11; ++i) { for (int j=0; j<11; ++j) { draw(p11, shift(i,j)*unitsquare, black); } } add(p11); filldraw(p13, box((0,0), (13,13)), palegreen, b); filldraw(p13, box((0,0), (8,3)), palecyan, b); filldraw(p13, box((6,4), (13,13)), palecyan, b); filldraw(p13, box((8,0), (13,4)), palered, b); filldraw(p13, box((0,3), (6,13)), palered, b); for (int i=0; i<13; ++i) { for (int j=0; j<13; ++j) { draw(p13, shift(i,j)*unitsquare, black); } } add(shift(13,-1)*p13); [/asy][/asy] I think there is a mistake for $m=11$ , there is no length $1$.
24.10.2024 05:01
Yes, you're right. Drew one of the edges in the wrong place, should be fixed now.