Maths Olympiad Prep

Library / /169 of 196

Combinatorics Difficulty 6.1 National Olympiad Prove it Soviet Union

Problem:

a. A 6×66 \times 6 board is tiled with 2×12 \times 1 dominos. Prove that we can always divide the board into two rectangles each of which is tiled separately (with no domino crossing the dividing line).

b. Is this true for an 8×88 \times 8 board?

Solution

Solution:

a.
We say a domino bridges two columns if half the domino is in each column. We show that for 0<n<60 < n < 6 the number of dominoes bridging columns nn and n+1n+1 must be at least 22 and even.

Consider first n=1n = 1. There cannot be 33 dominos entirely in column 11, or it would be separately tiled. So there must be at least one domino bridging columns 11 and 22. The number must be even, because it must equal the number of squares in column 11 (even) less twice the number of dominoes (entirely) in column 11.

Now suppose it is true for n<5n < 5 and consider column n+1n + 1. There must be at least one domino bridging columns n+1n + 1 and n+2n + 2, or columns 11 thru n+1n + 1 would be separately tiled. The number must be even, because it must equal the number of squares in column n+1n + 1 (even) less the number bridging nn and n+1n + 1 (even) less twice the number entirely in the column.

So in total there are at least 5×2=105 \times 2 = 10 dominos bridging columns. By the same argument there are at least another 1010 bridging rows, but there are only 1818 dominoes in total.

b.
No. For example:
1 2 3 3 1 1 2 2 1 2 1 2 2 3 3 1 3 3 1 3 1 2 4 1 1 2 2 3 1 2 4 3 1 3 3 2 2 1 2 3 3 2 1 1 4 1 2 1 3 2 3 2 4 3 3 1 1 1 3 2 1 1 2 2

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.