The game is winnable if and only if $n \neq k$. First suppose $2 \le k < n$. Query the cards in positions $\left\{ 1, \dots, k \right\}$, then $\left\{ 2, \dots, k+1 \right\}$, and so on, up to $\left\{ 2n-k+1, 2n \right\}$. By taking the diff of any two adjacent queries, we can deduce for certain the values on cards $1, 2, \dots, 2n-k$. If $k \le n$, this is more than $n$ cards, so we can find a matching pair. For $k = n$ we remark the following: at each turn after the first, assuming one has not won, there are $n$ cards representing each of the $n$ values exactly once, such that the player has no information about the order of those $n$ cards. We claim that consequently the player cannot guarantee victory. Indeed, let $S$ denote this set of $n$ cards, and $\overline S$ the other $n$ cards. The player will never win by picking only cards in $S$ or $\overline S$. Also, if the player selects some cards in $S$ and some cards in $\overline S$, then it is possible that the choice of cards in $S$ is exactly the complement of those selected from $\overline S$; the strategy cannot prevent this since the player has no information on $S$. This implies the result.

Why was this so easy I can never solve easy combo problems.

The solution in post #3 (which was also mine) is not what I was expecting from the last problem of a USAMO day, so I started wondering if perhaps the problem intended that the $k$ cards you chose were told to you unordered. I found this makes it a little harder, but not by enough.

I personally felt this easier than normal #6... This should exchange with problem 5 and 4 lol Got the same thing as #3.

v_Enhance wrote: The game is winnable if and only if $n \neq k$. First suppose $2 \le k < n$. Query the cards in positions $\left\{ 1, \dots, k \right\}$, then $\left\{ 2, \dots, k+1 \right\}$, and so on, up to $\left\{ 2n-k+1, 2n \right\}$. By taking the diff of any two adjacent queries, we can deduce for certain the values on cards $1, 2, \dots, 2n-k$. If $k \le n$, this is more than $n$ cards, so we can find a matching pair. For $k = n$ we remark the following: at each turn after the first, assuming one has not won, there are $n$ cards representing each of the $n$ values exactly once, such that the player has no information about the order of those $n$ cards. We claim that consequently the player cannot guarantee victory. Indeed, let $S$ denote this set of $n$ cards, and $\ol S$ the other $n$ cards. The player will never win by picking only cards in $S$ or $\ol S$. Also, if the player selects some cards in $S$ and some cards in $\ol S$, then it is possible that the choice of cards in $S$ is exactly the complement of those selected from $\ol S$; the strategy cannot prevent this since the player has no information on $S$. This implies the result. Wait, what if you get, say, 123 123 123 123 123 123 for the first 6 (assuming k = 3 and n > 3) can't you not know what the cards in slots 1, 2, and 3 are

You can assume that you can see the positions of the cards flipped, so you can still sequentially determine the first few cards by elimination.

v_Enhance wrote: The game is winnable if and only if $n \neq k$. First suppose $2 \le k < n$. Query the cards in positions $\left\{ 1, \dots, k \right\}$, then $\left\{ 2, \dots, k+1 \right\}$, and so on, up to $\left\{ 2n-k+1, 2n \right\}$. By taking the diff of any two adjacent queries, we can deduce for certain the values on cards $1, 2, \dots, 2n-k$. If $k \le n$, this is more than $n$ cards, so we can find a matching pair. For $k = n$ we remark the following: at each turn after the first, assuming one has not won, there are $n$ cards representing each of the $n$ values exactly once, such that the player has no information about the order of those $n$ cards. We claim that consequently the player cannot guarantee victory. Indeed, let $S$ denote this set of $n$ cards, and $\ol S$ the other $n$ cards. The player will never win by picking only cards in $S$ or $\ol S$. Also, if the player selects some cards in $S$ and some cards in $\ol S$, then it is possible that the choice of cards in $S$ is exactly the complement of those selected from $\ol S$; the strategy cannot prevent this since the player has no information on $S$. This implies the result. yeah, you can also win in $O(n^{2})$ turns I think with this strategy. Solved it with about 30 minutes and took me 15 minutes to write up, horrifically misplaced imo. Should've been #6,4,5 in order.

