[Math] Dividing a rectangle into squares

combinatorics

This is a rather simple question intuitively, but I can't seem to find a rigorous explanation for this:
suppose we are diving a rectangle into some number of equal sized squares, then they must all be aligned together(such that we can produce theses squares by performing horizontal and vertical cuts on the rectangle).

It makes sense to me, since if we have misalignment, then eventually we are going to reach a position where we can't fit the square. However, this assumes that the squares are originally aligned in the first place…
Any rigorous explanation/counter example to this?

Best Answer

I think it should be obvious given that you need to put a square in the corner in the rectangle (if you move it a distance away from one of the sides of the corner, that is less than the length of the square, you'll leave an unfillable gap). And, with that first square in place, you just created a new corner to be filled up, and again you need to put a square exactly in that spot ... etc. This way, it should be clear that as you go along one side of the rectangle, you need to align all squares, and once that first row is done, the same story applies to the next row, etc. .. until the rectangle is all tiled.

Related Solutions

[Math] Fewest steps to reach $200$ from $1$ using only $+1$ and $×2$

Look at what the operations $[+1]$ and $[\times 2]$ do to the binary expansion of a number:

$[\times 2]$ appends a $0$, and increases the length by one, leaving the total number of $1$'s unchanged;
if the final digit is $0$, then $[+1]$ increases the number of $1$'s by one, but doesn't change the length;
if the final digit is $1$, then $[+1]$ doesn't increase the total number of $1$'s (it may in fact decrease it), and doesn't increase the total length by more than $1$.

Therefore, with a single key press:

you can increase the length by one, but this won't increase the number of $1$'s;
you can increase the number of $1$'s by one, but this won't increase the length.

The binary expansion of $200$ is $200_{10}=11001000_2$. This has three $1$'s, and a length of eight. Starting from $1$, we must increase the length by seven, and increase the number of $1$'s by two. So this requires at least nine steps.

Recurrences for tilings part 1

Have I made any mistakes, and if so, what did I do wrong?

Your recurrences look fine to me.

Also, how can I get the recurrence $a_n = 4a_{n-2} - a_{n-4}$ directly for 3?

To be honest, I think your recurrence is better, since it's more intuitively obvious / less error-prone. :) But to answer your question, here is one way...

Consider the ways to fill the first $2$ columns (of $3$ squares each). There are $3$ ways to fill them using $3$ complete dominoes. So that accounts for $3a_{n-2}$. Besides these, they can also be filled using $2$ dominoes and $2$ half-dominoes, like this

AA.......
BCC......
BDD......

and its reflection. So we need to argue that the number of ways to fill the remaining ... above (incl. the reflected picture) amount to $a_{n-2} - a_{n-4}$ ways, for the desired total of $a_n = 4a_{n-2} - a_{n-4}$.

Now consider any $3 \times (n-2)$ rectangle, which can be filled in $a_{n-2}$ ways. Consider its first column. Either (case A) there are $3$ half-dominoes (no. of ways $= a_{n-4}$), or (case B) there is a full domino plus a half-domino. So no. of ways for case B $= a_{n-2} - a_{n-4}$, but this is exactly the same as filling the ... in the picture, once you consider C+D to be the full domino in that first column of the $3 \times (n-2)$ rectangle. $\square$

Best Answer

Related Solutions

[Math] Fewest steps to reach $200$ from $1$ using only $+1$ and $×2$

Recurrences for tilings part 1

Related Question