パンもハムもチーズも 1 回で半分に、ハム・サンドイッチ定理

パン、ハム、チーズがどんな形でどこに置かれていても、1 回のまっすぐな切り込みで 3 つとも同時に半分にできます。積み重なっていても、ばらばらでも変わりません。

これがハム・サンドイッチ定理です^[1]。$n$ 次元では、$n$ 個の対象を 1 枚の超平面で同時に二等分できる。

以下では $2$ 次元の回転ナイフの議論から始め、ボルスク・ウラムへの帰着、離散版、そして計算の難しさまで扱います。

主張

${\mathbb{R}}^n$ の中に、有限な測度を持つルベーグ可測集合が $n$ 個あるとします。

このとき、$n$ 個すべてを同時に二等分するアフィン超平面が存在します^[1,3]。

$n=3$ ならパン・ハム・チーズを 1 枚の平面で、$n=2$ なら 2 枚のパンケーキを 1 本の直線で。

使う仮定は少ない

形についての仮定がありません。凸でなくてよく、連結でなくてよい。

重なっていても差し支えありません。3 つが同じ場所にあっても、離れていても同じ主張。

要るのは測度が有限であることだけです^[3]。

$n=2$ の回転ナイフ

$2$ 次元で考えます。角度 $\alpha$ を 1 つ決めると、その向きの直線で 1 枚目を二等分するものが存在します。中間値の定理から。

その直線が 2 枚目をどう分けるかを見ます。$\alpha$ を $0$ から $\pi$ まで回すと、直線は同じ位置に戻りますが表裏が入れ替わる^[1]。

したがって 2 枚目の片側の量は、始めと終わりで大小が逆転します。途中で等しくなる角度がある。

回転させて追いかける

角度を回しながら、両方の片寄りを見ます。

直線はどの角度でも青を二等分しています。赤の片寄りだけが動く。

右のグラフが端で符号を変えるので、途中で $0$ を通ります。そこが両方を二等分する角度^[1]。

ボルスク・ウラムへの帰着

一般次元では、超平面を球面でパラメータ表示します。単位ベクトル $v\in S^n$ と定数から超平面 $⟨v,x⟩=c$ を決める。

$v$ ごとに、$n$ 番目の対象を二等分する $c$ を選びます。残る $n-1$ 個について片寄りを並べると、$f:S^{n-1}\to {\mathbb{R}}^{n-1}$ ができる^[1,3]。

対蹠点 $-v$ は同じ超平面を裏返したものに当たり、片寄りの符号が反転します。ボルスク・ウラムから $f(v)=f(-v)$ となる $v$ が存在し、そこで全部の片寄りが $0$。

歴史

シュタインハウスがスコットランドの書に問題として書き、バナッハが 1938 年にボルスク・ウラムを使って解きました^[1,3]。

一般次元はストーンとタキーが 1942 年に扱っています。ストーン・タキーの定理とも呼ばれる。

数学の定理に食べ物の名前が付いた例として、よく引かれます。

ストーン・タキーの一般化

切る道具を超平面に限らなくても成り立ちます。

$n+1$ 個の線型独立な可測関数の線型結合で書ける曲面なら、同じ主張が通る^[1]。

たとえば $2$ 次元で $1,x,y,x^2+y^2$ をとれば、直線だけでなく円でも切れます。3 つの図形を 1 つの円で同時に二等分できる。

例：円で切る

平面上の 3 つの領域を、1 本の円周で同時に二等分できます。

$x^2+y^2-ax-by-c=0$ の形の曲線を考え、$(a,b,c)$ をパラメータにする。直線は半径無限大の場合として含まれます。

道具を増やせば、同時に切れる対象も増える、という構図です^[1]。

離散版

点の有限集合でも同じことが言えます。赤い点と青い点が平面にあれば、両方を同時に二等分する直線が存在する^[1]。

点が直線の上に乗る場合の扱いを決めておきます。どちら側に数えてもよい、とするか、除くとするか。

奇数個のときは正確に半分にできないので、「どちら側も半分未満」という形に読み替えます。

例：離散版を図で見る

赤と青の点を平面に置き、両方を同時に二等分する直線を探します。

直線はつねに赤を 2 対 2 に分けています。青の分かれ方だけが角度で変わる。

$4$ 対 $0$ から $0$ 対 $4$ まで動くので、途中で $2$ 対 $2$ を通ります^[1]。

例：3 つの立体を切る

$n=3$ の元の形が、パン・ハム・チーズの話です。

平面の自由度は 3 で、二等分の条件も 3 つ。数が釣り合っているので解が出る。

サンドイッチが崩れていても、材料が飛び散っていても成り立ちます。位置の仮定が一切ないところが定理の強み。

例：赤 5 点と青 4 点

赤が 5 点なら、直線上に 1 点を乗せて両側 2 点ずつ、とできます。

青が 4 点なら両側 2 点ずつ。同時に達成する直線が必ずある。

離散版は連続版から極限で出せます。点を小さな円板に太らせてから縮める^[1]。

何個までなら切れるか

$n$ 次元で $n$ 個、というのが上限です。超平面のパラメータが $n$ 個の自由度しか持たないため。

向きが $S^{n-1}$ で $n-1$ 個、位置が $1$ 個。合わせて $n$ 個の条件まで課せます。

自由度と条件の数がちょうど釣り合っている、というのがこの定理の形。

ネックレス分割との関係

$t$ 色のビーズを並べたネックレスを 2 人で分けるとき、$t$ 回の切断で足ります^[4]。

連続版はハム・サンドイッチとほぼ同じ形で、区間上の $t$ 個の測度を $t$ 回の切断で二等分する主張。

離散版は連続版から丸めて出します。どちらもボルスク・ウラムが土台^[4]。

計算の難しさ

存在は保証されても、見つける手続きは別の話です。

$2$ 次元では $O(n)$ 時間の最適な算法があります^[1]。$d$ 次元でも $d$ を固定すれば多項式時間。

$d$ を入力の一部にすると難しくなります。ネックレス分割と同値で、PPA 完全と呼ばれる複雑性クラスに入る^[1]。

多項式時間の算法は期待されていません。存在証明が非構成的であることが、そのまま計算の難しさに現れています。

存在証明と構成の隔たり

ボルスク・ウラムの証明は、矛盾を導くか位相不変量を使う形です。切る場所を教えてくれません。

タッカーの補題を使う証明は有限の手続きに落ちますが、三角形分割の細かさが必要なぶん、計算量が跳ね上がります。

「あることは分かるが探せない」という状況の代表例になっています。

よくある誤り

参考文献