Skip to main content
OlympiadHQ

Browse · MathNet

Print

XI OBM

Brazil counting and probability

Problem

and play a game. Each has tokens numbered from to . The board is two rows of squares. The first row is numbered to and the second row is numbered to . On the th turn, places his token number on any empty square in either row and places his token on any empty square in the other row. wins if the order of the tokens is the same in the two rows, otherwise wins. Which player has a winning strategy? Suppose each player has tokens, numbered from to . Who has the winning strategy? What if both rows are all the integers? Or both all the rationals?
Solution
Note that will lose if he does not space his tokens widely enough. Call the rows and , so that denotes the number in row . Suppose plays on , then on . If plays on and on , then he loses, because swaps rows and plays on . However, does not need to make this mistake, so can only force a win by always playing in the longer row, until runs out of space to match him in the shorter row. So places each token as centrally as possible in one the shortest gap. must match him. The table
after19891492
1994745
2496372
3247185
412392
56145
63022
71410
864
921
Evidently can always play the first tokens. But can fit both tokens and into his gap of , whereas can only fit token . So loses for more than tokens, and wins for at most tokens.

The only way 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 in the other row, so that the tokens numbered are always placed on the same number in each row.
Final answer
With ten tokens on rows of lengths one thousand four hundred ninety two and one thousand nine hundred eighty nine, player B has a winning strategy. For k tokens on this board, B wins if k is at most ten and A wins if k is greater than ten. If both rows are all integers, B has a winning strategy. If both rows are all rationals, B has a winning strategy.

Techniques

Games / greedy algorithmsInvariants / monovariants