From $2008 \times 2008$ square we remove one corner cell $1 \times 1$. Is number of ways to divide this figure to corners from $3$ cells odd or even ?
Problem
Source: St Petersburg Olympiad 2009, Grade 11, P4
Tags: combinatorics
talkon
27.10.2017 15:57
We will mainly exploit symmetry arguments here. In fact we will find the parity of the number of ways to divide into L-trominoes an $n\times n$ board minus a corner square for every $n\geq 2$.
The answer is $\text{odd}$ if $n$ is a power of $2$, and $\text{even}$ otherwise.
In particular, for $n=2008$, the answer is $\boxed{\text{even}}$.
Solution. First, call a shape like this with $n$ rows an $n$-staircase, and let $p(n)$ denote the # of ways to divide an $n$-staircase into L-trominoes.
[asy][asy]
unitsize(12);
draw((0,0)--(0,5));
draw((0,0)--(5,0));
for( int i = 1; i < 6; ++i ){
draw((i,0)--(i,6-i));
draw((0,i)--(6-i,i));
}
[/asy][/asy]
Also let $q(n)$ denote the # of ways to divide an $n\times n$ board minus a corner into L-trominoes.
The staircase is useful for the following fact:
Fact 1. $q(n) \equiv p(n-2) \pmod 2$ for every $n$.
Proof. Note that an $n\times n$ board minus a corner has a diagonal axis of symmetry.
Any way to divide the board-minus-corner into L-trominoes that isn't symmetric along this axis can be paired with its mirror image.
Hence the parity must be equal to the parity of # of ways to divide the board-minus-corner symmetrically.
This forces the placement of L-trominoes along the axis like this:
[asy][asy]
unitsize(12);
for( int i = 0; i < 7; ++i ){
draw((i,0)--(i,7-i));
draw((0,i)--(6-i,i));
draw((7-i,7)--(7-i,i+1));
draw((7,7-i)--(i,7-i));
}
[/asy][/asy]
Therefore the # of ways to divide the remaining region symmetrically (along the diagonal) is exactly the # of ways to divide an $n-2$-staircase.
Now that we've reduced the problem to a problem about staircases, we continue by essentially the same argument, where we note that the $n$-staircase also has a diagonal axis of symmetry for every $n$.
Fact 2. $p(n)$ is even for $n$ odd.
Proof. If $n$ is odd then it's impossible to divide an $n$-staircase in a way that's symmetrical along the axis, since the axis will have $\frac{n+1}{2}$ squares while the adjacent diagonals have only $\frac{n-1}{2}$ squares, so any way to divide an $n$-staircase can be paired off with its reflection.
Fact 3. $p(n)\equiv p\left(\frac{n-2}{2}\right)\pmod 2$ for $n\geq 2$ even.
Proof. As always, we only need to consider symmetrical ways to divide.
Symmetry forces the following placements of trominoes:
[asy][asy]
unitsize(12);
draw((0,0)--(0,6));
draw((0,0)--(6,0));
for( int i = 1; i < 4; ++i ){
draw((i,i)--(i,7-i));
draw((i,i)--(7-i,i));
draw((i,0)--(i,i-1));
draw((0,i)--(i-1,i));
draw((7-i,0)--(7-i,i));
draw((0,7-i)--(i,7-i));
}
[/asy][/asy]
So we're left with dividing a shape that is two $\frac{n-2}{2}$-staircases sticked together. This shape, again, has an axis of symmetry, so we only need to count the # of symmetrical ways to divide such a shape. This is clearly just the number of ways to divide a $\frac{n-2}{2}$-staircase.
By substituting in $q(n+2)$ for $p(n)$ in the previous facts, we have $q(n) \equiv 0\pmod 2$ for every odd $n\geq 3$, and $q(n)\equiv q\left(\frac{n}{2}\right)$ for every even $n$. Now note that $q(2)$ is obviously $1$ which is odd to get that $q(n)$ is odd iff $n$ is a power of $2$. $\blacksquare$