A square is divided into congruent rectangles with sides of integer lengths. A rectangle is important if it has at least one point in common with a given diagonal of the square. Prove that this diagonal bisects the total area of the important rectangles
Problem
Source:
Tags: geometry, rectangle, rotation, induction, combinatorics unsolved, combinatorics
21.02.2011 00:27
Edit: see below.
17.08.2011 04:49
@applepi2000: You have incorrectly assumed that all rectangles must have the same orientation; some of the small rectangles may be rotated by $90^o$. Mods, can this problem be moved to olympiad combinatorics? I would definitely not consider this problem pre-olympiad.
01.09.2013 02:28
We can view directly the square as a $N\times N$ board divided in unit squares, tiled by $a\times b$ and $b\times a$ rectangles. The board is partitioned into $2N-1$ diagonals parallel to the given diagonal, $D_1,D_2,\ldots, D_{N-1},D_N,D_{N+1},\ldots, D_{2N-2},D_{2N-1}$ consisting of $1,2,\ldots N-1,N,N-1,\ldots, 2,1$ unit squares respectively. We say that a rectangle begins at $D_i$ if the left uppermost unit square of that rectangle belongs to $D_i$. Let $c_i$ be the number of rectangles that begin at $D_i$. Lemma: For each $1\leq i \leq 2N-1$, $c_i$ doesn't depend on the tiling. Proof: Given a rectangle, we focus on how many unit squares on each diagonal are covered by this rectangle. This only depends on the diagonal where the rectangle begins, not on the left uppermost square of the rectangle or on the fact that it is an $a\times b$ or $b\times a$ rectangle. Moreover, if $i<j$, a rectangle beginning at $D_j$ doesn't cover unit squares on $D_i$. We prove the lemma by induction on $i$. Clearly, $c_1=1$. Now, if $c_j$ doesn't depend on the tiling for every $j<i$, we will prove that $c_i$ doesn't depend on the tiling. The squares on $D_i$ are covered by rectangles that begin in $D_j$ with $j\leq i$. We know that the number of unit squares on $D_i$ covered by rectangles beginning in $D_j$ with $j<i$ doesn't depend on the tiling. So the number of squares on $D_i$ covered by rectangles beginning on $D_i$ doesn't depend on the tiling. But that number is $c_i$ $\blacksquare$ The fact that a rectangle is important depends only on which diagonal it begins. In case it is important, the area of that rectangle that lies over $D_N$ also depends only on which diagonal it begins. So the total area of the important rectangles that lies over $D_N$ doesn't depend on the tiling. Finally, by a simmetry argument the problem follows: reflecting the tiling by $D_N$ we get another such tiling of the square. A rectangle is important in the new tiling iff it was important in the old tiling. The total area of the important rectangles that was under the diagonal in the old tiling is exactly the total area of the important rectangles that is over the diagonal in the new tiling. This completes the proof.
Attachments: