第3問

n

を正の整数とする。Liu Bang と Xiang Yu は長さ

1

の棒を1本持っており、それを2人で分けたい。まず Liu が棒の上に高々

n

個の点に印を付け、次に Xiang が棒の上に高々

n

個の点に印を付ける。印を付けられた点はすべて異なる。その後、印を付けられたすべての点で棒を切り、いくつかの断片を作る。続いて、Liu から始めて交互にまだ取られていない断片を1つずつ取っていき、各プレイヤーは自分の断片の長さの合計を最大化することを目指す。各

n

に対し、Xiang の打ち方にかかわらず Liu が少なくとも長さの合計

c

を保証できるような最大の値

c

を求めよ。

ステップ 3/5: 2^(n+1) 個の部分集合和に対する鳩の巣原理が Liu の上界を与える

前のステップ次のステップ

2^{n+1}\ \text{subset sums }\Sigma(S)\in[0,1]\ \Longrightarrow\ \exists\,S\ne T:\ 0\le\Sigma(S)-\Sigma(T)\le\frac1{2^{n+1}-1}\ \Longrightarrow\ G\le\frac1{2^{n+1}-1}

詳しい解説

$S$ が $n+1$ 個のセグメントの $2^{n+1}$ 個すべての部分集合を動くとき、和 $\Sigma(S)$ はすべて $[0,1]$ に属し、 $\Sigma(\varnothing)=0$ 、 $\Sigma(\text{all})=1$ である。 $[0,1]$ を長さ $\tfrac1{2^{n+1}-1}$ の $2^{n+1}-1$ 個の小区間に分けると、鳩の巣原理により $0\le\Sigma(S)-\Sigma(T)\le\tfrac1{2^{n+1}-1}$ を満たす相異なる2つの部分集合 $S,T$ が存在する。両方から $S\cap T$ を取り除けば $\Sigma(S)-\Sigma(T)$ を変えずに $S,T$ を互いに素にできるので、ステップ2より Xiang は $G\le\tfrac1{2^{n+1}-1}$ 、すなわち Liu の合計が高々 $\tfrac12\bigl(1+\tfrac1{2^{n+1}-1}\bigr)=\tfrac{2^n}{2^{n+1}-1}$ であることを保証できる。