Maths Olympiad Prep

Library / /60 of 60

Combinatorics Difficulty 7.3 National olympiad, round 2 Prove it South Africa

Two players alternate placing 2×12 \times 1 tiles, with no overlap, on a 5×55 \times 5 chessboard until no player can place a tile.
A number of 1×11 \times 1 squares remain empty.
Figure 1

a) Prove that there must be an odd number of empty squares remaining.

b) Of the empty squares remaining, are more coloured black or white?

c) What is the maximum number of remaining squares?

Solution

a. The chessboard contains an odd number of squares and every time a 2×12 \times 1 tile is placed, the number of open squares decreases by 22, an even number. Hence the number of remaining squares is always an odd number (odd minus even is odd).

b. Before any tile is placed, there are 1313 black squares and 1212 white squares. Every time a tile is placed, the tile covers one black square and one white square, so the number of open black squares and open white squares both decrease by 11. Since there is one more black square than white squares at the start, there will be one more black square than white squares at the end.

c. The following arrangement shows 77 empty 1×11 \times 1 squares.
Figure 2

Assume for a contradiction that it is possible to have more than 77 empty squares. Since there must be an odd number, there are at least 99 empty squares.

Divide the board into four 2×32 \times 3 rectangles and one 1×11 \times 1 centre square:
Figure 3

If the top left 2×32 \times 3 rectangle had 33 empty squares, then these three empty squares must be touching diagonally, and hence so must the three covered squares. This means that either A1A1 is covered and B1B1 and A2A2 are empty (impossible with 1×21 \times 2 tiles) or B1B1 is covered and A1A1, B2B2 and C1C1 are empty (again impossible). This means that this rectangle can contain at most 22 empty squares. A similar argument shows that all of the 2×32 \times 3 rectangles have maximum two empty squares. However, this means that to get 99 empty squares in total, all four rectangles must have exactly two empty squares, and in addition the central square must be empty. It follows that the white squares C2C2, B3B3, D3D3 and C4C4 must all be covered.

Now, from part (b) we know that of the 99 empty squares, 55 must be black and 44 white. The only remaining white squares are A2A2, A4A4, B1B1, B5B5, D1D1, D5D5, E2E2, E4E4, of which four must be empty. None of the pairs (A2,B1)(A2,B1), (A4,B5)(A4,B5), (D1,E2)(D1,E2) and (D5,E4)(D5,E4) can be empty, since that would force the corner square also empty, a contradiction. Hence exactly one in each of the above mentioned pairs is empty, and hence the three black squares surrounding it must be covered. For the first white square, this forces three black squares to be covered, and for each of the remaining three white squares, at least two additional black squares are covered, leaving at most 13(3+2+2+2)=413 - (3 + 2 + 2 + 2) = 4 black squares empty, which contradicts the fact that 55 black squares must be empty.

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.