Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2016 USAMO Problems/Problem 6"

(→‎Solution)
(→‎Solution)
 
(4 intermediate revisions by 3 users not shown)
Line 10: Line 10:
 
For which values of <math>n</math> and <math>k</math> is the game winnable?
 
For which values of <math>n</math> and <math>k</math> is the game winnable?
 
==Solution==
 
==Solution==
−
 
+
=== Case I: <math>n>k</math> ===
 
We first prove that the game is winnable whenever <math>n > k</math> by demonstrating a winning strategy in this case.
 
We first prove that the game is winnable whenever <math>n > k</math> by demonstrating a winning strategy in this case.
  
Line 20: Line 20:
  
 
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>
 
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>
 +
 +
=== Case II: <math>n=k</math> ===
  
 
We now prove that the game is not winnable if <math>n=k.</math> We will say that the game is in a state <math>S</math> if your knowledge about the card labels is of the following form:
 
We now prove that the game is not winnable if <math>n=k.</math> We will say that the game is in a state <math>S</math> if your knowledge about the card labels is of the following form:
  
−
There exists a group of <math>n</math> cards for which you know that those <math>n</math> cards have all of the labels <math>1, 2, ..., n</math> (i.e. you know that they have all distinct labels) in some order, but you know nothing about which of those <math>n</math> cards have which labels. (Call this group of cards Group A.)
+
There exists a group of <math>n</math> cards for which you know that those <math>n</math> cards have all of the labels <math>1, 2, ..., n</math> (i.e. you know that they have all distinct labels) in some order, but you know nothing about which of those <math>n</math> cards have which labels. (Call this group of cards Group <math>A.</math>)
  
 
Suppose that the game is in such a state <math>S.</math> We will now show that, regardless of your next move, you cannot guarantee victory or an escape from state <math>S.</math>
 
Suppose that the game is in such a state <math>S.</math> We will now show that, regardless of your next move, you cannot guarantee victory or an escape from state <math>S.</math>
  
−
Clearly, the <math>n</math> cards that are not in Group A must also have all of the labels <math>1, 2, ..., n.</math> (You might know something about which cards have which labels, or you might not.) Call this other collection of cards Group B.
+
Clearly, the <math>n</math> cards that are not in Group <math>A</math> must also have all of the labels <math>1, 2, ..., n.</math> (You might know something about which cards have which labels, or you might not.) Call this other collection of cards Group <math>B.</math>
  
−
If, on the next move, you pick all of the cards from Group A or all of the cards from Group B, then you clearly will not get a matching pair. The wizard will then arbitrarily permute those cards. Thus, for those <math>n</math> chosen cards, you know their labels are all distinct, but you know nothing about which cards have which labels. Thus, you are back in state <math>S.</math>
+
If, on the next move, you pick all of the cards from Group <math>A</math> or all of the cards from Group <math>B,</math> then you clearly will not get a matching pair. The wizard will then arbitrarily permute those cards. Thus, for those <math>n</math> chosen cards, you know their labels are all distinct, but you know nothing about which cards have which labels. Thus, you are back in state <math>S.</math>
  
−
Now, suppose you pick <math>x</math> cards from Group <math>A</math> and <math>n-x</math> cards from Group <math>B,</math> where <math>x</math> is an integer and <math>1\le x\le n-1.</math> Then, the cards chosen from Group B will form a set of labels <math>P\subset Z_n,</math> where <math>Z_n = \left\{ {1, 2, ..., n} \right\}.</math> However, you know nothing about which cards in Group A have which labels. Thus, there is no way for you to prevent the <math>x</math> cards from Group A to form the exact set of labels <math>Q = Z_n\setminus P.</math> In such a case, there will be no matching cards, so you will not win. Furthermore, the wizard will then arbitrarily permute these <math>n</math> cards, so you will know that they have all <math>n</math> distinct labels, but you will know nothing about which cards have which labels. Therefore, you are again in state <math>S.</math>
+
Now, suppose you pick <math>x</math> cards from Group <math>A</math> and <math>n-x</math> cards from Group <math>B,</math> where <math>x</math> is an integer and <math>1\le x\le n-1.</math> Then, the cards chosen from Group <math>B</math> will form a set of labels <math>P\subset Z_n,</math> where <math>Z_n = \left\{ {1, 2, ..., n} \right\}</math> and <math>|P| = n-x.</math> However, you know nothing about which cards in Group <math>A</math> have which labels. Thus, there is no way for you to prevent the <math>x</math> cards from Group <math>A</math> to form the exact set of labels <math>Q = Z_n\setminus P.</math> In such a case, there will be no matching cards, so you will not win. Furthermore, the wizard will then arbitrarily permute these <math>n</math> cards, so you will know that they have all <math>n</math> distinct labels, but you will know nothing about which cards have which labels. Therefore, you are again in state <math>S.</math>
  
 
We have covered all cases, so it follows that, once you enter state <math>S,</math> you cannot guarantee escape from state <math>S</math> or victory.
 
