第3题

取 $1.99<p<q<2$，并对充分大的 k 取满足 $1.99^k\le n<p^k-1$ 与 $(p/q)^k\le2-q$ 的整数 n。以 $N=n+1$ 个候选开始，令 $x_i^0=1$，则 $T_0=N\le p^k<q^k$。对问题 D，两种可能的下一步总权重为 $T(D)=\sum_{i\notin D}qx_i+|D|$ 与 $T(D^c)=\sum_{i\in D}qx_i+|D^c|$。两者之和为 $qT+N\le q^{k+1}+p^k\le2q^k$，所以由所列条件，其中一个不超过 $q^k$。选该侧为 P。归纳可保持 $T_j\le q^k$。若某候选 i 连续 $k+1$ 次不属于 P，其权重将至少变为 $q^{k+1}$，与 $T_j\le q^k$ 矛盾；故所有候选都属于步骤一要求的每个连续块的并集。因此全部 $N=n+1$ 个候选仍然可能，而 B 只能指定 n 个，不能保证获胜。