2016 USAMO Problems/Problem 6
Integers and are given, with You play the following game against an evil wizard.
The wizard has cards; for each there are two cards labeled Initially, the wizard places all cards face down in a row, in unknown order.
You may repeatedly make moves of the following form: you point to any of the cards. The wizard then turns those cards face up. If any two of the cards match, the game is over and you win. Otherwise, you must look away, while the wizard arbitrarily permutes the chosen cards and turns them back face-down. Then, it is your turn again.
We say this game is if there exist some positive integer and some strategy that is guaranteed to win in at most moves, no matter how the wizard responds.
For which values of and is the game winnable?
This problem needs a solution. If you have a solution for it, please help us out by. We first prove that the game is winnable whenever by demonstrating a winning strategy in this case.
On the th move, choose the cards in positions through Assuming that you do not win on any earlier move, repeat this for
Assume that you did not win on any of the first moves, as described above. Let be an integer such that On the th move, the wizard revealed the cards in positions through so you know the labels of all of these cards (just not necessarily in the right order). Then, on the th move, the wizard revealed the cards in positions through which means that you get to see all of the cards that were moved to positions through This means that you can uniquely determine the label on card since you knew all of the labels from through and the card in position could not have moved anywhere else since your last move.
It follows that, after the sequence of moves described above, you know the labels on the first cards. Since we have so there must be a pair of cards with matching labels in this group of cards, by the Pigeonhole Principle. On your next move, you can pick a group of cards that includes that pair of matching cards, and you win.
We have created a strategy that is guaranteed to win in at most moves. Thus, the game is winnable for all
|2016 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAMO Problems and Solutions|