We have covered all cases, so it follows that, once you enter state <math>S,</math> you cannot guarantee escape from state <math>S</math> or victory.
Line 37: Line 39:
 
Now, look at the very first move you make. Obviously, you cannot guarantee victory on the first move, as you know nothing about which cards have which labels. Assuming that you do not win on the first move, the <math>n</math> cards you chose have all distinct labels. The wizard then permutes the <math>n</math> cards you chose, so you now know that those <math>n</math> cards have all distinct labels but know nothing about which cards have which labels. Therefore, if you do not win on your first move, then the game enters state <math>S,</math> and we have already proven that you cannot guarantee victory from this point.
 
Now, look at the very first move you make. Obviously, you cannot guarantee victory on the first move, as you know nothing about which cards have which labels. Assuming that you do not win on the first move, the <math>n</math> cards you chose have all distinct labels. The wizard then permutes the <math>n</math> cards you chose, so you now know that those <math>n</math> cards have all distinct labels but know nothing about which cards have which labels. Therefore, if you do not win on your first move, then the game enters state <math>S,</math> and we have already proven that you cannot guarantee victory from this point.
  
−
We therefore conclude that the game is not winnable if <math>n=k.</math> We proved earlier that the game is winnable if <math>n>k,</math> so the game is winnable if and only if <math>n = k\ge 2.</math>
+
We therefore conclude that the game is not winnable if <math>n=k.</math> We proved earlier that the game is winnable if <math>n>k,</math> so the game is winnable if and only if <math>n>k\ge 2.</math>
 +
 
 +
==Solution 2==
 +
We claim that the game is winnable if and only if <math>n>k</math>. Suppose after the first step, the cards <math>1</math> to <math>n</math> are shuffled around. Notice that we have <math>n</math> cards that we don't know the position of (which are all cards from <math>1</math> to <math>n</math>). Now, suppose we pick <math>p</math> known cards. Note that the <math>p</math> cards are all different(since the known cards are the cards from <math>1</math> to <math>n</math>), and there is still a possibility that the other cards from the unknown cards complement and cause <math>1</math> to <math>n</math>. Therefore, we are in the same state as before, and the game is unwinnable.
 +
 
 +
Now, suppose <math>n>k</math>. Denote the ith card counting from the left. We pick cards <math>1</math> to <math>k</math>, keeping track of the set of values of the cards. Then, we pick cards <math>2</math> to <math>k+1</math>, adding the value of the <math>k+1</math>th card into the set of value of cards. We keep doing this, until we pick cards <math>2n-k</math> to <math>2n-1</math>, at which point we know the exact number on the <math>2n</math>th card. Now, we go back to <math>1</math> through <math>k</math>, and repeat this process, until we reveal the <math>2n-1</math>th card(unless we win during the process). This process terminates only when there are less or equal to <math>k</math> cards that we don't know the exact numbers on or if we somehow win, clearly, as otherwise we're still revealing new information by picking cards from <math>1</math> through <math>k</math>. Note that we now know the exact values on <math>2n-k</math> of the cards. By the Pigeonhole Principle, since <math>k<n</math>, <math>2</math> of them are the same, and we pick those <math>2</math> cards and <math>k-2</math> other random cards and we win.
  
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 09:11, 8 April 2023

Problem

Integers $n$ and $k$ are given, with $n\ge k\ge 2.$ You play the following game against an evil wizard.

The wizard has $2n$ cards; for each $i = 1, ..., n,$ there are two cards labeled $i.$ 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 $k$ 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 $k$ chosen cards and turns them back face-down. Then, it is your turn again.

We say this game is $\textit{winnable}$ if there exist some positive integer $m$ and some strategy that is guaranteed to win in at most $m$ moves, no matter how the wizard responds.

For which values of $n$ and $k$ is the game winnable?

Solution

Case I: $n>k$

We first prove that the game is winnable whenever $n > k$ by demonstrating a winning strategy in this case.

On the $i$th move, choose the $k$ cards in positions $i$ through $i+k-1.$ Assuming that you do not win on any earlier move, repeat this for $1\le i \le 2n-k+1.$

Assume that you did not win on any of the first $2n-k+1$ moves, as described above. Let $j$ be an integer such that $1\le j\le 2n-k.$ On the $j$th move, the wizard revealed the cards in positions $j$ through $j+k-1,$ so you know the labels of all of these cards (just not necessarily in the right order). Then, on the $(j+1)$th move, the wizard revealed the cards in positions $j+1$ through $j+k,$ which means that you get to see all of the cards that were moved to positions $j+1$ through $j+k.$ This means that you can uniquely determine the label on card $j,$ since you knew all of the labels from $j$ through $j+k-1,$ and the card in position $j$ could not have moved anywhere else since your last move.

