ピザの定理
 |
初等幾何学におけるピザの定理（ピザのていり、英: pizza theorem）は、円板をある方法で切り分けると、2つの部分の面積を等しくすることができるという定理である。
p を円板内部の任意の点とし、n を 8 以上の 4 の倍数とする。まず p を通る任意の直線に沿って円板を切り、直線を p を中心に 2π/n ラジアンずつ回転させてはそれに沿って円板を切るという操作を計 n/2 − 1 回繰り返し、n/2 本の直線で円板を n 個の部分に切り分ける。そして時計回りまたは反時計回りに各部分に番号を順に振る。このとき、
- 『奇数番目の部分の面積の和は、偶数番目の部分の面積の和に等しい(Upton 1968)。』
ピザの定理という名称は、この切り方が伝統的なピザの切り方に似ていることに由来している。この定理によれば、2人で1枚のピザを分けるときは、このように切ってから一切れずつ交互に取っていけば取り分がちょうど同じになることがわかる。
歴史
ピザの定理は元々は チャレンジ問題として出題された(Upton 1968)。マイケル・ゴールドバーグ(Michael Goldberg)は各部分の面積を代数的に表し、直接的な式変形をすることでこれを証明した。Carter & Wagon (1994a)はシルエットパズルを解く要領で別証を与えた。各部分をさらに小図形へと細分して、奇数番目と偶数番目に合同な図形のペアを作り出す方法を示したのである。Frederickson (2012)は全ての場合（n = 8, 12, 16, ...）に通用するようなシルエットパズルの手法での証明を与えた。
一般化
領域の数が4の倍数であるという条件は必須である。ドン・コッパースミスが証明したように、円板を4個、または4の倍数でない数に分割した場合、一般的には面積を等しくすることができない。Mabry & Deiermann (2009)はCarter & Wagon (1994b)にある問題への解答として、この定理のより精緻な証明を行ったが、その証明では2つのピースの集まりの面積が等しくない場合、どちらがより大きい方かをも決定できる。特に、領域の数が 2 (mod 8) で、どの割線も円板の中心を通らないときは、中心を含むほうのピースの集まりのほうが他方より面積が小さくなる。逆に、領域の数が 6 (mod 8) でどの割線も円板の中心を通らないときは、中心を含むほうのピースの集まりのほうが他方より面積が大きくなる。直線による切り分けでは円板を奇数個に分けることはできない。直線が円板の中心を通る場合は、領域の数がいくつであろうと円板を等面積に分けられる。
Mabry & Deiermann (2009)はまた、ピザが公平に二分されるときは、耳の部分も公平に二分されることを述べた。ここでの「耳」は、弧（弧長）のことと解釈しても良いし、円板の外周と、半径の小さい同心円（切り分けの中心を内部に含むものとする）とで囲まれた円環のことだと解釈しても良い。後者の場合、2つの同心円板はいずれも公平に二分されているため、それらの差の集合どうしも等しい面積を持つことになる。しかし切り分けが不公平な場合、スライスの面積が大きい方を選ぶと、実は耳が小さい方を選ぶことになってしまう。
Hirschhorn et al. (1999)にあるように、どのトッピングも切り分けの中心 p を含む円板上（ピザ全体と同心円でなくともよい）に分布している限り、ピザの公平な分割はトッピングの公平な分割でもある。
関連した結果
Hirschhorn et al. (1999)は、ピザの定理と同じように n 枚のスライスに切り分けられたピザは、n/4 人でも分け合えることを示した。例えばピザが12枚に切り分けられているなら、2人だけでなく、3人でも同量ずつに分け合える。しかし5人に公平に分配するためには、ピザは20片に切り分けねばならないだろう。
Cibulka et al. (2010)とKnauer, Micek & Ueckerdt (2011)は、ダン・ブラウンとピーター・ウィンクラーが提出したより大規模な分配問題に対するある保証を得るため、ピザの自由な取り分けに関するゲーム理論を研究した。この研究においては、ピザは放射状にカットされ（各部分の角度は同一であるとは限らない）、ピザを分け合う2人のプレイヤーは、既に食べられている片の隣の片を交互に取っていけるという設定である。2人がいずれも取り分を最大化するようピザを取っていくと、先手は最低でもピザ全体の 4/9 が食べられることが保証される。かつ、決して 4/9 より多くは食べられないような最初の切り方が存在する。公平分割（fair division）問題またはケーキ分割問題（cake cutting problem）では、類似の設定で、各プレイヤーは異なった取り分の評価基準を持ってよいものとする。例えば、あるプレイヤーは乗っているペパロニの量を最大化するよう行動し、また別のプレイヤーはチーズを最大化したい、といった具合である。
関連した事項
ピザのスライスに関係のある他の数学的結果に、怠け仕出し屋の数列と呼ばれる整数列がある。これは、与えられた整数回数の直線による切り分けで、1枚のピザを最大でいくつの部分に分割できるかを表す数列である。この他ハムサンドイッチの定理は3次元の物体の切り分けに関する定理だが、これの2次元版を考えると、どんなに歪んだピザであったとしても、切り方を注意深く選べば、生地全体と耳の部分を同時に等分するよう直線で二分割できる。また同定理の3次元版によれば、生地・トマト・チーズを全て同体積に二分割するような平面による切断が存在することがわかる。
参考文献
- Carter, Larry; Wagon, Stan (1994a), “Proof without Words: Fair Allocation of a Pizza”, Mathematics Magazine 67 (4): 267, doi:10.1080/0025570X.1994.11996228, JSTOR 2690845.
- Carter, Larry; Wagon, Stan (1994b), “Problem 1457”, Mathematics Magazine 67 (4): 303–310, JSTOR 2690855.
- Cibulka, Josef; Kynčl, Jan; Mészáros, Viola; Stolař, Rudolf; Valtr, Pavel (2010), “Solution of Peter Winkler's pizza problem”, Fete of Combinatorics and Computer Science, Bolyai Society Mathematical Studies, 20, János Bolyai Mathematical Society and Springer-Verlag, pp. 63–93, arXiv:0812.4322, doi:10.1007/978-3-642-13580-4_4, ISBN 978-3-642-13579-8.
- Hirschhorn, J.; Hirschhorn, M. D.; Hirschhorn, J. K.; Hirschhorn, A. D.; Hirschhorn, P. M. Hirschhorn (1999), “The pizza theorem”, Austral. Math. Soc. Gaz. 26: 120–121.
- Frederickson, Greg (2012), “The Proof Is in the Pizza”, Mathematics Magazine 85 (1): 26–33, doi:10.4169/math.mag.85.1.26, JSTOR 10.4169/math.mag.85.1.26.
- Knauer, Kolja; Micek, Piotr; Ueckerdt, Torsten (2011), “How to eat 4/9 of a pizza”, Discrete Mathematics 311 (16): 1635–1645, arXiv:0812.2870, doi:10.1016/j.disc.2011.03.015.
- Mabry, Rick; Deiermann, Paul (2009), “Of Cheese and Crust: A Proof of the Pizza Conjecture and Other Tasty Results”, American Mathematical Monthly 116 (5): 423–438, doi:10.4169/193009709x470317, JSTOR 40391118.
- Ornes, Stephen (December 11, 2009), “The perfect way to slice a pizza”, New Scientist.
- Upton, L. J. (1968), “Problem 660”, Mathematics Magazine 41 (1): 42, JSTOR 2687962. Solution by Michael Goldberg.
脚注
外部リンク
- Weisstein, Eric W. "Pizza Theorem". mathworld.wolfram.com (英語).
- Sillke, Torsten, Pizza Theorem 2009年11月24日閲覧。