数理解析研究所講究録1120 巻 1999 年 41-50

41

二次元ハムサンドイッチ定理の–般化とその周辺
A Genaralization of 2-Diminsion Ham Sandwich Theorem and Related Topics
伊藤大雄

ITO Hiro

豊橋技術科学大学情報工学系〒 441-8580 豊橋市天伯町字雲雀ケ丘 1-1

ito@tutics.tut.

$\mathrm{a}\mathrm{c}$.jp

摘要: 「平面上に赤点 $pn$ 個、 白点 $pm$ 個が配置されている時 (但し任意の 3 点は同–直線上に無いとする) 、互いに重ならな個の凸領域が存在し、 各領域は丁度赤点 個、 白点 $m$ 個$\iota’\mathrm{a}_{P}$$n$を含む様にできる」 という金子・加納の予想は、 $p=2$ とすると有名なハムサンドイッチ定理(但し 2 次元版) になり、それをエレガントに–般化した重要な予想であった。本稿ではこの予想に対し 1998 年に伊藤らによって与えられた証明の概略を紹介する。 さらに関連した話題にも言及する。

キーワード: ハムサンドイッチ定理, 平面, 点集合, 凸包, 均等分割

1

はじめに
3 つの自然数 $m\geq 2,$ $n\geq 2,$ $q\geq 2$ を考える。

と$S_{w}$

は共通要素を持たないものとし、 さらに$|S_{r}|=nq,$ $|S_{w}|=mq$とする。便宜上$S_{r}$$S_{r}$$S_{r}\cup S_{w}$を赤点集合、$S_{w}$

を各々平面上の点集合とする。但し、$S_{r}$

内の点はどの 3 点も $-$ 直線上に無いものとする。

$S_{w}$

定理を証明する。
定理 1とを白点集合と呼ぶことにする。本稿では下記の(無 1 参照)
は 個の部分集合,,に分割でき、 (i) 任意の $1\leq i<j\leq q$
に対し conv $(P_{i})\cap conv(P_{j})=\emptyset$ であり (但し conv$(P)$ は $P$ の凸包) かつ (ii)
任意の $1\leq i\leq q$ に対し$S_{r}\cup S_{w}$$P_{1},$$q$$P_{2}$$P_{q}$、$|P_{i}\cap S_{r}|=n$

かつ $|P_{i}\cap Sw|=m$ である様にできる。

口

この定理は金子・加納によって与えられた予想 [9] を証明したものである。 その予想は $q=2$ の時には有名な平面ハムサンドイッチ定理と等価となるため、正しいことが分る。 さらに–般の に対$[1, arrow 6]$$q$

しても $n=1,2$ ならば予想が成立することが金子・加納によって証明された( $n=1$ 1 ま文献 $[9]_{\text{、}}n=2$
は文献 [10]
最近その予想が完全 1 こ成立する (すなわち–般の $q,n,$ $m$ に対して成立する) ことが伊藤ら
酒井 [13] Bespamyatnikh ら [3] の 3 グループによってほぼ同時に証明された。
これらの 3 つの$)_{0}$$[7]_{\backslash }$$\text{、}$証明は似ている部分も多いが重要な部分がかなり異なっている。本稿では伊藤らの証明を解説する。 なお、詳細は文献 [8] を参照されたい。
上記 3 グループの証明は全て以下の定理を証明することによっている。
定理 2 任意のが$S_{r}$,$S_{w}$

に対し、 3 つの整数 $q_{1}\geq 1,$ $q_{2}\geq 1,$ $q_{3}\geq 0(q_{1}+q_{2}+q_{3}=q)$ が存在し、(i) 任意の $1\leq i<j\leq 3$ に対し conv$(Pi)\cap \mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}(P_{j})=\emptyset\text{、}$$S_{r}\cup S_{w}$42$\mathrm{x}$:red point$\text{口}$: white point

図 1: 定理 1 の例: $n=1,$ $m=2,$ $q=5$ の場合$l$$r(ab)$

図 2: 直線

(c)

(b)

(a)

$l$

に対する開領域$\mathrm{R}(l)$と$\mathrm{L}(l)_{\text{、}}$

半直線(ii) 任意の $1\leq i\leq 3$ に対し $|P_{i}\cap S_{r}|=q_{i}n$ かつを満たすように$P_{1}$,$P_{2}$,$P_{3}$$\mathrm{r}(ab)_{\text{、}}$

くさび領域$\mathrm{w}\mathrm{d}\mathrm{g}(aob)$と$\mathrm{w}\mathrm{d}\mathrm{g}(b_{\mathit{0}}a)$.

$|P_{i}\cap s_{w}|=q_{i}m\text{、}$口に分割できる。

定理 2 を利用すれば定理 1 は数学的帰納法によって証明することができる。 $q=2$ については、 定理 2は平面ハムサンドイッチ定理そのものなので成立することは明らかである。 よって以下では $q\geq 3$ と仮定して話を進める。

2

準備

2.1

諸定義

