MathLabs

第3問

nn を正の整数とする。Liu Bang と Xiang Yu は長さ 11 の棒を1本持っており、それを2人で分けたい。まず Liu が棒の上に高々 nn 個の点に印を付け、次に Xiang が棒の上に高々 nn 個の点に印を付ける。印を付けられた点はすべて異なる。その後、印を付けられたすべての点で棒を切り、いくつかの断片を作る。続いて、Liu から始めて交互にまだ取られていない断片を1つずつ取っていき、各プレイヤーは自分の断片の長さの合計を最大化することを目指す。各 nn に対し、Xiang の打ち方にかかわらず Liu が少なくとも長さの合計 cc を保証できるような最大の値 cc を求めよ。
ステップ 4/5: Liu の 1 : 2 : 4 : ... : 2^n 分割が Xiang の上界を与える
前のステップ次のステップ
segments 12n+1−1,22n+1−1,…,2n2n+1−1:x2+x4+⋯+x2k≤2n−1+2n−2+⋯+2n−k2n+1−1\text{segments }\frac{1}{2^{n+1}-1},\frac{2}{2^{n+1}-1},\ldots,\frac{2^n}{2^{n+1}-1}:\qquad x_2+x_4+\cdots+x_{2k}\le\frac{2^{n-1}+2^{n-2}+\cdots+2^{n-k}}{2^{n+1}-1}
詳しい解説

逆向きに、棒を 2n+1−12^{n+1}-1 倍に拡大し、Liu のカットで n+1n+1 個の元セグメントの長さを 1,2,4,…,2n1,2,4,\ldots,2^n とする。Xiang のカット後、ステップ1のように全断片を並べる。k=1,…,nk=1,\ldots,n について x2+x4+⋯+x2k≤2n−1+2n−2+⋯+2n−kx_2+x_4+\cdots+x_{2k}\le2^{n-1}+2^{n-2}+\cdots+2^{n-k} を帰納法で示す。k=1k=1 では x2≤2n−1x_2\le2^{n-1} である。実際、2n−12^{n-1} より長い断片は長さ 2n2^n の唯一の元セグメントにしか入れず、そのような互いに素な断片を2つ入れることはできない。k−1k-1 まで正しく、kk で初めて破れると仮定する。k−1k-1 に対応する上界と次の上界の差から x2k>2n−kx_{2k}>2^{n-k} を得る。断片は整列しているので x1,…,x2kx_1,\ldots,x_{2k} はすべて 2n−k2^{n-k} より真に長い。長さが高々 2n−k2^{n-k} の元セグメントから切り出した断片はこの長さになれないので、これら 2k2k 個は長さ 2n−k+1,…,2n2^{n-k+1},\ldots,2^n の最大の kk 個の元セグメントだけに完全に含まれる。従って x1+⋯+x2kx_1+\cdots+x_{2k} はその合計 2n−k+1+⋯+2n2^{n-k+1}+\cdots+2^n 以下である。整列により各組で x2i−1≥x2ix_{2i-1}\ge x_{2i} なので、偶数番目の和はその半分、すなわち 2n−k+⋯+2n−12^{n-k}+\cdots+2^{n-1} 以下となり、kk での破れに矛盾する。これで帰納法が示され、厳密不等号により重なるカットや零長断片も極限操作なしに扱える。