Difference between revisions of "2016 USAMO Problems/Problem 6"
(Created page with "==Problem== Integers <math>n</math> and <math>k</math> are given, with <math>n\ge k\ge 2.</math> You play the following game against an evil wizard. The wizard has <math>2n</...") |
|||
Line 11: | Line 11: | ||
==Solution== | ==Solution== | ||
{{solution}} | {{solution}} | ||
+ | We first prove that the game is winnable whenever <math>n > k</math> by demonstrating a winning strategy in this case. | ||
+ | |||
+ | On the <math>i</math>th move, choose the <math>k</math> cards in positions <math>i</math> through <math>i+k-1.</math> Assuming that you do not win on any earlier move, repeat this for <math>1\le i \le 2n-k+1.</math> | ||
+ | |||
+ | Assume that you did not win on any of the first <math>2n-k+1</math> moves, as described above. Let <math>j</math> be an integer such that <math>1\le j\le 2n-k.</math> On the <math>j</math>th move, the wizard revealed the cards in positions <math>j</math> through <math>j+k-1,</math> so you know the labels of all of these cards (just not necessarily in the right order). Then, on the <math>(j+1)</math>th move, the wizard revealed the cards in positions <math>j+1</math> through <math>j+k,</math> which means that you get to see all of the cards that were moved to positions <math>j+1</math> through <math>j+k.</math> This means that you can uniquely determine the label on card <math>j,</math> since you knew all of the labels from <math>j</math> through <math>j+k-1,</math> and the card in position <math>j</math> could not have moved anywhere else since your last move. | ||
+ | |||
+ | It follows that, after the sequence of <math>2n-k+1</math> moves described above, you know the labels on the first <math>2n-k</math> cards. Since <math>n > k,</math> we have <math>2n-k \ge n+1,</math> so there must be a pair of cards with matching labels in this group of <math>2n-k</math> cards, by the Pigeonhole Principle. On your next move, you can pick a group of <math>k</math> cards that includes that pair of matching cards, and you win. | ||
+ | |||
+ | We have created a strategy that is guaranteed to win in at most <math>m = 2n-k+2</math> moves. Thus, the game is winnable for all <math>n > k.</math> | ||
{{MAA Notice}} | {{MAA Notice}} | ||
==See also== | ==See also== | ||
{{USAMO newbox|year=2016|num-b=5|aftertext=|after=Last Problem}} | {{USAMO newbox|year=2016|num-b=5|aftertext=|after=Last Problem}} |
Revision as of 20:11, 27 April 2016
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
The problems on this page are copyrighted by the Mathematical Association of America's 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 |