第3题

设当前候选集 S 有 $N\ge2^k+1$ 个元素。选取 $D_1$ 使两侧各至少有 $2^{k-1}$ 个元素。知道 $P_1$ 后，选 $D_2$ 使 $D_2\cap P_1^c$ 与 $D_2^c\cap P_1^c$ 各至少有 $2^{k-2}$ 个元素；继续进行，使得经过 j 次回答后未覆盖的集合仍有两个部分，各至少含 $2^{k-j}$ 个元素。经过 k 次后，取 $D_{k+1}$ 为 $P_1\cup\cdots\cup P_k$ 外的一个单点。若 $P_{k+1}=D_{k+1}^c$，就删去该单点；若 $P_{k+1}=D_{k+1}$，则在 $S\setminus D_{k+1}$ 上重复这 k 步。于是 $P_{k+1}\cup\cdots\cup P_{2k+1}$ 包含 x，却遗漏至少一个候选。故 B 可将 N 减少一。反复操作直到候选至多剩 $2^k$ 个，再把整个候选集作为 X。