第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 回後、$P_1\cup\cdots\cup P_k$ の外の一点を $D_{k+1}$ とする。$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 は候補を一つ減らせる。これを繰り返して候補を $2^k$ 個以下にし、その全体を X とすればよい。