It follows that, after the sequence of $2n-k+1$ moves described above, you know the labels on the first $2n-k$ cards. Since $n > k,$ we have $2n-k \ge n+1,$ so there must be a pair of cards with matching labels in this group of $2n-k$ cards, by the Pigeonhole Principle. On your next move, you can pick a group of $k$ cards that includes that pair of matching cards, and you win.

We have created a strategy that is guaranteed to win in at most $m = 2n-k+2$ moves. Thus, the game is winnable for all $n > k.$

Case II: $n=k$

We now prove that the game is not winnable if $n=k.$ We will say that the game is in a state $S$ if your knowledge about the card labels is of the following form:

There exists a group of $n$ cards for which you know that those $n$ cards have all of the labels $1, 2, ..., n$ (i.e. you know that they have all distinct labels) in some order, but you know nothing about which of those $n$ cards have which labels. (Call this group of cards Group $A.$)

Suppose that the game is in such a state $S.$ We will now show that, regardless of your next move, you cannot guarantee victory or an escape from state $S.$

Clearly, the $n$ cards that are not in Group $A$ must also have all of the labels $1, 2, ..., n.$ (You might know something about which cards have which labels, or you might not.) Call this other collection of cards Group $B.$

If, on the next move, you pick all of the cards from Group $A$ or all of the cards from Group $B,$ then you clearly will not get a matching pair. The wizard will then arbitrarily permute those cards. Thus, for those $n$ chosen cards, you know their labels are all distinct, but you know nothing about which cards have which labels. Thus, you are back in state $S.$

Now, suppose you pick $x$ cards from Group $A$ and $n-x$ cards from Group $B,$ where $x$ is an integer and $1\le x\le n-1.$ Then, the cards chosen from Group $B$ will form a set of labels $P\subset Z_n,$ where $Z_n = \left\{ {1, 2, ..., n} \right\}$ and $|P| = n-x.$ However, you know nothing about which cards in Group $A$ have which labels. Thus, there is no way for you to prevent the $x$ cards from Group $A$ to form the exact set of labels $Q = Z_n\setminus P.$ In such a case, there will be no matching cards, so you will not win. Furthermore, the wizard will then arbitrarily permute these $n$ cards, so you will know that they have all $n$ distinct labels, but you will know nothing about which cards have which labels. Therefore, you are again in state $S.$

We have covered all cases, so it follows that, once you enter state $S,$ you cannot guarantee escape from state $S$ or victory.

Now, look at the very first move you make. Obviously, you cannot guarantee victory on the first move, as you know nothing about which cards have which labels. Assuming that you do not win on the first move, the $n$ cards you chose have all distinct labels. The wizard then permutes the $n$ cards you chose, so you now know that those $n$ cards have all distinct labels but know nothing about which cards have which labels. Therefore, if you do not win on your first move, then the game enters state $S,$ and we have already proven that you cannot guarantee victory from this point.

We therefore conclude that the game is not winnable if $n=k.$ We proved earlier that the game is winnable if $n>k,$ so the game is winnable if and only if $n>k\ge 2.$

Solution 2

We claim that the game is winnable if and only if $n>k$. Suppose after the first step, the cards $1$ to $n$ are shuffled around. Notice that we have $n$ cards that we don't know the position of (which are all cards from $1$ to $n$). Now, suppose we pick $p$ known cards. Note that the $p$ cards are all different(since the known cards are the cards from $1$ to $n$), and there is still a possibility that the other cards from the unknown cards complement and cause $1$ to $n$. Therefore, we are in the same state as before, and the game is unwinnable.

Now, suppose $n>k$. Denote the ith card counting from the left. We pick cards $1$ to $k$, keeping track of the set of values of the cards. Then, we pick cards $2$ to $k+1$, adding the value of the $k+1$th card into the set of value of cards. We keep doing this, until we pick cards $2n-k$ to $2n-1$, at which point we know the exact number on the $2n$th card. Now, we go back to $1$ through $k$, and repeat this process, until we reveal the $2n-1$th card(unless we win during the process). This process terminates only when there are less or equal to $k$ cards that we don't know the exact numbers on or if we somehow win, clearly, as otherwise we're still revealing new information by picking cards from $1$ through $k$. Note that we now know the exact values on $2n-k$ of the cards. By the Pigeonhole Principle, since $k<n$, $2$ of them are the same, and we pick those $2$ cards and $k-2$ other random cards and we win.

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

See also

2016 USAMO (Problems • Resources)
Preceded by
Problem 5 		Last Problem
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2016_USAMO_Problems/Problem_6&oldid=191899"