Library / /44 of 45

, 2008

Combinatorics Difficulty 7.2 National olympiad, round 2 Prove it Slovenia

Anja has a number of $1 \times 1$ square tiles $\Box$ , while Bojan has the L-shaped tiles $\Box\Box$ . They take turns putting their tiles onto a rectangular board, one tile at a time. Anja wins if Bojan cannot fit another one of his tiles onto the board when his turn comes despite there being squares left uncovered. Otherwise, Bojan wins. Prove:

a) given a $6 \times 9$ board, Bojan cannot win regardless of who has the first move;

b) given a $8 \times 8$ board, can Bojan put the tiles onto the board in a way that insures his winning, regardless of how Anja plays and who had the first move.

(Note: All tiles have to lie entirely on the board and they must not cover any of the other tiles).

Solution

(a) A $6 \times 9$ board has $54$ squares. If Bojan wants to win, they have to cover the entire board, because Anja can always fit in another one of her tiles as long as there are empty squares left. After Bojan and Anja each put $13$ tiles onto the board there will be two squares left uncovered. Regardless of who made the first move, the board will not be covered entirely and Anja will win.

(b) An $8 \times 8$ board can be divided into $16$ $2 \times 2$ squares as shown in the figure.

If Anja is the one to start, she puts one of her tiles into one of these $2 \times 2$ squares. Bojan can now use one of his tiles to fill this square. He can do this every time his turn comes, so eventually they cover the entire board and Bojan wins.

If Bojan is the one to start, he puts one of his tiles into one of the $2 \times 2$ squares. If Anja should happen to cover the remaining small square, he can choose another one of the $2 \times 2$ squares for his next move. But if, on the other hand, Anja does not cover the remaining small square, Bojan should proceed by covering whatever other $2 \times 2$ square she chose. After $15$ moves there is either one $2 \times 2$ square left uncovered or of the four remaining squares three lie inside the same $2 \times 2$ square. Either way Bojan can put one of his tiles onto the board and Anja is forced to fill the last remaining square, ensuring Bojan's victory.

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.