第3問
を正の整数とする。Liu Bang と Xiang Yu は長さ の棒を1本持っており、それを2人で分けたい。まず Liu が棒の上に高々 個の点に印を付け、次に Xiang が棒の上に高々 個の点に印を付ける。印を付けられた点はすべて異なる。その後、印を付けられたすべての点で棒を切り、いくつかの断片を作る。続いて、Liu から始めて交互にまだ取られていない断片を1つずつ取っていき、各プレイヤーは自分の断片の長さの合計を最大化することを目指す。各 に対し、Xiang の打ち方にかかわらず Liu が少なくとも長さの合計 を保証できるような最大の値 を求めよ。
詳しい解説
Liu のカットでできる 個の区間を元のセグメントと呼び、部分集合 の長さの和を と書く。互いに素で同時には空でない を取り、 となる向きに選ぶ。 と のセグメントをそれぞれ左から右の順に2列へ並べ、両列の始点を共通の原点に置く。その原点から掃引し、一方の列の累積端点が他方の列のセグメントの端点に達するたび、対応する実際のセグメントをその距離の位置で切る。この結果、短い列が尽きるまでの部分は等しい長さの対になり、長い列には長さ のはみ出しが1つ残る。 の外の元セグメントはすべて二等分し、はみ出しの中に完全に入る の元セグメントも二等分するので、はみ出しで未対の断片が交互和に余分な寄与を作らない。回数を正確に数える。はみ出しに完全に入る S のセグメント数を q とする。T 列が終わる前の S 列には、S のセグメント数から q と1を引いた数以下の内部端点があり、T 列にはセグメント数より1つ少ない内部端点がある。各端点は高々1つの鏡映カットを生むので、鏡映段階は S の個数と T の個数の和から q と2を引いた数以下である。はみ出しの q 個と S,T の外の残りのセグメントを二等分すると、合計は高々 n-1、従って n 以下である。T が空なら、n+1 個のうち1個を残して他を二等分すれば n 回で済む。 すべての対は同じ長さの相手を持つ。大きさ順の列では等しい対の寄与は で符号が逆になって相殺され、最後にはみ出しの末端にある1つの断片だけが残り得る。その長さは 以下である。よって Xiang は を保証できる。