Problem of the Day: June 10

Luke and Andrew play a game on a square board consisting of nxn white tiles, where n >=2. Luke moves first, and the players alternate taking turns. A move consists of picking a square consisting of 2x2 or 3x3 white tiles and coloring all those tiles black. The first player who cannot find any such squares loses. Show that for all n, Luke has a winning strategy for the game.

(Give solutions in comments to this post. On Wednesday I'll post some combination of my own solution and the most elegant approaches suggested by others.)

Edited to add solution:
Two approaches that are often helpful in tackling "winning strategy" problems are:
1. Strategy stealing
2. Mirroring strategies
Strategy stealing is a bit tempting here because there is no possibility of a draw, which means that if strategy stealing shows that Andrew can't have a winning strategy (because Luke could steal it), Luke then must have a winning strategy. On the other hand, it's hard to see what the neutral move could be that would effectively transform Andrew into the "first player" position.

So let's consider mirroring strategies. This approach shows up more often in constructing winning strategies for the second player. But when it's used for the first player, that's sometimes because there's a central symmetry-breaking position that needs to be claimed.

That's the key here, and one insight is thinking about the fact that both 2x2 and 3x3 moves are permitted. Luke can always claim the center of the board in his first move. If n is even, he plays 2x2 in the center, and if n is odd, he plays 3x3 in the center.

After that, Luke's approach is to mirror Andew's plays across some symmetry in the game. The key then is finding the right symmetry. The obvious candidates -- vertical or horizontal symmetry -- don't work, because Andrew can play across those lines of symmetry. But rotational symmetry works. If Luke always plays Andrew's move rotated 180 degrees, then he will always have a play available, and thus will win the game.

(Problem source: Niels Henrik Abel Math Competition, Final Round, 2007/2008 #2b)


Comments

Post a Comment

Popular posts from this blog

Problem of the Day: June 21

A magical castle has n identical rooms, each of which contains m distinguishable doors arranged in a line. In each room i<n, there is one door that takes you to room i+1, and all other doors take you back to room 1. In room n, there is one door that takes you out of the castle, and all other doors take you back to room 1. When you go through a door into a room, you are unable to tell which room of the castle is is (and there is no way of marking rooms). You also cannot tell which doors have been opened before. Determine for which pairs (n,m) there is a strategy that guarantees escape from the castle, and explain the strategy. Edited to add solution: Here's a starting thought: if we could reliably know when we are in room 1, we could solve the problem easily for any n and m. We would then: 1. Enumerate all length n sequences from the alphabet {1,...,m}. 2. For each sequence in that list, (i) get to room 1, and (ii) then follow that sequence. Eventually we'd get to the c...
Read more

Problem of the Day: June 12

Find all positive integers x, y, and z satisfying x 2 + y 2 + z 2 = 2xyz. (As usual, give solutions in comments to this post. On Friday I'll post some combination of my own solution and the most elegant approaches suggested by others.) Edited to add solution : If x 2 + y 2 + z 2 = 2xyz, then x 2 + y 2 + z 2 must be even. Thus there are two cases to consider: 1. One of x, y, z is even and two are odd. 2. All three of x, y, and z are even. Start with case 1. Assume (without loss of generality) that x is even, so x = 2a. Then we have 4a 2 + y 2 + z 2 = 4ayz. But then y 2 + z 2 must be a multiple of 4. But odd numbers are always 1 mod 4, so this is impossible. Thus case 1 can't be achieved. Now consider case 2. We have x=2a, y=2b, and z=2c. Thus 4a 2 + 4b 2 + 4c 2 = 16abc, or a 2 + b 2 + c 2 = 4abc. So let's now focus on this new equation. Again we  need the sum to be even, so we need either one or three even numbers. But one even and two odd...
Read more