本稿では特に断わらない限り直線とは方向を持った有向直線であり、とする。 直線 l\downarrow よ平面を$l,$$\mathrm{R}(l),$$\mathrm{L}(\iota)$の 3 つに分割する、但し$\mathrm{R}(l)$と上の点を通過しないもの
は各々l の右側にある開半平$s_{r^{\cup S}w}$$\mathrm{L}(l)$面と左側にある開半平面を表す (図 2(a) 参照) 直御はそれに含まれる 2 点 $a,$ を用いて諾の様に表すことができる、但し $a,$ はこの順口上に表れるものとする (図 2( 参照)。点 から発する半直上と表される (図 2(b) 参照) 特に断わらない限り、 半直線も線が点 $b(\neq a)$ を通る時の点を通らないものとする。
$b$

。

$b$

$\mathrm{r}(ab)$$\mathrm{a}\rangle$$a$$S_{r}\cup S_{w}$$\circ$43とを考える。 b\in R(詫) の場合、で作られる角のうち小さい方(大きい方) を $\angle aob(\angle boa)$ で表す oは、 /aob\leq \mbox{\boldmath $\pi$}であるとき
であるときと定義する (図 2(c) 参照) 。平面上の任意の点集合 に対し、 の凸包 ( $S$ を含
む極小領域) を conv $(s)$ と表す。平面上の任意の領域 $W$ に対し、 in $(W),$を各々内部領域、外部領域、 境界領域を表すものとする。

平面上の異なる 3 点 $a,$$b,$$\mathrm{r}(oa)$$\mathit{0}$$\mathrm{r}(ob)$$\mathrm{w}\mathrm{d}\mathrm{g}(aob\rangle$$\mathrm{R}(oa)\cap.\mathrm{L}(ob)\text{、}\angle aob>\pi$$\mathrm{R}(oa)\cup \mathrm{L}(ob)$

$S$

$S$

$\mathrm{e}\mathrm{x}(W),$$U=\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{V}\langle Sr^{\cup}Sw)$$x,y\in \mathrm{b}\mathrm{o}(U),$$z\in \mathrm{i}\mathrm{n}(U)$に対し、する。 arc $(xy)$ の長さを arc-diの和で定義される)。

2.2$q_{1},$$q_{2}$

, and

$qs$

.