dantx5 wrote: You can assume that you can see the positions of the cards flipped, so you can still sequentially determine the first few cards by elimination. oh shoot I forgot that for the actual proof, I did it for disproving n=k though ughghghghghghggghghhh If I made the assertion that k < n at the beginning and basically demonstrated all of the required stuff do you think I would still receive a 7 down score?

MellowMelon wrote: The solution in post #3 (which was also mine) is not what I was expecting from the last problem of a USAMO day, so I started wondering if perhaps the problem intended that the $k$ cards you chose were told to you unordered. I found this makes it a little harder, but not by enough. wwwrqnojcm wrote: I personally felt this easier than normal #6... This should exchange with problem 5 lol Got the same thing as #3. Yeah I agree. I'll go as far as to say this was the easiest problem on the entire exam, both JMO and USAMO combined, and that's with me being awful at combinatorics. (Disclaimer I didn't actually try J4 yet.) Literally Danielle and I just took a pack of playing cards, played the cases $(k,n) = (2,2), \; (2,3), \; (3,3)$ for about ten minutes, and then were done.

So I showed the strategy Evan described for $k<n$. Then I went on to say for $k=n$ that after you determine the values of the first n cards, you can just pick one in the second group, look at it, and then pick its match in the first group. Still worth 7-?

Deleted.

Ugh I jntepreted it so that the you can never see the cards. Dumb me, I even got the ladder but it's okay

