11th Brazil 1989 Problem 4 A and B play a game. Each has 10 tokens numbered from 1 to 10. The board is two rows of squares. The first row is numbered 1 to 1492 and the second row is numbered 1 to 1989. On the nth turn, A places his token number n on any empty square in either row and B places his token on any empty square in the other row. B wins if the order of the tokens is the same in the two rows, otherwise A wins. Which player has a winning strategy? Suppose each player has k tokens, numbered from 1 to k. Who has the winning strategy? Suppose that both rows are all the integers? Or both all the rationals?
Solution The only way B can lose is if he runs out of space to put his tokens. Clearly he cannot run out of space with the rationals, because there is always a rational between any two given rationals. Similarly, he should not run out of space with all the integers. He just copies A in the other row, so that the tokens numbered k are always placed on the same number in each row. Note that B will lose if he does not space his tokens widely enough. Call the rows R and S, so that Sn denotes the number n in row S. Suppose A plays 1 on R5, then 2 on R6. If B plays 1 on S5 and 2 on S7, then he loses, because A swaps rows and plays 3 on S6. However, B does not need to make this mistake, so A can only force a win by always playing in the longer row, until B runs out of space to match him in the shorter row. So A places each token as centrally as possible in one the shortest gap. B must match him. The table below shows the size of the shortest gap after each play. after 1989 1492 1 994 745 2 496 372 3 247 185 4 123 92 5 61 45 6 30 22 7 14 10 8 6 4 9 2 1 Evidently B can always play the first 10 tokens. But A can fit both tokens 10 and 11 into his gap of 2, whereas B can only fit token 10. So B loses for > 10 tokens, and wins for ≤ 10 tokens. 11th Brazil 1989 © John Scholes jscholes@kalva.demon.co.uk 4 April 2004 Last corrected/updated 4 Apr 04