Browse · MathNet
PrintSlovenija 2008
Slovenia 2008 counting and probability
Problem
Two players share a pile of coins, alternating in taking one coin off the pile and placing it on any empty square of a chessboard. The player who puts the coin onto the board in such a way that together with three other coins already on the board it forms a rectangle with sides parallel to the edges of the board, wins. Which of the players has the winning strategy – the first or the second?
Solution
The second player has the winning strategy. He or she can arrange the columns into 1004 pairs with columns 1 and 2 forming the first pair, columns 3 and 4 forming the second pair, and so on, with columns 2007 and 2008 forming the final pair. Whenever the first player puts a coin into one of the columns, the second player should put a coin into the second column of that pair and on the same line as the first. After at most 1004 moves the first player will be forced to put a coin into a column that already contains one other coin. The second player will then be able to form the rectangle and win.
Final answer
the second player
Techniques
Games / greedy algorithmsPigeonhole principle