ハムサンドイッチの定理

数学の測度論におけるハムサンドイッチの定理（ハムサンドイッチのていり、英: ham sandwich theorem）、またはストーン・テューキーの定理（英: Stone–Tukey theorem. アーサー・H・ストーン（英語版）とジョン・テューキーに因む）とは、 $n$ 次元空間内に与えられた $n$ 個の可測な「物体」に対して、それぞれの量を一度に等分することが出来るような $(n - 1)$ 次元超平面が存在することについて述べた定理である。ここでの「量を等分する」という文が意味を持つために、そのような「物体」は有限測度（あるいは有限外測度）の集合でならなければならない。

名前の由来

ハムサンドイッチの定理は、 $n = 3$ である場合、3つの「物体」としてハムとそれを挟む2枚のパン（すなわち、サンドイッチ）を考えることで、1回のナイフカット（数学的に言うと平面）でそれらすべての量をそれぞれ半分に出来るような切り方が必ず存在する、と言い換えることが出来る。2次元 ( $n = 2$ ) の場合、この定理はパンケーキの定理として知られ、皿の上に載せられた2枚の限りなく薄いパンケーキを、一回のナイフカット（数学的に言うと直線）でそれらすべての量をそれぞれ半分に出来るような切り方が必ず存在する、と言い換えられる。

ハムサンドイッチの定理はしばしばハムチーズサンドイッチの定理とも呼ばれ、この場合 $n = 3$ での3つの物体としては

ハム
スライスチーズ
2枚のパン（1つの非連結な物体と見なす）

が選ばれる。この場合の定理は「与えられたハムチーズサンドイッチに対し、そのハム、チーズ、パンの量がそれぞれ半分となるようなサンドイッチの切り方が必ず存在する」と言い換えられる。

なお、はさみうちの原理を指してサンドイッチ定理 (sandwich theorem) と呼ぶことがあるが、本項におけるハムサンドイッチの定理とは無関係である。

歴史

ハムサンドイッチの定理についてまとめた Beyer & Zardecki (2004) によれば、平面上の3つの物体を等分する $n = 3$ のケースを考えた初めての研究は Steinhaus (1938) であるとされている。問題の提示はスタインハウス（英語版）によりなされ、その解決はステファン・バナフによりなされた（証明にはボルサック・ウラムの定理（英語版）が用いられた）。提示された問題には、2種類の文章が存在した。1つ目は公式的なものとして、「任意に配置された3つの物体を、ひとつの適切な平面によって等分することは常に可能であるか？」であり、2つ目は非公式的なものとして、「肉と骨と油が等分されるように、ミートカッターの下にハムを配置することは可能か？」であった。

より近代的なアプローチを示した文献として、ストーン・テューキーの定理とも呼ばれるきっかけとなった、Stone & Tukey (1942) が挙げられる。この論文では、測度を含むより一般的な設定の下での、定理の $n$ 次元版の証明が行われた。ある査読者からの情報によると^[誰?]、 $n = 3$ の場合の証明はスタニスワフ・ウラムによるものとされているが、Beyer & Zardecki (2004) はこれを間違いだと指摘している（ボルサック・ウラムの定理によって「ウラムは確かに問題解決への根本的な貢献を与えた」とは注意されている）。

ボルサック・ウラムの定理への転化

ハムサンドイッチの定理は、ボルサック・ウラムの定理（英語版）を用いることによって、以下に述べる手順で証明される。この証明は、ステインハウスや他の研究者によって与えられたものであり、 $n = 3$ の場合はステファン・バナフに従う。

今、2等分しようとしている $n$ 個の物体を $A 1, A 2, \dots, A n$ と表す。 $n$ 次元ユークリッド空間 $R n$ に埋め込まれている、原点を中心とする $n - 1$ 次元単位球面を $S$ と表す。その球面 $S$ の表面上の任意の点 $p$ に対して、原点から $p$ への法線ベクトルに直交する（必ずしも 0 を中心としない）有向アフィン超平面の連続体を、そのベクトルの指す方向である各超平面の「正の方向」によって定義することができる。

中間値の定理により、そのような超平面のすべての族には、有界な物体 $A n$ を2等分するような超平面が少なくとも1つ含まれている。すなわち、一つの極端な場合には、そのような「正の方向」に含まれるような $A n$ の体積は全くなく、またもう一方の極端な場合には、 $A n$ のすべての体積がそのような「正の方向」に含まれるため、その中間には必ずちょうど半分の $A n$ の体積が「正の方向」に含まれるような場合が存在する、ということである。

もしもその族にそのような超平面が1つ以上含まれているのなら、 $A n$ が2等分される各 translations の間隔の中点を選ぶことにより、唯一つだけ超平面を決めることができる。したがって、球面 $S$ の表面上の各点 $p$ に対して、原点から $p$ へのベクトルと直交し、かつ $A n$ を2等分するような超平面 $π(p)$ を得ることができる。