に関わらず–定なので、 これを arc $(xy)$ と表現で表す (arc $(xy)$ は折れ線であるので arc-dist $(xy)$ は各線分の長さ$\mathrm{w}\mathrm{d}\mathrm{g}(xzy)\cap \mathrm{b}\mathrm{o}(U)$$s\mathrm{t}(xy)$$\mathrm{b}\mathrm{o}(W)$

は

$z$

の存在

次の補題は金子加納 [9] によって示された。
と補題 A
をのとき、 任意の整数$l_{1}$$|\mathrm{L}(l_{1})\cap S_{r}|=|\mathrm{L}(l_{2})\cap s_{r}|$$l_{2}$$|\mathrm{L}(l_{3})\cap S_{w}|=i$

(但し

$i$

かつ $|\mathrm{L}(l_{1})\cap s_{w}|<|\mathrm{L}(\iota_{2})\cap S_{w}|$ を満たす 2 直線とする。 こ$|\mathrm{L}(\iota_{1})\cap S_{w}|\leq i\leq|\mathrm{L}(\iota_{2})\cap S_{w}|$を満たす直線$l_{3}$) に対し、$|\mathrm{L}(\iota_{3})\cap S_{r}|=|\mathrm{L}(\iota_{1})\cap S_{r}|$かつが存在する。

口

もしある $k(1\leq k\leq q-1)$ に対し $\text{ }|\mathrm{L}(l)\cap S_{r}|=kn$ かつ $|\mathrm{L}(\iota)\cap s_{w}|=km$ である様な直線が存在するならば、 $\{q_{1}=k, q_{2}=q-k, q_{3}=0\}$ は定理 2 の条件を満たすことになる。 よって補題 A より、任意の整数 $k(1\leq k, \leq q-1)$ に対し、 (i)である任意の直線 に対して $|\mathrm{L}(l)\cap S_{w}|<km$
であるか、 (ii)$\cap s_{r}|=kn$ である任意の直線に対して $|\mathrm{L}(l)\cap S_{w}|>km$ であるかの、 どちらか、$|\mathrm{L}(\iota)\cap s_{r}|=kn$$|\mathrm{L}(\iota\rangle$

$l$

$l$

方を満たすと仮定して良い。 この仮定から、 各が出来る、 すなわち

$l$

$k$

$k$

には LOW か HIGH のどちらかのラベルを付けることが (i) を満たすならばラベル LOW を付し、 (ii) を満たすならばラベル付すことが出来る。以上の考察の下で次の補題が得られる。

HIGH が補題 1ラベ) が等しくかつ $q_{1}+q_{2}+q_{3}=q$ である 3 整数 $1\leq q_{1},$証明

1 のラベルが LOW であると仮定する。 もし全てのラベルが LOW であるならば $\{1, 1, q-2\}$ が$q_{2},$$q_{3}\leq q-1$が存在する。

口

所望の 3 整数となる。 よって少なくと も一つは HIGH のラベルを持つ整数が存在すると仮定して良い。
さらに、任意の$k\triangleleft$

に対し、

$k$

のラベルと $q-k$ のラベルは、 その定義から、必ず異なっていなければならない。 ラベル HIGH を持つ最小の整数を.

とする。 すると $q-k$ と $-1$ はどちらもラベル LOW をよって持つ。
$\{q-k, k-1,1\}$ は補題 1 の条件を満たす。 1 のラベルが HIGH である場合は、
HIGH と$k$$k$

LOW を入れ替えれば全く同じ議論が成立する。

$\mathrm{Q}.\mathrm{E}$.D.

補題 1 より得られるを考える。 ここで
, q3 のラベルは LOW である と仮定して–般性を失わない。 なぜならばもしそれらのラベルが HIGH ならば、 $S$, とを入れ替えて考えればラベル$q_{1},$ $q_{2},$$\mathrm{r}_{q_{1}},$$q_{3}$$q_{2}$$\mathrm{J}$$S_{w}$

を LOW にできるからである。以下本稿ではここで得られた

本稿では特に断わらない限り分割は常に$q_{1},$$q_{2},$$q_{3}$

を使用する。

$\mathrm{j}$$|P_{i^{\cap}}Sr|=qin$,を満たすものとする。分割が陪口 $S_{w}|=q_{i}m$ も満たす場合、均等分割であると言う。
$U$

の内点

$\mathit{0}$と境界上の 3 点 $a,$

(図 3(a) 参照)o$s_{r^{\cup S}w}$

は

$b,$

$c$

$\mathrm{w}\mathrm{d}\mathrm{g}(boC)$を考える。但し $a,$と$\mathrm{w}\mathrm{d}\mathrm{g}(Coa)$

と

$b,$

$c$

はこの順に時計回りに並んでいるものと るによって 3 分割される。 ここで、 を分割$\text{す}-$$\mathrm{w}\mathrm{d}\mathrm{g}(aob)$$\mathit{0}$

44

$a$

$u$

(a)

(b)

図 3: (a) 分割と (b) T-分割

(d ノ

図 4: 点 $a,$

$b,$

$c,$

$d,$

$e$

及び直線

$l,$

$\mathrm{t}\mathrm{o}\mathrm{p}\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{e}(\iota)$

を分割の足と呼ぶ。 \angle aob\leq \mbox{\boldmath $\pi$}かつ $\angle boc\leq\pi$ かつ \angle coa\leq \mbox{\boldmath $\pi$}であるとき、 その分割は凸であの中心、 $a,$ると言う。 さらにそれらの 3 つの角のうち –つが\mbox{\boldmath $\pi$} に等しいならば、 その分割を T-分割 (T-partition)
$b,$

$c$

(図 3(b) 参照)と呼ぶ

3

主定理の証明

3.1

目標領域

。

$\angle aob=\pi$であるとき、訪を$\mathrm{T}$-分割の上部直線 (top-line) と呼ぶ。

本節では、所望の分割の中心が位置する領域を限定する。
の点を高々–つしか含まない様にとる。さらに$b,c\in \mathrm{b}\mathrm{o}(U)$$a\in \mathrm{b}\mathrm{o}(U)$

を、

$a$

を通る任意の直線がを $|\mathrm{L}(a7)\cap S\varphi|=q_{3}n$ かつ$S_{f}\cup S_{w}\mathrm{J}^{-}--$$|\mathrm{R}(\overline{a}\not\supset)\cap S_{r}|=q2n$でとなるようにとる (もしこの様な点が存在しない場合でをあるようにとる。
をが得られる) 。さらにを満たすよ
も、 を微少に動かせば必ずこのようなうにとる (図 4(a) 参照)
上の 2 点を通る直線の集合を とする。さらに$d\in \mathrm{b}\mathrm{o}(U)$$|\mathrm{L}(^{arrow}bd)\cap S_{r}|=q_{1}n$

$d$

$c$

。

$|\mathrm{R}(C\mathrm{Y})\cap S_{r}|=q1n$$e\in \mathrm{b}\mathrm{o}(U)$$s_{r^{\cup S}w}$$\Gamma’=\mathrm{r}\cup\{\overline{a}\S|s\in S_{r}\cup S_{w}\}$$\Gamma$

とする。
$x$

と

$x\preceq y$$y$を$\mathrm{b}\mathrm{o}(U)$上の任意の 2 点とする。

$\mathrm{a}\mathrm{r}\mathrm{c}- \mathrm{d}\mathrm{i}_{\mathrm{S}\mathrm{t}(a}x$)$\leq \mathrm{a}\mathrm{r}\mathrm{c}- \mathrm{d}\mathrm{i}_{\mathrm{S}}\mathrm{t}(ay)$であるとき、 $x\preceq y$ と表現する。

かつ $x\neq y$ であるならば $x\prec y$ である。

をに対し、 toplineと定義する。
とかつである様な直線とする。
topline の交点を center $(l)$ との交点を $b’(\iota),$ $c’(l)$ とする (但し $b’(l)\prec c’(l)$ )表現する (図 4(b) 参照)。 topline $(l)$ と$l\in\hat{L}$$\hat{L}=\{\overline{a}\not\supset|x\in \mathrm{a}\mathrm{r}\mathrm{c}(bc)\cup\{b, c\}\}-\Gamma’$$q_{2}n$$|\mathrm{R}(\mathrm{t}_{0}\mathrm{p}\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{e}(\iota))\mathrm{n}\mathrm{L}(\iota)\cap s_{r}|=q_{3}n$$\mathrm{b}\mathrm{o}(U)$$(\iota)$$l$$|\mathrm{R}(\mathrm{t}\mathrm{o}\mathrm{p}\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{e}(l))\cap \mathrm{R}(l)\cap S_{r}|=$$(\iota)$。

45

補題 2 任意の直線$l\in\hat{L}$に対し、 center $(l)$ と topline$(\iota)$を以下の条件 (1) $-(4)$ を満足するように定めることができる。

(1) to..p.l.i..n$\mathrm{e}(a?)=\overline{b\sim-}3\text{かつ}\wedge.\iota_{0}\mathrm{P}^{1}\mathrm{i}\mathrm{n}\mathrm{e}(\overline{a}?)=\overline{e}\delta$.

(2) 5enter(d) 切軌跡は折れ線となる。
(3) 任意の$x^{:},\cdot y^{\wedge}.\cdot\in \mathrm{a}\mathrm{r}\mathrm{c}\langle b_{C}$)$-\overline{\mathrm{u}}\{b,c\}(x\prec y)$に対し、$b’(a\not\supset)\prec b’(a\mathrm{B})$かつ $c’(ayarrow)\prec c’(a\mathrm{r})$。

$-\backslash$「「$\mathrm{a}\mathrm{r}\mathrm{c}- \mathrm{d}\mathrm{i}\mathrm{S}P-\cdot:^{\ovalbox{\tt\small REJECT}}\varphi \mathrm{t}(ab"(x\wedge\backslash )\mathrm{n})\mathit{1}\text{と^{}-}$

$(4)$

」 と「

$\mathrm{a}\mathrm{r}\mathrm{c}-\mathrm{d}\mathrm{i}\mathrm{S}\mathrm{t}(aC(x)’)$$a$と center $(a3)$ の距離」は全ての–様連続関数$\angle bax$である。

にの対どれ、かもでしあ. る。

$y$$– \cdot...\cdot.\mathrm{p}’..\underline{.’.}\sim\backslash (\ddot{\mathrm{s}}_{\alpha}r\backslash \underline{\backslash }:.\rangle.\wedge\int_{-}\check{.}\mathrm{f}..\cdot\ovalbox{\tt\small REJECT}\backslash )arrow---\epsilon^{--}\mathrm{L}(\dot{\mathrm{t}}0-!.\mathrm{p}\iota \mathrm{i}\mathrm{n}\overline{\mathrm{e}}(_{-}^{arrow)}ay\bigcap_{\mathrm{J}}^{--}\S_{b}|^{\text{の差}0}..|\mathrm{h},1-\sim-\mathrm{r}^{\ovalbox{\tt\small REJECT}}--\backslash .\wedge\cdot\overline{y}.*,\mathrm{a}\in.\mathrm{r}\mathrm{c})\cup..\}(X\prec,y)\theta x.’.(’.rightarrow b\overline{C}^{\wedge}\approx--’---\wedge.\sim-\vee\sim\sim\backslash -\wedge=-\backslash :\hat{\dot{d}}.-’\backslash -\sim-$が+ 分近いならば、$|\mathrm{L}(\mathrm{t}\mathrm{o}\mathrm{p}\iota \mathrm{i}\mathrm{n}\mathrm{e}(a\not\supset)\cap S_{b}|\text{口}$略\neg - (丈猷-[8}’ 参照几-証明..
$\text{、}.l...\in\hat{..L}l_{\sim_{\mathrm{I}}}^{\wedge}’"’ x" \mathrm{x}\backslash \iota \text{する}..\cdot \mathrm{c}\mathrm{e}.1.\cdot \mathrm{e}_{J}\overline{r}\iota)\mathrm{t}\sim\cdot.\veearrow.--^{\tau\prime}!^{\mathrm{t}(}\backslash \sim^{\overline{\dot{\mathrm{r}}}^{-\wedge}}-.\text{の}$$b”...=e.’ c_{!rightarrow}(C)\neg.:...c\backslash \cdot,....=-.\text{と}.\text{す_{}\mathrm{J}}\nearrow_{\partial}..\cdot.\cdot$

軌跡を$l_{a}$$\text{マ^{}-.\text{き}-}.- m1^{\cdot}.-$:$f_{a}$と $a7$ と昼で囲まれる閉領域を砺で表す。任意の $x\in$と. とができる。

$P_{1^{-}}^{\cdot}(X\rangle.=--.\check{\mathrm{W}}\mathrm{d}^{\mathrm{b}}\backslash \mathrm{g}\mathrm{r}b(x)\overline{\vec{x}}C(X))\cap U,$

,

と表す。

$\overline{m}\hat{\mathrm{i}}(x)-\cdot.=\dagger..P_{1}(_{X})\cap s_{w}|,$$P_{2}(x)=\mathrm{W}\mathrm{d}\mathrm{g}(_{C(x}\rangle_{X}a)\cap U,$$m_{2}(x)=|P_{2}(X)\cap S_{w}|,$$P_{3}(x)=\mathrm{w}\mathrm{d}\mathrm{g}(axb(x\rangle)\mathrm{n}U$$m_{3}(X)=|P_{3}(X)\cap s_{w}|$

,

,

.

$\text{こ}.\text{ご}.\cdot$$:_{\wedge^{\vee}.\wedge}...-\cdot.-\prime \mathrm{p}\mathrm{d}\mathrm{i}\hat{\mathrm{s}}\mathrm{t}..(.\cdot\overline{X}^{\vee\cdot\cdot\sim},-- y)\text{ら}arrow^{-}=(|m1(_{X)(}-m_{1}y)|+|m2(x)-m_{2}(y)|+|ms(x)-m_{3}(y)|)/2$

pdist( ,y).4k.x,y 閲の分金距離と呼ぶ。任意のpd
題る。 さらに$x_{\vee}.’$$x$に対して $m_{1}(x)+m_{2}(x)+m_{3}(X)=m$ であることから、$\mathrm{i}\mathrm{s}$$\mathrm{p}\mathrm{d}\mathrm{i}S\mathrm{t}(_{X}, y)\leq 1$$\underline{\mathrm{t}}.(.x..’.y)..\mathrm{f}^{\mathrm{h}.\mathrm{k}^{\wedge}}\infty\cdot\ovalbox{\tt\small REJECT}- \mathrm{a}\mathrm{e}_{\vee}:\backslash ,\ovalbox{\tt\small REJECT}\xi-$-

は、 $|m_{1}(x)-m_{1(y)1}\leq 1$ かつ $|m_{2}(X)-m_{2}(y)|\leq 1$

かつ $|rn_{3}(x)-m_{3(y)1}<1$ と同値である。
.

篇蓼\alpha :‘.

$\mathrm{T}$$\mathrm{f}_{-}^{\wedge}.\#^{-\ovalbox{\tt\small REJECT}_{l}}.\backslash$\S$\mathrm{g}\overline{\mathrm{a}}\mathrm{g}4\not\in_{\grave{\mathrm{a}}}.\wedge-$

3.=1\sim グラプめ構成-\acute \tilde$-\neg\not\in_{\mathrm{c}arrow}\overline{-\vee}$$\mathrm{a}\text{て}.\dot{.}M\ovalbox{\tt\small REJECT},$$- \backslash .\dot{\prec}.:\mathrm{f}\overline{\mathrm{f}}\cdot\overline{\prime}\Leftrightarrow_{\backslash }\theta)_{X_{i}}y_{-\tau k,\sim}\in.\cdots U\int\wedge-\mathrm{Q}\text{こ}\vee\vee\cdot\wedge\infty.-\supset\cup-\ovalbox{\tt\small REJECT}.-.\ldots,\ovalbox{\tt\small REJECT}$$x$

比較的審 、で多$\text{る_{}0_{\tau}}..\llcorner$

^4

と

$y$

が十分近ければ$\mathrm{p}\mathrm{d}\mathrm{i}\mathrm{S}\mathrm{t}(x,y)\leq 1$

である様にとれれば定理 2 の証明は力球。- これを示すのは簡単では無い。 そこで、 もう少し限定した性質を以下に示す牟.-.–牢理 4q|誕與贈る道具としてはこれで十分なのである。
定\iota g.3\rightarrow(-ただし $V$ を節点集合、 $E$ を枝集合とする) で、 $v\in V$ は $(U_{a}-\Gamma‘)$ $\cup\{a\}$ 上$=- \mathrm{y}_{\text{フ}-}^{-}:.\cdot \text{フ}.\sim.G--_{r}=\mathrm{t}=_{1}.;.\cdot\cdot-\wedge’ \mathrm{w}- V,E\}_{arrow\sim}-\vee.\cdot$に羅 p:舷麹 g.\not\in 核は検真 ‘,Pf3.5\neq ...\rho 町分で表現され、 さらに以下の条件を満たすようなものが存在する。
$\cdot$(i) $G$ の外周以 99) 窓ぱ–=\check p-自 (すなわち丁度 3 本の枝から成る) である。
(ii) 任意の吻 \oplus 塑に対 Lは凸。

$\mathrm{Y}(v)$に対し$( \mathrm{i}.!.!..\cdot)^{-}.|_{:}-*-\backslash \cdot\Gamma\cdot\backslash \cdot\wedge-\cdot:.:\sim\int\piarrow \text{接}*.-.\ddot{\text{す}_{}9}- \text{る},.2..\text{節}:\wedge.- \mathrm{c}-\backslash -\dot{\wedge}‘\backslash \cdot.-\prime v- \text{点}.\cdot.\dot{v},.\overline{\epsilon}1V\sim.’..---;$:($\mathrm{i}\mathrm{v}\rangle\sim\backslash \mathrm{b}\ddot{\mathrm{Q}}(\theta_{a}^{\mathrm{x}}\dot{"})$

mk 餌$Jt\mathit{3}$\exists ま. ひの外周と--致する。

q 騨糎\mbox{\boldmath $\varphi$}聲 \mbox{\boldmath $\lambda$}r 山\alpha 暇ふ$\mathrm{p}\mathrm{d}\mathrm{i}\mathrm{S}\mathrm{t}(v, v’)\leq 1$である。
口構填的–‘.\iota .\sim \tilde 与えられる。 しかしこの証明はとても複雑な場合分けを必要とし、 ここで紹介する余裕は無い。 この証明は文献 [8] にあるので興味のある方は参照されたい。
$\tilde{J}^{*}.\vee\cdot,.-:.\ldots\backslash ^{j}\wedge j\epsilon \mathfrak{B}.ffl3\ldots g.)_{-}^{arrow \mathrm{i}}\mathrm{r}\mathrm{F}_{\sim}=\mathrm{B}\mathrm{R}^{1}-\wedge.- j.\mathrm{g}\wedge.\mathrm{r}^{=}$

46

33

証明

$v\in V$に対し以下の関数を定める。
$f(v)=\mathrm{t}((m_{3}(v)-q_{3}m)-(m_{2}(v\rangle-q_{2}m))/2\rfloor$,$g(v)=m_{1}(v)-q1m$ .

定理 3 の条件 (iii) より、 $f(v)$ と $g(v)$ は$v$

を隣接節点に動かしても高々$\pm 1$しか変化しない。 $q1,$ $q2,$ $q3$ のラ

ベルが LOW であることから、 $m_{1}(b)-q_{1}m<0,$ $m_{3}(b)-q_{3}m<0,$ $m_{1}(c)-q1m<0,$ $m_{2}(c)-q_{2}m<0$である。従って $f(b)<0$ かつ $f(c)>0$ となる。

補題 3 $G$ 上に路$\langle v_{1}, v_{2}, \ldots, v_{k}\rangle$

で、 $v_{1}\in 7_{a}\cup$ 謎かつ$v_{k}\in\ell_{a}$かつ任意の $i=1,2,$$k$$\ldots,$

に対し $f(v_{i})=0$
口である様なものが存在する。

この様な路が存在しないと仮定すると、 ある隣接 2 節点 , v’ で $f(v)\geq 1$ かつ $f(v’)\leq-1$ であ.D.
る様なものが存在する。 これは条件 (iii) に反する。

証明

$v$

$\mathrm{Q}.\mathrm{E}$$f(v_{1})=0$ であるので $m_{3}(v)-$ $q_{3}m=m_{2}(v)-$ $q_{2}m$ である。

$m_{3}(v)-q_{3}m=7n_{2}(v)-q_{2}m<0$ が得られる ($g(v_{1})=m_{1}(v1)-q_{1}.m>0$ 。

$q_{1}$$q_{2}$と$q_{3}$$v_{1}\in 7_{a}\cup$

謎であることを考慮するとのラベルが LOW であることに注意) 。 よってのラベルが LOW であるので、 $g(vk)<0$ となる。従って、 $g(v_{h})=0$となる様な $v_{h}\in\{v_{1}, v_{2}, \ldots, v_{k}\}$ が存在しなければならない。 よって $m_{1}(v_{h})=q_{1}m,$ $m_{2}(v_{h})=q_{2}m$ ,は凸であるので、 これが所望の均等分割である。以上より定理 2 が証明さ
$m_{3}(v_{h})=q_{3}m$ となる。
$\mathrm{Y}(v_{h})$れた。

定理 2 を用いれば定理 1 の証明は数学的帰納法によって容易であるのでここでは省略する。

4

関連話題
本章では関連する話題についていくつか紹介する。

4.1

$k-$

扇

Ba’ra’ny と Matou\v{s}ek は平面を分割する k-扇 (k-fan) という概念を定義した。

, 砺によって分割される平面
定義 1 平面上の任意の点 と を端点とする任意の 本の半直線(
半直線上の任意の部分は、任意に両隣りの集合のどちらかに属している
分割を鳥扇 (k-fan) と呼ぶ。
$x$

$k$

$x$

と解釈する。)$l_{1},l_{2},$$\ldots$口k 扇は– 見ハムサンドイッチ分割の特殊な場合に見えるが、た扇によって得られる分割は凸で無くても良い点は逆に自由度が高い。彼等はん扇に対していくつかの性質を得た [2] が、 そのうち重要なもの
は次の性質である。

定理 4(B\’ar\’any and Matou\v{s}ek 1999) 平面上の $5n$ 個の赤点と $5m$ 個の白点で、 いかなる 5-扇でも全ての集合が各々赤点 個と白点 個を含む様に出来ないものが存在する。 また、平面上の任意の $5n$個の赤点と $5m$ 個の白点に対し、 4-扇で、 1 つの集合が赤点 $2n$ 個と自点 $2n$ 個を含み、 残りの 3 集合が
$n$

各々赤点

$n$

個と白点

$n$

$n$

個を含む様なものが存在する。

Ba’ra’ny と Matou\v{s}ek の元の定理は離散点集合ではなく、平面上の連続的な測度に対する結果であるがその結果は明らかに離散的な対象に適用できる。

47

4.2

完全分割

周囲にチョコレートが塗られたケーキをん人で公平に分けたい。 その時各人はスポンジの量もチョコ分の 1 欲しいし、 さらにもらったケーキ片があまり汚い形をしているのは気分が悪い。
こうい た条件をモデル化したのが次の完全分割である。
レートの量も$k$$\text{っ}$定義 2 $S$ を平面上の凸集合とする。 $S$ が互いに重ならないた個の凸集合に分割され、 さらに各集合はの面積のた分の 1 の面積を持ちかつ $S$ の境界のうちの 分の 1 を含み、 各集合の含む $S$ の境界は連続しているとき、 その分割を完全た-分割 (perfect k-division) と呼ぶ。
口

$S$

$k$

金子と加納は以下の定理を与えた [11]。

定理 5(金子・加納 1999) 任意の平面上の凸集合$S$と任意の自然数$k$に対し、完全 k-分割が存在する。
口

完全鳥分割において特徴的なのは、「各集合の含む $S$ の境界は連続している」 とする点である。実際
この条件が無い場合は、 面積を表す測度を赤点の数で、境界長を表す測度を白点の数で表すことによって、平面ハムサンドイッチ分割問題の特殊な場合となるため、定理 1 の結果に包含されることになる (点数を増加させることによって、 連続的な測度をいくらでも正確に近似できることに注意)

しかし境界の連続性があることによってん $=3$ の場合で既に平面ハムサンドイッチ分割とは異なる問題となってい。

(例えば平行な 2 直線による 3 分割はハムサンドイッチ分割では許容されるが完全分割では許されな

るい)。 よってこの完全分割もハムサンドイッチ分割と似ているが独立した概念である。

4.3

ケーキ分割問題ハムサンドイッチ分割や完全分割はケーキの分割の抽象化として語られることが多いが、 それそのものの 「ケーキ分割問題 (cake cutting$\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{m}$)」 と呼ばれている問題がある。 この問題の定義を説明する前に、 次の問題を考えてみよう。

問題太郎と次郎が 1 つのケーキを分けようとしている。 2 人とも全体の価値の 2 分の 1 以上を貰えば満足する。但し、 2 人の価値観は同じとは限らない (すなわち、チョコの量を重視する子もいればサンタクロースの人形を強く欲する早いるという様に様々な価値観があるということだ)らも不満が出ない様に分けるにはどうしたら良いか ?

どちらか

。

この問題の答は後述するが、比較的有名かつ手ごろな頭の体操であるので、 もし答を御存じ無い方は暫くここで考えてみることをお勧めする。 ケーキ分割問題は上記の問題を色々な視点から –般化したものを総称してこう呼ぶ。 まず問題を正確に記述する為に用語を定義しておかなければならない。
ケーキ全体を $X$ と表す。ケーキ全体あるいは断片 $A$ は 2 つの断片 $B$ と $C$ (但し $B\cup C=A,$ $B\cap C=$ 釦に分けることができる。参加者$i=1,2,$はケーキの任意の断片 $A$ に対し、価値\mu i $(A)$ を持っている。 この時関数\mu i は下記の条件を満たさなければならない。
$k$$P_{i},$$\bullet$$\bullet$$\bullet$$\bullet$ケ$-\text{キ}$$\ldots,$

全体の価値は 1 である。すなわち $\mu_{i}(X)=1$。

-

ケーキを全く得られない場合の価値は零である。すなわち$\mu_{i}(\emptyset)=0$

どんな断片も負の価値を持つことは無い。すなわち任意のケーキ片$A$に対して\mu ’(A)$\geq 0$

ケーキは分割によって全体の価値が減ったり増えたりしない。すなわち $B\cup C=A\subseteq X,$
である時、 $\mu_{i}(B)+\mu i(C)=\mu_{i}(A)$。

.

$B\cap C=\emptyset$48
言い換えれば、 \mu ’ の数学的ふるまいは確率測度に等しい。 さらに、任意のケーキ片 A、任意の参加者$B$ と
任意の正の実数 $0<r<\mu_{i}(A)$ に対し、君は $A$ を $\mu_{i}(B)=r,$ $\mu_{i(\rangle}C=\mu_{i}(A)-\gamma$ を満たす 2 つの片$P_{i}\text{、}$C. に正確に切り分けることができるものとする。
以上の前提に基づき、 ケーキ分割のアルゴリズム (ルール) を与え、 そのルールに乗っ取って分割を遂行すれば、 各人が与えられた公平概念 (例えば 分の 1 以上の価値を持つ等; 詳細は後述する) を満$-$足するケーキ片 (複数の片の集まりでも良い) を得ることができる様にせよ、 という問題を –般にケ$k$キ分割問題と呼ぶ。
例えば前記の太郎

begin
Step 1
Step 2end.

$(P_{1})$と次郎$(P_{2})$による分割の問題の場合はアルゴリズムは次の様に与えられる。

$P_{1}$

が $X$ を $\mu_{1}(A)=\mu_{1}(B)=1/2$ となる様に分割する$P_{2}$

が

$A$

と

$B$

$0$

のうち、 価値の高いと思う方を取る。

ここで面白い点は 「各\mu ’ は個人的な価値であって他人からは分らなくても良い」 ことである。 つまり上記のアルゴリズムにおいて太郎が本当に正確に半分に分割したかどうかは次郎からは確認できなくとも良いのである。 もし太郎が正確に半分に分割していなかったら、例えば\mu 1 $(A)>1/2>\mu_{1}(B)$ の様に分割していたならば、次郎に を取られた場合に太郎は半分の価値を取ることはできなくなってしまう。
結局、 アルゴリズムの指示に従わなかった場合、 災難はその指示に従わなかった人自身にのみ降り掛かる様なアルゴリズムになっている。 ケーキ分割問題のアルゴリズムを与える際には、 この条件も満足する様に与えなければならない 1。
とす
公平概念については下記のものなどがある (参加者を 人、 参加者疏の得た片 (の合計) をる)。 なお、 名称は文献 [12] に従っている。
$A$

$k$

$X_{i}$

1. 単純公平分割 (simple fair division): 任意の $1\leq i\leq k$ に対して\mu ’(X,)\geq 1/た.
2. 強公平分割 (strongly fair division): 任意の $1\leq i\leq k$ に対して\mu ’(Xi) $>1/k\sim$ .

3. 無羨望分割 (envy-hee division): 任意の $1\leq i,j\leq$ んに対して\mu i$(\lambda_{i}’)\geq\mu_{i}(X_{i})$.

4. 超無羨望分害|J (super envy-free division): 任意の $i\neq j,$ $1\leq i,j\leq k$ に対して\mu i $(X_{j})<1/k$ .

5. 正確分割 (exact$\mathrm{d}\mathrm{i}\mathrm{v}\mathrm{i}\mathrm{S}\mathrm{i}\mathrm{o}\mathrm{n}\rangle$: 任意の $1\leq i,j\leq k$ に対して\mu i $(X_{i})=1/k$ .

によると 2800 年も遡ることができる
ケーキ分割問題の元となった冒頭の問題は、 Brams とによって人の無羨望分割アルゴリズムというぐらい古い問題であるが、 1995 年に Brams とが提案されたことをきっかけに、 多くの研究者の注目を浴びる様になった。 ケーキ分割問題についてこ$\mathrm{T}\mathrm{a}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{r}[\mathrm{s}]$$\mathrm{T}\mathrm{a}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{r}[4]$$k$

こではスペースの関係でこれ以上は述べないが、詳しくは比較的最近刊行された専門書 $[5, 12]$ や日本語による解説文 [14] があるので、 興味のある方はそちらを参照することをお勧めする。 以下ではケーキ分割問題とハムサンドイッチ分割との関係について少し触れておきたい。
ハムサンドイッチ分割との関係
は定理 1 において $q=2$ の場合 (すなわち古典的な平面ハムサンドイッチ分割) は、部分集合の考える価値\mu 1
共に赤点 個と白点 $m$ 個を同時に含むことを要求される。 ここで赤点の数を参加者$P_{1},$$n$$P_{2}$$P_{1}$

であり、 白点の数を参加者乃の考える価値\mu 2 であると考えると、参加者 2 人による単純公平分割は、部\sim \mu ’ が個人的な価値であるという前提の元では、 アルゴリズムは自然とこうなると思われる。 この件についてなんらかの証明があるかどうかは不明ではあるが。

49

分集合

が少なくとも赤点 個を含み、部分集合疏が少なくとも白点 $m$ 個を含む様にする問題であると考えることができる。 さらに 3 人での分割では赤点、 白点の他に参加者馬の価値感を表す 「青点」 導入することで説明できる。 この様に対応付けすると、 ケーキ分割問題は点の種類が人数分ある点はハム$P_{1}$$n$

サンドイッチ分割より複雑だが各人が自分の色の点だけ見ていれば良いという点はより簡単になっている。 さらにケーキ分割問題では常にケーキは 1 次元の物体として考えられているが、これを 2 次元の物体と考えて凸制約等を考慮すれば、 また面白い問題が考えられる。

平面ケーキの 3 人による凸無羨望分割が存在することは定理 1 を使えば簡単に示すことが出来る。 しかしこれについては、 2 次元性を使用しなくても、 任意の 1 次元ケーキが 3 片分割によって 3 人に無羨

望分割できることが知られており [12, pp. 65-66]. いわば自明のことである。従って、 2 次元が有効に働くとすれば 4 人以上による凸無羨望分割が存在する時であろう。現在我々は 4 人ならば凸無羨望分割が存在すると予想しているが証明には至っていない。

5

まとめ

本稿では 2 次元ハムサンドイッチ定理の–般化に関する金子・加納の予想が成立すること (定理 1)の証明の概略を紹介した。元々のハムサンドイッチ定理は–般の 次元に対しても存在するが、勿論定理 1 が 3 次元以上に拡張できる可能性はある。 実際平面 2 分割は自由度を使い切っているのにもかかわ$n$らず、 平面 3 分割は自由度を 1 つ残している ( を上にほぼ自由に設定できることに注意) ことは興味深く、 こうい た観察から –般の 次元においても同様の性質が成立する公算は高い。
もちろん
$a$

$D$

$\mathrm{b}\mathrm{o}(U)$$n$

その証明は簡単では無さそうだが。

さらに関連する最近の話題についてもいくつか述べた。 これらの他にも色々な変形があるものと思われ、 今後の研究動向に興味がもたれる。

参考文献[1] 秋山仁, Graham, R. L., 離散数学入門, 朝倉書店 (1993).
[2] B\’ar\’any, I., and Matou\v{s}ek, J., Simultaneous partitions of mesures by -fan,manuscript (1999).
$k$[3] Bespamyatnikh, S., Kirkpatrick, D., and Snoeyink, J., Generalizing ham
sandwich cuts to equitable subdivision, Proceedings of Fifteenth Annual ACM Symposium on Computational
Geometry, pp. 49-58 (1999).
$(\mathrm{S}\mathrm{o}\mathrm{C}\mathrm{G}’ 99)$[4] Brams, S. , and Taylor, A. D., An envy-free cake division protocol,
American Mathematical
Monthly, 102, pp. 9-18 (1995).
$\mathrm{J}$[5] Brams, S. , and Taylor, A. D., Fair Division, Cambridge University
Press (1996).
$\mathrm{J}$[6] Goodman, J. and O’Rourke, J., Handbook of Discrete and Computational
Geometry, CRC Press(1997).
[7] Ito, H., Uehara, H., and Yokoyama, M., 2-dimension ham sandwich
theorem for partitioning
into three convex pieces (Extended abstract), Proceedings
JapanofConference on Discrete andComputational Geometry ’98 (Collection of Extended abstracts), December, Tokai
Univ., pp.
69-73 (1998).

50[8] Ito, H., Uehara, H., and Yokoyama, M., 2-dimension ham sandwich theorem for partitioning into
three convex pieces, Proceedings of Japan Conference on Discrete and Computational Geometry’98 (JCDCG ’98), Springer (to appear).
.
. yilab. tutics.
http:$//\mathrm{w}\mathrm{w}\mathrm{w}$$\mathrm{t}\mathrm{u}\mathrm{t}.\mathrm{a}\mathrm{c}.\mathrm{j}\mathrm{p}/\mathrm{i}\mathrm{t}\mathrm{o}/\mathrm{L}\mathrm{i}\mathrm{s}\mathrm{t}.\mathrm{R}\mathrm{m}\mathrm{l}\neq \mathrm{a}\mathrm{n}\mathrm{c}\mathrm{h}\mathrm{o}\mathrm{r}\mathrm{P}\mathrm{L}\mathrm{H}\mathrm{a}\mathrm{m}$[9] Kaneko, A. and Kano, M. A balanced partition of points in the plane and tree embedding
problems, (submitted).
[10] Kaneko, A. and Kano, M., Balanced partition of two sets of points in the plane, (submitted).
[11] Kaneko, A. and Kano, M. Perfect -divisions of convex sets in the plane, Proceedings of JapaneseHungarian Symposium on Discrete Mathematics and Its Applications, Kyoto, March 17-19, 1999,
pp. 91-93.
$n$[12] Robertson, J. and Webb, W., Cake-Cutting Algorithms, A$\mathrm{K}$Peters (1998).

(Extended abstract), Proceedings of Japan Confer[13] Sakai, T., Radial partitions of point sets inence on Discrete and Computational Geometry ’98 (Collection of Extended abstracts), December,
Tokai Univ., pp. 74-78 (1998).
$\Re^{2}$[14]$\not\in\text{\’{e}}_{l}\underline{\mathrm{g}}\mathrm{H}^{\backslash }\mathrm{g},$$\mathrm{X},\backslash t\mathrm{K}\{_{\mathit{4}}j\mathrm{D}\mathrm{a}\iota,$$/\backslash \underline{\backslash }\urcorner^{-\backslash }\text{ム}\mathrm{T}\prime_{=\theta \mathrm{J}}\ovalbox{\tt\small REJECT} \mathrm{J}\text{と}\ll^{-\sigma)}\mp\ovalbox{\tt\small REJECT},$$\kappa_{\backslash }\mathrm{f}\mathrm{f}\mathrm{l}\Re\neq \mathrm{E},$$9$, pp. 12-27 (1999).