Maths Olympiad Prep

Library / /4 of 4

Combinatorics Difficulty 6.5 National olympiad Prove it North Macedonia

A domino is a 2×12 \times 1 or 1×21 \times 2 tile. Determine in how many exactly n2n^2 dominoes can be placed without overlapping on a 2n×2n2n \times 2n chessboard so that every 2×22 \times 2 square contains at least two uncovered unit squares which lie in the same row or column.

Solution

The answer is (2nn)2\binom{2n}{n}^2.

Divide the chessboard into 2×22 \times 2 squares. There are exactly n2n^2 such squares on the chessboard. Each of these squares can have at most two unit squares covered by the dominos. As the dominos cover exactly 2n22n^2 squares, each of them must have exactly two unit squares which are covered, and these squares must lie in the same row or column.

We claim that these two unit squares are covered by the same domino tile. Suppose that this is not the case for some 2×22 \times 2 square and one of the tiles covering one of its unit squares sticks out to the left. Then considering one of the leftmost 2×22 \times 2 squares in this division with this property gives a contradiction.

Now consider this n×nn \times n chessboard consisting of 2×22 \times 2 squares of the original board. Define AA, BB, CC, DD as the following configurations on the original chessboard, where the gray squares indicate the domino tile, and consider covering this n×nn \times n chessboard with the letters AA, BB, CC, DD in such a way that the resulting configuration on the original chessboard satisfies the condition of the question.

Note that then a square below or to the right of the containing an AA or BB must also contain an AA or BB. Therefore the (possibly empty) region consisting of all squares containing AA or BB abuts the lower right corner of the chessboard and is separated from the (possibly empty) region consisting of all squares containing a CC or DD by a path which goes from the lower left corner to the upper right corner of this chessboard and which moves up or right at each step.

A similar reasoning shows that the (possibly empty) region consisting of all squares containing an AA or DD abuts the lower left corner of the chessboard and is separated from the (possibly empty) region consisting of all squares containing a BB or CC by a path which goes from the upper left corner to the lower right corner of this chessboard and which moves down or right at each step.

Therefore the n×nn \times n chessboard is divided by these two paths into four (possibly empty) regions that consist respectively of all squares containing AA, BB, CC, or DD. Conversely, choosing two such paths and filling the four regions separated by them with AAs, BBs, CCs and DDs counterclockwise starting at the bottom results in a placement of the dominos on the original board satisfying the condition of the question.

As each of these can be chosen in (2nn)\binom{2n}{n} ways, there are (2nn)2\binom{2n}{n}^2 ways the dominos can be placed.

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 and solution reproduced as published; topic and difficulty added by this site.