Browse · MathNet
PrintSlovenija 2008
Slovenia 2008 counting and probability
Problem
Anja has a number of square tiles , while Bojan has the L-shaped tiles . 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 board, Bojan cannot win regardless of who has the first move;
b) given a 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).
a) given a board, Bojan cannot win regardless of who has the first move;
b) given a 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 board has 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 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 board can be divided into squares as shown in the figure.
If Anja is the one to start, she puts one of her tiles into one of these 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 squares. If Anja should happen to cover the remaining small square, he can choose another one of the 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 square she chose. After moves there is either one square left uncovered or of the four remaining squares three lie inside the same 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.
(b) An board can be divided into squares as shown in the figure.
If Anja is the one to start, she puts one of her tiles into one of these 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 squares. If Anja should happen to cover the remaining small square, he can choose another one of the 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 square she chose. After moves there is either one square left uncovered or of the four remaining squares three lie inside the same 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.
Techniques
Games / greedy algorithmsInvariants / monovariants