2016 USAMO Problems/Problem 6
Problem
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?
Solution
This problem needs a solution. If you have a solution for it, please help us out by adding it.
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
These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions.
See also
2016 USAMO (Problems • Resources) | ||
Preceded by Problem 5 |
Last Problem | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |