MathLabs

第3問

嘘つき当てゲームでは、A が 1≤x≤N1\le x\le N を満たす整数 xx を選び、B に NN を知らせる。B は任意の正整数集合 DD について「xx は DD に属するか」と質問する。A は各質問に真または偽で答えられるが、任意の連続する k+1k+1 個の回答のうち少なくとも一つは真でなければならない。有限回の質問の後、B は高々 nn 個の正整数からなる集合 XX を指定し、x∈Xx\in X なら勝ちである。(a) n≥2kn\ge2^k なら B が勝利を保証できること、(b) 十分大きいすべての kk に対し、n≥1.99kn\ge1.99^k でどの戦略も勝利を保証できないものがあることを示せ。
ステップ 3/3: 重み付き敵対者はかなり小さい目標を妨げる
前のステップ次のステップ
ざっくり言うと

可能な真の回答集合から連続して外れる候補の重みは指数的に増えるので、A はすべての候補を整合的に保てる。

xij+1={xij,i∈Pj,qxij,i∉Pj,Tj=∑ixijx_i^{j+1}=\begin{cases}x_i^j,&i\in P_j,\\ qx_i^j,&i\notin P_j,\end{cases}\qquad T_j=\sum_i x_i^j
詳しい解説

1.99<p<q<21.99<p<q<2 を選び、十分大きい k に対し 1.99k≤n<pk−11.99^k\le n<p^k-1 かつ (p/q)k≤2−q(p/q)^k\le2-q を満たす整数 n を取る。N=n+1N=n+1 個の候補から始め、xi0=1x_i^0=1 とすると T0=N≤pk<qkT_0=N\le p^k<q^k。質問 D に対する二つの次の総和は T(D)=∑i∉Dqxi+∣D∣T(D)=\sum_{i\notin D}qx_i+|D| と T(Dc)=∑i∈Dqxi+∣Dc∣T(D^c)=\sum_{i\in D}qx_i+|D^c| である。その和は qT+N≤qk+1+pk≤2qkqT+N\le q^{k+1}+p^k\le2q^k だから、表示した条件により一方は qkq^k 以下である。その側を P と選ぶ。帰納的に Tj≤qkT_j\le q^k。ある候補 i が k+1k+1 個連続する P から外れるとその重みは少なくとも qk+1q^{k+1} になり、Tj≤qkT_j\le q^k に反する。よってすべての候補が手順1の各ブロックの合併に含まれる。したがって N=n+1N=n+1 個すべてが可能なのに、B は n 個しか指定できず、勝利を保証できない。