ハム・サンドイッチ定理

ハム・サンドイッチ定理はBorsuk-Ulamの定理の応用として有名な結果です。$n$ 個の対象を1つの超平面で同時に二等分できることを主張します。

定理の主張

${\mathbb{R}}^n$ 内の $n$ 個の有界可測集合 $A_1,\dots ,A_n$（それぞれ正の測度を持つ）に対して、すべてを同時に二等分する超平面が存在する。

二等分とは、超平面の両側に各集合の測度の半分ずつが含まれることです。

$n=3$ の場合（ハム・サンドイッチ）

${\mathbb{R}}^3$ で3つの対象（パン2枚とハム1枚）を1つの平面で同時に二等分できます。

サンドイッチを1回の直線的な切断で、パン・ハム・パンをすべて公平に分けられるという意味で、この定理は「ハム・サンドイッチ定理」と呼ばれます。

$n=2$ の場合

平面上の2つの有界可測集合を、1本の直線で同時に二等分できます。

ピザとフライドポテトを1本の直線で同時に半分ずつに分けられます。

Borsuk-Ulamからの証明

超平面は法線ベクトル $v\in S^{n-1}$ と原点からの距離 $t\in \mathbb{R}$ で指定できます。

$f:S^{n-1}\to {\mathbb{R}}^{n-1}$ を、$f(v)=(t_1(v),\dots ,t_{n-1}(v))$ で定義します。$t_i(v)$ は、法線 $v$ の超平面で $A_i$ を二等分するときの距離パラメータです。

各 $t_i(v)$ は連続で、$t_i(-v)=-t_i(v)$ です（法線を逆にすると距離の符号が変わる）。

したがって $g(v)=(t_1(v)-t_n(v),\dots ,t_{n-1}(v)-t_n(v)):S^{n-1}\to {\mathbb{R}}^{n-1}$ を考えると、Borsuk-Ulamの定理から $g(v)=g(-v)$ となる $v$ が存在します。

この $v$ に対して $t_1(v)=\cdots =t_n(v)$ となり、すべての集合を同時に二等分する超平面が存在します。

離散版

$n$ 個の有限点集合に対しても、各集合を（ほぼ）二等分する超平面が存在します。点が超平面上にないとき、両側の点数の差は高々1です。

一般化：質量の等分割

より一般に、${\mathbb{R}}^n$ 上の $n$ 個の絶対連続測度を同時に二等分する超平面が存在します。

Stone-Tukey定理

$n$ 個の測度を $k$ 等分するには、$k-1$ 個の平行な超平面が必要です。Stone-Tukey定理はこの一般化を与えます。

応用：公平分割

ハム・サンドイッチ定理は公平分割問題の数学的基礎となります。

計算複雑性

2次元の場合、2つの凸多角形を二等分する直線は $O(n)$ 時間で計算できます。一般の次元では問題は複雑になります。

関連する結果

パンケーキ定理：${\mathbb{R}}^2$ の2つの有界集合を1本の直線で二等分できる（$n=2$ の場合）。