Dominoes

How many 1 n 100 1\leq n\leq 100 are there such that it is possible to tile an n × n n\times n board with the same number of horizontal and vertical 1 × 2 1\times 2 dominoes?


The answer is 25.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Patrick Chatain
Jun 27, 2016

Note that as each domino takes up 2 squares then n n must be even

Now take an even n × n n\times n board and color it as in figure 1. Note that every vertical domino will take up 1 and only 1 shaded square while every horizontal domino will take up either 0 or 2 shaded squares. As there are an even number of shaded squares then we must have an even number of vertical dominoes. Say we have 2 k 2k vertical dominoes.

Now as the number of vertical dominoes equals that of horizontal dominoes we must have 2 k 2k horizontal dominoes. Thus we have a total of 4 k 4k dominoes and as each domino takes up 2 squares we have a total of 8 k 8k squares taken up. Therefore the number of squares in the board must be a multiple of 8.

Thus n 2 n^2 must be a multiple of 8 so n n must be a multiple of 4. Now if n n is a multiple of 4, say n = 4 m n=4m for some positive integer m m then we can divide the board into m 2 m^2 4 × 4 4\times 4 boards each which can be tiled with 4 horizontal and 4 vertical dominoes as shown in figure 2. So we can achieve the condition if and only if n n is a multiple of 4.

So our answer is all the multiples of 4 from 1 to 100 25 \implies \fbox{25}

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...