In a $2^n \times 2^n$ square with $n$ positive integer is covered with at least two non-overlapping rectangle pieces with integer dimensions and a power of two as surface. Prove that two rectangles of the covering have the same dimensions (Two rectangles have the same dimensions as they have the same width and the same height, wherein they, not allowed to be rotated.)
Problem
Source: Netherlands Team Selection Test 2016 Day 1-Problem 2
Tags: combinatorics, geometry, rectangle
ThE-dArK-lOrD
23.09.2016 22:19
We suppose to the contrary that we can covered $2^n\times 2^n$ with some relatively distinct dimension rectangles.
Among all side length of every rectangles, suppose that the minimum is $2^p$
Define set of rectangles "adjacent" iff when there exist rectangle $2^p\times P$ which covered by such rectangle(s) (all of them must have at least one side length equal to $2^p$)
We "merge" each "adjacent" set of rectangles into one rectangle, then consider one of obtained rectangle, let it dimension is $2^p\times L_1$
WLOG that the $2^p\times L_1$ rectangles have vertical side length $2^p$
Then we note that LemmaIf $2^{a_1}+2^{a_2}+...+2^{a_c}=2^{b_1}+2^{b_2}+...+2^{b_c}$ for some $c\in \mathbb{Z}^+$ and $a_1,a_2,...,a_c,b_1,b_2,...,b_c\in \mathbb{Z}^+$ with $c_0=\min \{ a_1,a_2,...,a_c,b_1,b_2,...,b_c\}$, then there exist two element in $\{ a_1,a_2,...,a_c,b_1,b_2,...,b_c\}$ that equal to $c_0$
(Prove of the Lemma is trivial)
Consider left side of $2^p\times L_1$, let the line contain that side is $l$ (which have length $2^p$), since we have merge all adjacent cell, so there exist another rectangle(s) (or the border of $2^n\times 2^n$) which one of their sidelie on $ l$, we use the lemma to get that there exist another rectangle which at least of side length is $2^p$ and the side lie on $l$, let that rectangle have dimension $2^p\times L_2$ (See the figure below)
Then we consider another side of $2^p\times L_2$ and do the same argument.
But obviously, we can't do it infinite times, so it must end when there exist a "cycle" of side length $2^p$ (probably not complete the cycle at $2^p\times L_1$)
Suppose that the rectangles in the "cycle" have dimensions $2^p\times L_1,L_2,...,L_z$
This mean there exist $c_1,c_2,...,c_z \in \{ -1,1\}$ such that $\sum_{i=1}^{z}{c_iL_i} =0$
But note that for each of $2^p\times L_i$ consist of some (or a) rectangle before we "merge" them, so they are all have pairwise distinct other side length (since already one of there side length is $2^p$)
Then the Lemma give us a contradict with our assumption.
P.S. I'm not sure that it's correct, plz check it.
Attachments:
math90
25.09.2016 08:06
Among all side length of rectangles in the partition, suppose that the minimum is $2^p$.
Number every corner of unit square with two coordinates form $0$ t $2^n$, left-right and up-down.
If we remove the rectangle from the upper border and continue until we remove all rectangles, we see that all corners of the rectangles have both coordinates divisible by $2^p$.
Hence we can reduce the problem to $2^{n-p}\times 2^{n-p}$ square, with minimal length of rectangle equal to $1$.
Hence we can assume that we have $2^n\times 2^n$ square, with minimal length of rectangle equal to $1$.
Let $s$ be the amount of all rectangles in even rows, minus the amount of all rectangles in odd rows.
WLOG there exists a rectangle $R$ whose vertical size equals $1$. let its horizontal size be $2^k$.
We see that $R$ contributes $2^k$ or $-2^k$ to $s$.
Every rectangle whose vertical size does not equal to $1$ contributs $0$ to $s$.
Hence only rectangles with vertical size $1$ affect $s$.
Let all rectangles with vertical size $1$ be $R_1,\dots,R_t$, with horizontal sizes $2^{i_1},\dots,2^{i_t}$.
Since $s$ equals $0$ when thhe square is full, there exist $e_j=\pm 1$ such that $\sum_{j=1}^t e_j 2^{i_j}=0$.
Let $c=\min\{i_1,\dots,i_t\}$. If only one index equals $c$, then RHS is divisible by $2^c$ but not by $2^{c+1}$, a contradiction.
Hence there exist two indices which equal to $c$. Hence there exist two rectangles $1\times 2^c$.
Thing__2
14.08.2019 17:52
Let $R$ be one of the rectangles used in the tiling s.t. $R$ has the (possible joint) minimum area $A$ of these rectangles, with width $2^a$ and height $2^b$. Of the rectangles with area $A$, let $R$ be the one with maximal width and we assume, for contradiction, that the dimensions of $R$ are unique amongst those used in the tiling. Label the rows and columns of the square $1, 2, ..., 2^n$, going from bottom to top and left to right, respectively. Consider the colouring where a unit square with coordinates $(x, y)$ is shaded iff $2^a \mid x$, giving columns of shaded squares $2^a$ apart. Clearly $R$ is on exactly 1 of the shaded columns so covers exactly $2^b$ shaded squares. Claim: the number of shaded squares covered by a rectangle of area at least $2A$ is divisible by $2^{b+1}$ Proof: Let $Q$ be such a rectangle have width $2^c$ and height $2^d$, where $c + d > a + b$ as $2^{c+d} > 2^{a+b}$ Case 1, $c > a$: then $Q$ covers exactly $2^{c-a}$ shaded columns, and covers exactly $2^d$ squares in each, giving a total of $2^{c+d-a}$ shaded squares which is divisible by $2^{b+1}$ as their ratio is $2^{c+d-a-b-1}$, where the exponent is a non-negative integer. Case 2, $d > b$: then if $Q$ is on any shaded columns the number of shaded squares will be $2^d$, clearly divisible by $2^{b+1}$ and if not then it covers 0 shaded squares, also divisible by $2^{b+1}$. This finishes the proof of the claim. We now consider the number of shaded squares that a rectangle $T$ of area $A$, width $2^e$ and height $2^f$ can cover. Note $a+b=e+f$ and $e < a$ as $R$ has unique maximal width of rectangles with area $A$. Consequently $f > b$. $T$ is either in 0 or 1 shaded columns. If it is in 0 then the number of shaded squares 0 and if it is in 1 then the number of shaded squares is $2^f$. Note that either way, the number of shaded squares is divisible by $2^{b+1}$. We deduce that all rectangles used in the tiling that are not $R$ cover a number of shaded squares divisible by $2^{b+1}$, where $R$ uses $2^b$. The total number of shaded squares is $2^{2n-a}$. The only way this is not divisible by $2^{b+1}$ is if $a=b=n$, which is impossible as then there is only one rectangle in the square, hence $2^{b+1}$ divides the total number of shaded squares. However, $0 \equiv$ total number of shaded squares$\mod2^{b+1}$ = sum over the rectangles of the number of shaded squares in each $\equiv 2^b + 0 + 0 + 0... + 0\mod2^{b+1} = 2^b$, a contradiction, so our assumption that $R$ had unique dimensions compared to others used in the tiling was false.