その $(n - 1)$ -球面から $(n - 1)$ -次元ユークリッド空間 $R n - 1$ への関数 $f$ を、次のように定める:

f (p) =

(

π(p)

の正の方向に含まれる

A 1

の体積,

π(p)

の正の方向に含まれる

A 2

の体積, ...,

π(p)

の正の方向に含まれる

A n -1

の体積).

この関数 $f$ は連続である。したがって、ボルサック・ウラムの定理（英語版）により、 $f (p) = f (q)$ であるような球面 $S$ 上の対蹠点 $p$ と $q$ が存在する。そのような対蹠点 $p$ と $q$ は、正とする方向が正反対であることを除いて等しいような超平面 $π(p)$ と $π(q)$ に対応する。したがって、 $f (p) = f (q)$ は、各 $i = 1, 2, ..., n - 1$ に対して、超平面 $π(p)$ （あるいは $π(q)$ ）の正の方向と負の方向に含まれる $A i$ の体積が等しいことを意味する。以上のことから、 $π(p)$ （あるいは $π(q)$ ）が、 $A 1, A 2, \dots, A n$ の体積を同時に2等分するような、求めるハムサンドイッチカットであることが分かる。

測度論の場合

測度論において、Stone & Tukey (1942) は1種類の、より一般的な形式のハムサンドイッチの定理を証明した。それらはいずれも、共通とする集合 $X$ に含まれる $n$ 個の部分集合 $X 1, X 2, \dots, X n$ の2等分に関するものであった。ここで $X$ はカラテオドリ外測度を持ち、各 $X i$ は有限外測度を持つとされる。

一つ目の一般的な形式化は、次のようなものである: 適切に制限された任意の実関数 $f:S^{n}\times X\to \mathbb {R}$ に対して、 $n$ -球面 $S n$ に含まれるある点 $p$ が存在し、 $X$ を $f (s, x) < 0$ と $f (s, x) > 0$ に分割するようなその表面が、 $X 1, X 2, \dots, X n$ の各外測度を同時に2等分する。この証明には、再びボルサック・ウラムの定理が用いられる。この定理は、 $f (s, x) = s 0 + s 1 x 1 + ... + s n x n$ とすることによって標準的なハムサンドイッチの定理を一般化するものである。

二つ目の形式化は次のようなものである：正測度の $X$ の任意の部分集合において線型独立であるような、 $X$ の $n + 1$ 個の任意の可測関数 $f 0, f 1, \dots, f n$ に対して、ある線型結合 $f = a 0 f 0 + a 1 f 1 + ... + a n f n$ が存在し、 $X$ を $f (x) < 0$ と $f (x) > 0$ へ2等分するようなその表面 $f (x) = 0$ は、 $X 1, X 2, \dots, X n$ の各外測度を同時に2等分する。この定理は、 $f 0 (x) = 1$ とし、また各 $i > 0$ に対して $f i (x)$ を $x$ の $i$ 番目の座標とすることによって、標準的なハムサンドイッチの定理を一般化するものである。

参考文献

Beyer, W. A.; Zardecki, Andrew (2004), “The early history of the ham sandwich theorem”, American Mathematical Monthly 111 (1): 58–61, doi:10.2307/4145019, JSTOR 4145019 .
Edelsbrunner, H.; Waupotitsch, R. (1986), “Computing a ham sandwich cut in two dimensions”, J. Symbolic Comput. 2: 171–178, doi:10.1016/S0747-7171(86)80020-7 .
Lo, Chi-Yuan; Steiger, W. L. (1990), “An optimal time algorithm for ham-sandwich cuts in the plane”, Proceedings of the Second Canadian Conference on Computational Geometry, pp. 5–9 .
Lo, Chi-Yuan; Matoušek, Jiří; Steiger, William L. (1994), “Algorithms for Ham-Sandwich Cuts”, Discrete and Computational Geometry 11: 433–452, doi:10.1007/BF02574017 .
Megiddo, Nimrod (1985), “Partitioning with two lines in the plane”, Journal of Algorithms 6: 430–433, doi:10.1016/0196-6774(85)90011-2 .
Steinhaus, Hugo (1938), “A note on the ham sandwich theorem”, Mathesis Polska 9: 26–28 .
Stone, A. H.; Tukey, J. W. (1942), “Generalized "sandwich" theorems”, Duke Mathematical Journal 9: 356–359, doi:10.1215/S0012-7094-42-00925-6 .

外部リンク

Weisstein, Eric W. "Ham Sandwich Theorem". mathworld.wolfram.com (英語).
ham sandwich theorem on the Earliest known uses of some of the words of mathematics
Ham Sandwich Cuts by Danielle MacNevin
An interactive 2D demonstration

この項目は、解析学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。