phil9047 wrote: How many points do you think saying k=n is unwinnable will get? I spent my last 10 minutes on this and saw that k=n does not work and then assumed that k < n is even worse so I said the whole game is unwinnable. 0 (To be clear you could have gotten $> 0$ if you had correctly claimed that *only* $k=n$ was winnable, but if you just claim the entire game is unwinnable then you aren't going to get points.)

I figured out the strategy for k<n, and just stated that k=n is unwinnable, how many points is that? I didn't think that v_enhance's proof would work, since maybe the player could theoretically gain some more information from his moves?

darn was hoping for a hard combo question this year...

darn i got messed up by the problem order... thought this one was gonna be super duper hard

Scoring like this? 1 for proving k=n is unwinnable, 5 for proving k<n is winnable, 1 for claiming k<n is winnable, 1+1=1?

Shaddoll wrote: Scoring like this? 1 for proving k=n is unwinnable, 5 for proving k<n is winnable, 1 for claiming k<n is winnable, 1+1=1? and 5+1=5, I doubt my not-really-a-solution is worth more than that.

why is proving k<n winnable a 5? it seems to be the easiest part to me

El_Ectric wrote: Integers $n$ and $k$ are given, with $n\ge k\ge2$. You play the following game against an evil wizard. The wizard has $2n$ cards; for each $i=1,\ldots,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 then turns them back face-down. Then, it is your turn again. We say this game is 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? We claim the answer is all $k \neq n$. To show all $k \neq n$ is trival:-Pack the cards in positions $\left\{ 1, \dots, k \right\}$, then $\left\{ 2, \dots, k+1 \right\}$, and so on, up to $\left\{ 2n-k+1, 2n \right\}$. By taking the diff of any two adjacent packs, we can deduce for certain the values on cards $1, 2, \dots, 2n-k$ i.e there are $2n-k>n$ cards and we need to show we can pick two cards of equal number but this trivally follows from the Pigeon hole principle. To show $k=n$ has no optimal strategy:-Suppose that in the first step we pick cards $[a_1,a_2,a_3,.......,a_n]$ however we can't make sure of an optimal strategy to make sure that after the wizard replaces the cards we pick two cards with the same value so we are done.$\blacksquare$

The answer is $n \neq k$. Proof for $n>k$: To do this, let the cards (in any order) be numbered $c_1,c_2 \dots c_{2n}$. Then, apply the process on $c_1 \dots c_k$ and then on $c_2 \dots c_{k+1}$. From this, you can deduce $c_1$. Similarly, you can continue this, and deduce all $c_1, \dots c_{2n-k}$ and by Pigeonhole, we have that there are an $i,j$ such that $c_i=c_j$. Just choose these two and $n-2$ other random cards to finish. Proof that $n=k$ does not work: There is obviously no way to win on move $1$. Thus, say on move $i$, you lose. This means, the subset you have chosen is $(1,2,\dots n)$. Let this subset be $X$, and the subset that is the complement of $X$ be $Y$. Now to win on move $i+1$, it is obvious that you should not choose $X$ or $Y$. Let $T$ be the subset you choose, and $A=T \cap X$ and $B=T\cap Y$. Now first note that neither $A$ nor $B$ has duplicate elements. Thus, we need some element in $A$ to appear also in $B$. Now note that $Y$ does not change, but $X$ does. Also since $X=(1,2,\dots n)$, there is always a chance that $A$ contains all the elements that $B$ does not, and thus there is no way to guarantee a win in this case.

We claim that the game is winnable iff $k<n$. For $k<n$, label the cards $1,2,\ldots,2n$ from left to right. Then, first ask to reveal $(1,\ldots,k)$, then $(2,\ldots, k+1)$, and so on, incrementing to the right each time until checking $(2n-k+1,2n)$. After doing this, we know the exact identities of the cards left at slots $1,2,\ldots, 2n-k$. Note that $k\leq n-1$, so $2n-k\geq n+1$, so by the pigeonhole principle, there are two with the same number, so we just select some set of $k$ containing these two and we win. For $k=n$, we claim that at all times, there is a set of $n$ cards where the only information we have is that they're the multiset $\{1,2,\ldots ,n\}$. This is because after each round, the $n$ shuffled cards are $1,\ldots,n$ so you have no information on any of the cards. Thus, for any of the pairs we may hope to guarantee, the other is in the multiset of $n$, so we cannot guarantee anything and the wizard wins. $\blacksquare$.

PepsiCola wrote: For an interesting question (and how I originally read this problem), what are the $n$ and $k$ that yield a winning strategy if, after selecting the $k$ cards, the wizard reshuffles the entire deck? I think that the answer to this is: No such pair exists. To see why, we will change permuting a little: it is equivalent game if wizard names the cards after i choose them (for example, if $n=3$ and $k=2$, if I choose $(1,3)$, the wizard can assign two distinct numbers on these $2$ cards so they don't match). The conclusion thus follows because $k \leq n$

We Pick sets of k cards such that none of them are card 2n. We count these up(if were forced to pick a position we picked before we dont count it again otherwise we may overcount). Now we know what card 2n is. Now we pick stuff such that it doesnt hit 2n or 2n-1, then we can know what that is. We do this until we know as many as we cab. If k<n, we know 2n-k>n cards, so we can pick and win. If k=n, we will end up knowing n of them, but then if we pick any of them, our knowledge is ruined.

huashiliao2020 wrote: Just wanted to point something out--I think most solutions need to account for if (1,2,...,k)=(2,3,...,k+1) this never happens because the k+1-th card isn't in the first (hence doesn't move) but must be in the second?

how did you quote my post AFTER i deleeted it? anyways i just realized and im gonna post my sol soon, i had it finished originally but just needed to account for this case edit: your post also made no grammatical sense in my brain so i did not even read it so i will still post what i hope is correct Take the natural algorithm (1,2,...,k),(2,3,...,k+1),...,(2n-k+1,...,2n) and look at their differences to find what number cards each of them are; for k<n 2n-k+1 is at least n+2, meaning we know at least n+1 cards, done. Note that if for example (1,2,...,k)=(2,3,...,k+1) in some order, assuming two aren't in the same pile, we have k+1=the first number; in this case we keep going to find the k+1th number, which evidently finds the first number. This is something most solutions haven't pointed out; imho would be a 1 point deduction, although this case is decently trivial. As for k=n, you get one of every card in every time, and you can't guarantee any win 100\% because the wizard can rearrange the cards in one way s.t. you take cards from the first set (1,2,...,n) and the complement in the second (but same) set (1,2,...,n)

huashiliao2020 wrote: how did you quote my post AFTER i deleeted it? anyways i just realized and im gonna post my sol soon, i had it finished originally but just needed to account for this case edit: your post also made no grammatical sense in my brain so i did not even read it so i will still post what i hope is correct return of aops downvote button

Solved with pi271828. So anti :skull: The answer is $\boxed{\text{all }(n,k)\ \mid\ n>k}$. For $1\le i\le2n$, let $a_i$ be the label of the card in position $i$, variable across time. Construction. For $1\le i\le 2n-k+1$, pick $S_i=\{a_i,\dots,a_{i+k-1}\}$. So long as all the elements of $S_i$ are distinct (else we win immediately), revealing $S_i$ determines $a_{i-1}$, since by assumption $S_{i-1}$ was revealed the previous turn. Hence, we can determine $a_1,\dots,a_{2n-k}$, i.e., we can determine at least $n+1$ different cards (as $n>k$ by assumption), giving a pair of equals by Pigeonhole. Necessity. If $n=k$, it is possible to chose labels $1,\dots,n$ on the first turn. Whenever one chooses $1,\dots,n$, it is impossible to know the positions of each of the other $1,\dots,n$, which in turn precludes guaranteeing a pair. $\square$

We claim that the game is winnable if and only if $n\neq k$. If $n>k$, then a strategy is to look at the cards in positions $1$, $2$, $\ldots$, $k-1$, $i$ for all $i\geq k$. This allows you to determine the values of cards $k$ through $2n-1$, which has $2n-k$ total values, so since $2n-k>k$, there exists two cards with the same value, so you can pick $k$ of the cards including those two cards. Now, if $n=k$, we will show that the wizard can permute the cards such that it is always possible for the $k$ chosen cards to be a permutation of $1$, have information on at most $k$ of the cards, and all $k$ of those cards must have distinct values. Therefore, for any $k$ cards, it is possible to permute the $k$ unknown cards such that the $k$ cards are a permutation of the numbers $1$ through $k$. This means that the game is winnable if and only if $\boxed{n\neq k}$.

I claim that the game is winnable if and only $k < n$. Firstly, we prove that if $k < n$, the game is winnable. Indeed, we can pick arbitrary $k$ cards. After wizard permutes the $k$ we chose, just pick $k-1$ cards from there and pick 1 card from other $2n-k$ card. Then, we can know the written number on the remaining one card we didn't choose. Since we have $2n$ cards, we can know the written number on $2n-k$ card. Since $2n-k > n$, there surely exists two equal number on $2n-k$ card we know. Now we prove that we can't win if $k=n$. We may assume that wizard knows our next move. WLOG, assume that we chose the first $n$ card and that $n$ cards were the permutation of $(1, 2, \dots, n)$. Assume that the next move, we choose some numbers from the first $n$ cards and some cards from the last $n$ cards. Since wizard knows what cards we are going to choose from the last $n$ cards, wizard can permute the first $n$ card that $n$ card we are going to choose will be the permutation of $(1, 2, \dots, n)$. Hence, if wizard follows that strategy, the game will never end. $\blacksquare$

The game is winnable when $k < n$. If $k < n$, we can choose the first $k$ cards, then choose the $2$ through $k+1$ cards. Then we can determine what the first card is. Repeating this, we can determine the first $2n-k$ cards. Since $k < n$, there must be a pair of matching cards in the first $2n-k$ cards, then just pick those cards. If $k=n$, then suppose the first $n$ cards we choose do not contain a pair. Then on the next turn, suppose we choose $a$ of the first $n$ cards and $n-a$ of the other $n$ cards. Then the wizard could have permuted the cards such that the set of the $a$ cards is the complement of the other $n-a$ cards, so the $n$ cards we choose are all different, and this could repeat infinitely, so the game is not winnable.

The answer is all $k$ so that $k \neq n$. Our strategy for $k < n$ is to check cards$(1, \dots, k)$, $(2, \dots, k+1)$, $\dots$, $(2n - k + 1, \dots, 2n)$. This allows to figure out the placement and identity of the first $2n - k$ cards. Then it follows by Pigeonhole there must be a matching pair in the first $2n - k$ cards, so we can just choose those two cards. If $k = n$, then notice that any given move does not give us any new information, and is isomorphic to the starting position. Say we, WLOG permute the first $n$ cards. Then we gain the information that the first $n$ cards are all of $i = 1, 2 \dots, n$ and similarly for the last $n$. However we don't know the positions of any of the cards, and any new set of $n$ cards that we choose may also be just be cards $(1, 2, \dots, n)$, leading us back to our original position.

This is P6 or P⅙(<1) ?