Maths Olympiad Prep

Library / /5 of 5

Combinatorics Difficulty 7.4 National olympiad, round 2 Prove it Brazil

AA and BB play a game. Each has 1010 tokens numbered from 11 to 1010. The board is two rows of squares. The first row is numbered 11 to 14921492 and the second row is numbered 11 to 19891989. On the nnth turn, AA places his token number nn on any empty square in either row and BB places his token on any empty square in the other row. BB wins if the order of the tokens is the same in the two rows, otherwise AA wins. Which player has a winning strategy? Suppose each player has kk tokens, numbered from 11 to kk. Who has the winning strategy? What if both rows are all the integers? Or both all the rationals?

Solution

Note that BB will lose if he does not space his tokens widely enough. Call the rows RR and SS, so that SnS^n denotes the number nn in row SS. Suppose AA plays 11 on R5R5, then 22 on R6R6. If BB plays 11 on S5S5 and 22 on S7S7, then he loses, because AA swaps rows and plays 33 on S6S6. However, BB does not need to make this mistake, so AA can only force a win by always playing in the longer row, until BB runs out of space to match him in the shorter row. So AA places each token as centrally as possible in one the shortest gap. BB must match him. The table

after19891492
1994745
2496372
3247185
412392
56145
63022
71410
864
921

Evidently BB can always play the first 1010 tokens. But AA can fit both tokens 1010 and 1111 into his gap of 22, whereas BB can only fit token 1010. So BB loses for more than 1010 tokens, and wins for at most 1010 tokens.

The only way BB 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 AA in the other row, so that the tokens numbered kk are always placed on the same number in each row.

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.