ハムサンドイッチの定理のソースを表示

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

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

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

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

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

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

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

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

==ボルサック・ウラムの定理への転化==
ハムサンドイッチの定理は、{{仮リンク|ボルサック・ウラムの定理|en|Borsuk–Ulam theorem}}を用いることによって、以下に述べる手順で証明される。この証明は、ステインハウスや他の研究者によって与えられたものであり、{{math|1=''n'' = 3}} の場合は[[ステファン・バナフ]]に従う。

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

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

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

その {{math|(''n'' &minus; 1)}}-球面から {{math|(''n'' &minus; 1)}}-次元ユークリッド空間 {{math|'''R'''<sup>''n'' &minus; 1</sup>}} への関数 {{mvar|f}} を、次のように定める:
:{{math|1=''f''(''p'') = }} ({{math|&pi;(''p'')}} の正の方向に含まれる {{math|''A''<sub>1</sub>}} の体積, {{math|&pi;(''p'')}} の正の方向に含まれる {{math|''A''<sub>2</sub>}} の体積, ..., {{math|&pi;(''p'')}} の正の方向に含まれる {{math|''A''<sub>''n''&minus;1</sub>}} の体積).

この関数 {{mvar|f}} は[[連続 (数学)|連続]]である。したがって、{{仮リンク|ボルサック・ウラムの定理|en|Borsuk–Ulam theorem}}により、{{math|1=''f''(''p'') = ''f''(''q'')}} であるような球面 {{mvar|S}} 上の[[対蹠点]] {{mvar|p}} と {{mvar|q}} が存在する。そのような対蹠点 {{mvar|p}} と {{mvar|q}} は、正とする方向が正反対であることを除いて等しいような超平面 {{math|π(''p'')}} と {{math|π(''q'')}} に対応する。したがって、{{math|1=''f''(''p'') = ''f''(''q'')}} は、各 {{math|1=''i'' = 1, 2, ..., ''n'' &minus; 1}} に対して、超平面 {{math|π(''p'')}} （あるいは {{math|π(''q'')}}）の正の方向と負の方向に含まれる {{math|''A''<sub>''i''</sub>}} の体積が等しいことを意味する。以上のことから、{{math|π(''p'')}} （あるいは {{math|π(''q'')}}）が、{{math|''A''<sub>1</sub>, ''A''<sub>2</sub>, …, ''A''<sub>''n''</sub>}} の体積を同時に2等分するような、求めるハムサンドイッチカットであることが分かる。

==測度論の場合==
[[測度論]]において、{{harvtxt|Stone|Tukey|1942}} は1種類の、より一般的な形式のハムサンドイッチの定理を証明した。それらはいずれも、共通とする集合 {{mvar|X}} に含まれる {{mvar|n}} 個の部分集合 {{math|''X''<sub>1</sub>, ''X''<sub>2</sub>, …, ''X''<sub>''n''</sub>}} の2等分に関するものであった。ここで {{mvar|X}} はカラテオドリ[[外測度]]を持ち、各 {{math|''X''<sub>''i''</sub>}} は有限外測度を持つとされる。

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

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

== 参考文献 ==
*{{citation
 | doi = 10.2307/4145019
 | last1 = Beyer | first1 = W. A.
 | last2 = Zardecki | first2 = Andrew
 | issue = 1
 | journal = [[American Mathematical Monthly]]
 | pages = 58–61
 | title = The early history of the ham sandwich theorem
 | url = http://proquest.umi.com/pqdweb?did=526216421&Fmt=3&clientId=5482&RQT=309&VName=PQD
 | volume = 111
 | year = 2004
 | jstor = 4145019}}.
*{{citation
 | doi = 10.1016/S0747-7171(86)80020-7
 | last1 = Edelsbrunner | first1 = H. | author1-link = Herbert Edelsbrunner
 | last2 = Waupotitsch | first2 = R.
 | journal = J. Symbolic Comput.
 | pages = 171–178
 | title = Computing a ham sandwich cut in two dimensions
 | volume = 2
 | year = 1986}}.
*{{citation
 | last1 = Lo | first1 = Chi-Yuan
 | last2 = Steiger | first2 = W. L.
 | contribution = An optimal time algorithm for ham-sandwich cuts in the plane
 | pages = 5–9
 | title = Proceedings of the Second Canadian Conference on Computational Geometry
 | year = 1990}}.
*{{citation
 | last1 = Lo | first1 = Chi-Yuan
 | last2 = Matoušek | first2 = Jiří | author2-link = Jiří Matoušek (mathematician)
 | last3 = Steiger | first3 = William L.
 | doi = 10.1007/BF02574017
 | journal = [[Discrete and Computational Geometry]]
 | pages = 433–452
 | title = Algorithms for Ham-Sandwich Cuts
 | volume = 11
 | year = 1994}}.
*{{citation
 | doi = 10.1016/0196-6774(85)90011-2
 | last = Megiddo | first = Nimrod
 |authorlink= Nimrod Megiddo
 | journal = Journal of Algorithms
 | pages = 430–433
 | title = Partitioning with two lines in the plane
 | volume = 6
 | year = 1985}}.
*{{citation
 | last = Steinhaus | first = Hugo | author-link = Hugo Steinhaus
 | journal = Mathesis Polska
 | pages = 26–28
 | title = A note on the ham sandwich theorem
 | volume = 9
 | year = 1938}}.
*{{citation
 | doi = 10.1215/S0012-7094-42-00925-6
 | last1 = Stone | first1 = A. H.
 | last2 = Tukey | first2 = J. W. | author2-link = John Tukey
 | journal = [[Duke Mathematical Journal]]
 | pages = 356–359
 | title = Generalized "sandwich" theorems
 | url = http://projecteuclid.org/euclid.dmj/1077493229
 | volume = 9
 | year = 1942}}.

== 外部リンク ==
* {{MathWorld|title=Ham Sandwich Theorem|urlname=HamSandwichTheorem}}
*[http://jeff560.tripod.com/h.html ham sandwich theorem] on the [http://jeff560.tripod.com/mathword.html Earliest known uses of some of the words of mathematics] 
*[http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2002/DanielleMacNevin/index.htm Ham Sandwich Cuts] by Danielle MacNevin
*[http://gfredericks.com/sandbox/ham_sandwich An interactive 2D demonstration]

{{analysis-stub}}

{{DEFAULTSORT:はむさんといつちのていり}}

[[Category:位相幾何学の定理]]
[[Category:測度論の定理]]
[[Category:位相空間論]]
[[Category:数学に関する記事]]