2016 USAMO 第 6 题

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?

给出整数 $n$ 和 $k$，其中 $n\ge k\ge 2.$ 您与邪恶巫师玩以下游戏。

巫师有 $2n$ 卡；对于每个 $i = 1, ..., n,$，有两张标记为 $i.$ 的卡片。最初，向导将所有卡片面朝下以未知顺序排列成一排。

您可以重复进行以下形式的移动：您指向任意 $k$ 的牌。然后巫师将这些牌翻面朝上。如果任何两张牌匹配，则游戏结束，您获胜。否则，你必须把目光移开，而向导会任意排列 $k$ 选定的牌并将它们面朝下放回去。然后，又轮到你了。

如果存在一些正整数 $m$ 和一些保证在最多 $m$ 步中获胜的策略，无论向导如何响应，我们就说这个游戏是 $\textit{winnable}$ 。

对于哪些 $n$ 和 $k$ 值，游戏可以获胜？