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,\dots,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 \emph{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?

\end{enumerate}

Solution: The game is winnable if and only if $k < n$.

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\}$.
Indeed, by taking the difference of the $i$th and $(i+1)$st query,
we can deduce the value of the $i$th card, for $1 \le i \le 2n-k$.
(This is possible because the cards are flipped face up before they are re-shuffled,
so even if two adjacent queries return the same set,
one can still determine the $i$th card.
It is possible to solve the problem even without the flipped information, though.)
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.