猜牌游戏, $\binom{2n+1}{n}=\binom{2n+1}{n+1}$

Czhang271828

$A$ 和 $B$ 是两个魔法师(或者叫数学爱好者), 今天他们对 $C$ 表演了一个魔术.

$A$ 拿出事先准备的 $2n+1$ 张纸牌, 每张牌上写有数字 $1$ 至 $2n+1$. $A$ 先把自己关进小黑屋里, 再让 $C$ 随机选出 $n+1$ 张牌, 并将牌转交给 $B$, 随后让 $B$ 精心选出其中的 $n$ 张牌给 $C$, $C$ 将这 $n$ 张牌打乱后再交给 $A$ (即无法通过牌的先后顺序传递信息).

但出乎意料地是, $A$ 立马知道 $B$ 手中剩下的那张牌, 点解?  

Czhang271828

一种可行解法, 将每一 $(n+1)$-元集写作从小到大的排列的数组, 并依照字典序结构对这 $\binom{2n+1}{n+1}$ 个集合进行排列. 注意到, 在每一 $(n+1)$-元数组中的 $n$-元子数组($n+1$ 个)亦可通过字典序排列, 从而将每一 $(n+1)$-元数组对应未被占用的字典序最小的 $n$-元子数组即可.

考虑 $n=3$ 的情况, 则 $C$ 的所有选牌方式有字典序排列 $(1,2)<(1,3)<(2,3)$. 其中, $(1,2)$ 的子数组中字典序最小者为 $(1)$; $(1,3)$ 的子数组中字典序最小者也为 $(1)$, 但 $(1)$ 已被占用, 故选 $(3)$; 类似地, $(2,3)$ 对应 $(2)$. 从而\[
(1)\subseteq (1,2),\quad (3)\subseteq (1,3),\quad (2)\subseteq (2,3)
\]是可行解. 例如以上策略是 $A$ 与 $B$ 商量好的, $C$ 抽出 $(2,3)$, 此时 $B$ 选出 $(2)$ 即可.

更复杂地, 考虑 $n=5$, 则有对应\[
\begin{matrix}
&(1,2)&(1,2,3)\quad
&(1,4)&(1,2,4)\\
&(1,5)&(1,2,5)\quad
&(1,3)&(1,3,4)\\
&(3,5)&(1,3,5)\quad
&(4,5)&(1,4,5)\\
&(2,3)&(2,3,4)\quad
&(2,5)&(2,3,5)\\
&(2,4)&(2,4,5)\quad
&(3,4)&(3,4,5)
\end{matrix}\quad .
\]
根据上表, 若 $C$ 抽出的牌是 $(2,3,4)$, 则 $B$ 需展示的是 $(2,3)$.

如何证明对应的良定义性? 本人暂无很好的构造性方法(或许一开始选取的对应欠妥), 不过数学归纳显然.