1
$\begingroup$

So I'm trying to solve this problem and I think I'm on the write track, but my proof relies on a domino being divisible by 2, which I don't think is correct.

The problem: Prove that a $2^n \times 2^n$ checkerboard can be covered exactly by dominoes (a domino is a rectangle consisting of two adjacent squares). Give proof by induction.

A checkerboard must always have an identical # of black and white squares in order to be tiled by dominoes. Assume a checkerboard with $N$ squares will always have $N/2$ black squares and $N/2$ white squares, so it can be tiled with dominoes.

My Basis: $P(1)=2^1 \times 2^1 = 4$ squares, giving us 2 black squares and 2 white squares.

Inductive Hypothesis: $P(k) = 2^k \times 2^k$

Need to show: $P(k+1)=2^{k+1} \times 2^{k+1}$

To increase the size of the $2^k \times 2^k$ checkerboard, you need to add 2 squares to both the height and width of the checkerboard. So, $2(2^k) \times 2(2^k)$ is increasing the size of the checkerboard, and will always provide an even number of squares, which creates an identical number of black and white squares on the checkerboard.

$2(2^k) \times 2(2^k) = 2^{k+1} \times 2^{k+1}$

Therefore, a $2^n \times 2^n$ checkerboard can always be tiled by dominoes for any $n\in\mathbb N$.

Is this correct? I feel like I'm all over the place with this proof, and am not sure if having a checkerboard be divisible by 2 actually proves that I'll get an identical number of black and white squares.

Thanks!

$\endgroup$
8
  • 1
    $\begingroup$ You're right to be skeptical, on two counts: (1) while it's true that any shape that can be tiled will have equal numbers of black and white squares, the opposite isn't at all obvious and you can't assume it for your proof. Instead, you'll want to exhibit a specific tiling. (2) Adding two squares to both height and width gives you a (2^n+2)x(2^n+2) board, not a 2(2^n)x2(2^n) board. $\endgroup$
    – Steven Stadnicki
    Commented Mar 16, 2013 at 19:05
  • $\begingroup$ A 2^0 x 2^0 checkerboard has one filed and can therfore not be covered with dominos. For n>0 it cab it covered. $\endgroup$
    – MrSmith42
    Commented Mar 16, 2013 at 19:07
  • 1
    $\begingroup$ Black and white is not relevant. And for the induction step the size of the board is doubled in each direction, we are not adding two rows and $2$ columns. Proof is not correct. Result is really easy, so easy that I think the real question is different. (Any $a\times b$ board where at least one of $a$ or $b$ is even can be tiled.) $\endgroup$
    – André Nicolas
    Commented Mar 16, 2013 at 19:08
  • $\begingroup$ Here's a hint towards a proper inductive proof: how can you split a $2^{k+1}\times2^{k+1}$ checkerboard into some number of $2^k\times 2^k$ boards? And if you have tilings of those $2^k\times2^k$ boards, how can you 'staple them together' into a tiling of the $2^{k+1}\times2^{k+1}$ board? $\endgroup$
    – Steven Stadnicki
    Commented Mar 16, 2013 at 19:10
  • 1
    $\begingroup$ @ Andre Nicolas Maybe the simpleness of it is why I'm having so much trouble. This is the question. I just don't know how to write into words that as the checkerboard expands, we're just adding another chunk of checkerboard to it that's already able to be tiled by dominoes. Therefore, we can always tile the checkerboard as it expands. $\endgroup$
    – user56763
    Commented Mar 16, 2013 at 19:17

1 Answer 1

Reset to default
3
$\begingroup$

HINT: In the figure below, each of the squares $A,B,C$, and $D$ is a $2^k\times 2^k$ checkerboard. How big is the whole board?

enter image description here

$\endgroup$
1
  • $\begingroup$ In other words, use the fact that if a figure $Y$ can be covered by copies of figure $X$, and a figure $Z$ can be covered by copies of figure $Y$, then $Z$ can be covered by copies of $X$ (where $X$ is a domino). $\endgroup$
    – Marc van Leeuwen
    Commented Mar 16, 2013 at 19:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .