おいしいサンドイッチの作り方（前編）
みなさんお久しぶりです。
今日は、「サンドイッチ問題」「ピザサンドイッチの問題」「うどんピザサンド問題」などと呼ばれる数学の問題について得られた知見をまとめていこうと思います。
「サンドイッチ問題」は、2019年12月に「数学デー」*1というイベントで生まれた問題です。そのイベントに参加した友人から話を聞いて興味を持った私が、友人の助けを借りてあれこれ考えてみたところ、思いのほか強力な結果が得られ「サンドイッチ問題」をほとんど解決することができました。その結果を限られた人たちの間に留めておくのはもったいないと思い、ネットの海に放流することを決意した次第です*2。
数学デー史上最も実りのない話題だと思われていた（俺が思ってただけ）ピザの話、めちゃくちゃ進捗でた#数学デー#数学デーinN高 pic.twitter.com/0X5IBflW4Q
— 鯵坂もっちょ🐟 (@motcho_tw) January 10, 2020
前提知識
サンドイッチ問題を説明するために、まずは用語や概念の定義を行います。
ピザとサンドイッチ
これをピザ（pizza）といいます。ピザはピザでも抽象的なピザで、具がのっている面（A面）と具がのっていない面（B面）があることが重要です。その他の特徴（マルゲリータかどうか、etc...）は捨象することにします。
ピザを複数枚重ねると、ピザの塔ができます。
これをサンドイッチ（sandwich）*3と呼ぶことにします。
同じ枚数のピザからなるサンドイッチであっても、面どうしがどのように重なっているかによって複数種類のサンドイッチが存在することに注意しましょう。例えば、以下のサンドイッチはすべて異なります*4。
ピザが何枚も重なった絵をいちいち書くわけにはいかないので、サンドイッチを表す便利な表記法を導入します。A面を表にしているピザを「$>$」、B面を表にしているピザを「$<$」に対応させ、上から「ABBA」のように重なっているサンドイッチを$><<>$と表記することにします*5。不等号の開いている側に具がのっているイメージです。例えば、「$<>$」は具が載っている面どうしが向かい合わせにくっついているような（まともな）サンドイッチです。
以上の話を厳密に書くと下のようになります。
（サンドイッチ）
集合 $P=\{<, >\}$ の元をピザといい、$n$ 枚のピザからなる順序組 $(p_1,\cdots, p_n)\;(p_i\in P)$ をサンドイッチという。
このとき、次の事実が成り立ちます。
（サンドイッチの個数）
$n$ 枚のピザからなるサンドイッチは $2^n$ 通り存在する。
これは、サンドイッチを構成する $n$ 枚のピザそれぞれに対して $<, >$ の $2$ 通りの選択肢が存在することから分かります。
grabbableなサンドイッチ
サンドイッチの中でも、1枚目のピザが $<$ で最後のピザが $>$ であるようなものを grabbableなサンドイッチ*6と呼ぶことにします。
例えば、$<<>>>$ はgrabbableですが、$><<<>$ はそうではありません。サンドイッチの両端を掴んだときに具が剥き出しになっておらず、手を汚さないサンドイッチがgrababbleです。明らかに、以下の命題が成り立ちます。
grababbleなサンドイッチをひっくり返したものもgrabbableである。
せっかくなので、「ひっくり返す」に相当する記法を用意しましょう。サンドイッチ $s=(p_1,\cdots, p_n)$ に対して、$s$ をひっくり返したサンドイッチを $s^{\rm T}:=(p_n^{\rm T}, \cdots, p_1^{\rm T})$ で表すことにします（ただし$(>)^{\rm T}=<, (>)^{\rm T}=<$）。例えば $(<<>)^{\rm T}=<>>$ です。
ピザ $n$ 枚からなるgrababbleなサンドイッチは、最初と最後の1枚ずつが確定していますから、次の事実が成り立ちます。
（grabbableなサンドイッチの個数）
$n$ 枚のピザからなるgrababbleなサンドイッチは $2^{n-2}$ 通り存在する。
サンドイッチ問題
これでサンドイッチ問題を説明する準備が整いました。
$n\;(\geq 2)$ 枚のピザを使い、以下の操作を行ってgrabbableなサンドイッチをつくることを考えます。
操作
- はじめ、$n$ 枚のピザが具が載っている面を上にして（$>$ の状態で）横一列に並んでいる。
- 隣り合う $2$ つのサンドイッチを任意に選び、左側のサンドイッチをひっくり返して右側のサンドイッチに重ねる。
- 2. を$n-1$ 回繰り返し、$n$ 枚のピザからなるgrabbableなサンドイッチをつくる*7。
例えば、以下のように「操作」を行うと $3$ 枚のピザからなるサンドイッチを作ることができます。
最終的に $<>>$ というサンドイッチができていることが分かりますね。
さて、このような「操作」を考えたとき、以下のような疑問が湧いてきます。これがサンドイッチ問題です。
サンドイッチ問題
- この「操作」によって、どんなgrabbableサンドイッチも作ることができるのだろうか？
- 同じgrabbableサンドイッチを生成するという同値関係によって「操作」を分類したとき、その完全代表系を構成できるか？
- あるgrabbableサンドイッチを生成するような「操作」は何種類存在するか？
問題1.のモチベーションは理解しやすいでしょう。grabbableサンドイッチの完成形が与えられたとき、それを生成するような「操作」は必ず存在するでしょうか？もしかしたら、どのように「操作」を行っても生成することができないようなgrabbableサンドイッチが存在するかもしれません。
問題2., 3. が生まれた理由は次のようなものです。実は、異なる「操作」を行ったにもかかわらず、最終的に生成されるサンドイッチが同じである場合が存在します。すなわち、あるgrabbableサンドイッチを生成する「操作」が複数存在することがあるのです。どういったサンドイッチに複数通りの「操作」が存在して、どういったサンドイッチには1通りしか存在しないのでしょうか？その構造が知りたくなります。
こういう時の常套手段として、「操作」を同じサンドイッチを生成するものごとにグループ化することがよくあります。
上のように「操作」をグループ分けして分類したとき、次のことが達成できれば、この「操作」のことがだいたい分かったと言えそうです。
- グループごとに代表選手を選ぶことができ、その代表の共通点が分かっている。（＝各サンドイッチを生成するような重複のない「レシピ集」を作ることができる）
- 各グループの構成人数を求める方法が分かっている。（＝サンドイッチが与えられたときに、そのサンドイッチを生成する「操作」の個数を求めることができる）
この$2$つが達成可能かを問うているのが、問題2.と問題3.であるというわけです。
問題1（任意のgrabbableサンドイッチが生成可能か？）
結論から言うと、問題1の答えはYESです。以下の事実が成り立ちます。
（任意のgrabbableサンドイッチは生成可能）
$n$ 枚からなる任意のgrabbableサンドイッチ $s$ に対して、$s$ を生成するような「操作」が存在する。
証明のポイントは、「操作を逆向きに見る」ことです*8。完成形から、1つ手前のステップ、2つ手前のステップ…と遡っていくことで、最終的に初期状態にすることができれば、証明が完了します。
ここで、次の事実に注目します。
- 「操作」の途中に現れるサンドイッチはすべて、grabbableであるか、$>$ である。
これを念頭におくと、任意のgrabbableサンドイッチ $s$ に対して、1ステップ前の状態を構成することができることが分かります。実際、
- $s=<<\cdots >$ という形をしているならば、1ステップ前の状態として $>\;+\;<\cdots >$ がとれる（$<\cdots >$ はgrabbable）。
- $s=<\cdots >>$ という形をしているならば、1ステップ前の状態として $(<\cdots >)^{\rm T}\;+\; >$ がとれる（$(<\cdots >)^{\rm T}$ はgrabbable）。
- それ以外の場合は、必ず $s=<\cdots ><\cdots >$の形をしている*9ので、1ステップ前の状態として $(<\cdots >)^{\rm T}\;+\; <\cdots >$ がとれる。
が成り立つので、任意のgrabbableサンドイッチ $s$ に対して、1ステップ前の状態が構成できました。これを繰り返し用いれば、最終的に初期状態まで遡ることができます。
したがって、この「操作」によって任意のgrabbableサンドイッチが生成可能であることが分かりました。
次回予告
長くなってしまったので記事を分けることにします。問題2と問題3の答え（非常にボリュームが多いです）は次回の記事で説明したいと思います。お楽しみに。
*1:数学好きの人々が都内で集まってゆるーく数学の話をするイベントです。Twitter (@sugaku_day)を見ると感じがつかめると思います。ちなみに筆者は行ったことがありません。
*2:もうすぐ年末ですし。
*3:ピザタワーと呼ぶ流儀もあります。
*4:①と③はひっくり返すと同じになりますが、異なるサンドイッチであると定義することにします。
*5:本質的には括弧列なので、$)(()$と書いてもよかったのですが、すでにこの表記が一部界隈で定着しているようなのでそのままにしました。
*6:和訳するなら「可把（かは）」あるいは「可握（かあく）」でしょうか。
*7:この操作をどのように行っても、最終的にできるサンドイッチはgrabbableになることが証明できます。
*9:1.,2.に該当しないならば、$s$がどのような形をしていても、必ず $>$ と $<$ の境目が存在するからです。
