Game is winnable if and only if $n \neq k$

Question

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, \ldots, n$, there are two cards labelled $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.

Prove that the game is winnable if and only if $n \neq k$.

Answer 1

$\textbf{Winnable for } k<n:\quad$ At step $l$, choose the cards in positions $l,l+1,\ldots,l+k$. Comparing the $k-1$ cards you see at positions $l,l+1,\ldots,l+k-1$ with the ones you saw at the previous step, you can conclude which card is at position $l-1$. (Obviously, this only applies from step $2$). After $n+2$ steps you know for certain which cards are in the positions $1,2,\ldots,n+1$. Two of these must coincide, simply choose them and $k-2$ arbitrary others.

Edit: The not winnability argument for $n=k$ was a bit sloppy...

Answer 2

I'm assuming that by "arbitrarily permutes the $k$ chosen cards" you mean that the $k$ chosen cards are placed in their original positions but in a different order; i.e. from $\{1, 2, 3, 4, 5, \dotsc\}$, if $\{2, 3, 5\}$ were chosen then a valid placement would be $\{1, 3, 5, 4, 2, \dotsc\}$ but not $\{2, 3, 1, 4, 5\}$. Further, I assume that no card is placed in the same position (the cards are deranged). The rest of this answer is based on these assumptions, so please clarify if they are incorrect.

Choose the cards at indices $1, 2, \dotsc, k$ and memorize their values. Now choose the cards at indices $2, 3, \dotsc, k+1$. There will be exactly one value which occurred in the first choice, but did not occur in the first $k-1$ cards of the second choice due to the derangement condition. We now know that that value is present at the index 1.

Then, choose the cards at indices $3, 4, \dotsc, k+2$ and by the above argument, we know the value present at the index 2 as well. Continue this procedure until we know the values of the first $2n - k$ indices. If $2n - k > n \iff n > k$, then there must be two indices with the same value in these: and since we know the values specifically, we can choose any $k$ cards containing those two and we are done. Since it is given that $n \geq k$, it is true that either $n = k$ or $n > k$: in the latter case, we have a winning strategy which takes exactly $n - k + 2$ steps (count them!).

In the former case $n = k$, I cannot prove that there does not exist a winning strategy, but I have made these observations: the strategy above definitely doesn't work, and it is possible for the wizard to 'reverse engineer' his permutations (i.e. not actually permute them until after you have made your choice while still following the rules, which is equivalent to a non-cheating case if you think about it) so that your choice will not contain matching cards. This reverse engineering method does not work for the strategy above because at each step, the permutation chosen does not matter in deciding the next step.

Answer 3

Two answers have already given a winning strategy for $n\gt k$.

For $n=k$, in each step we win unless we choose a complete set of $n$ different numbers. The other $n$ numbers are also all different, so whatever subset we pick from them in the following step, it won't contain a pair, and no matter what we know about these numbers, there's no way to prevent the remaining numbers, which have to be picked from the ones just shuffled, from being exactly the ones missing for a complete set of $n$ different numbers. Since this is true in every step, no step is certain to win, so in this case the game is not winnable.