練習問題

第 6.2.3 項で触れた「容器に水を入れる問題」をモデル化する状態機械の定義を次に示す。遷移を \(2\) 個しか持たない状態を全て答えよ。

1. 小さい容器を満たす:\(\quad\) \((b, l) \to (b, 3) \quad\) (\(l < 3\))

2. 大きい容器を満たす:\(\quad\) \((b, l) \to (5, l) \quad\) (\(b < 5\))

3. 小さい容器を空にする: \(\quad\) \((b, l) \to (b, 0) \quad\) (\(l > 0\))

4. 大きい容器を空にする: \(\quad\) \((b, l) \to (0, l) \quad\) (\(b > 0\))

5. 小さい容器から大きい容器に水を移す:

   \[ (b, l) \to \begin{cases} (b + l, 0) & b + l \leq 5 \text{ のとき} \\ (5, l-(5-b)) & \text{それ以外のとき} \end{cases} \]

6. 大きい容器から小さい容器に水を移す:

   \[ (b, l) \to \begin{cases} (0, b + l) & b + l \leq 3 \text{ のとき} \\ (b - (3-l), 3) & \text{それ以外のとき} \end{cases} \]

1960 年代後半 Nerdiaナーディア という小国でクーデターが起こり、軍事政権が発足した。この軍事政権は組み込みの乗算演算を完全に違法化し、\(3\) 以外の実数による除算も禁止した。幸い、若い反体制活動家が任意の二つの非負整数を乗算する方法を生み出し、人々は軍事政権によって処刑されることを心配せず乗算を計算できるようになった。彼が人々に教えた手続きを次に示す:

このアルゴリズムは非負整数の三つ組 \((r, s, a)\) を状態とする状態機械でモデル化できる。初期状態は \((x, y, 0)\) であり、遷移は \(s > 0\) に対して次の規則で定義される:

1. 入力 \(x = 5\), \(y = 10\) に対する \(multiply\) の実行がたどるステップを説明せよ。

2. 不変条件の原理を使って、このアルゴリズムの部分正当性を証明せよ ── つまり、\(s=0\) のとき \(a = xy\) だと示せ。

3. このアルゴリズムが \(\textbf{do}\) 文の本体を最大でも \(1 + \log_{3} y\) 回しか実行しないことを証明せよ。

二次元格子上を移動できる Wall-Aウォーラー という名前のロボットがある。Wall-A は位置 \((0,0)\) を出発し、\(4\) 種類のステップのいずれかで移動する。それぞれのステップは次の量だけ位置を変化させる:

1. \((+2, -1)\)
2. \((+1, -2)\)
3. \((+1, +1)\)
4. \((-3, 0)\)

Wall-A の移動例を次に示す。矢印の上の数字はステップの種類に対応する:

Wall-A の恋人、スタイリッシュで高出力なロボット Evaエヴァ は位置 \((0, 2)\) で Wall-A を待っている。

1. Wall-A の移動をモデル化する状態機械を説明せよ。状態は何か？ どんな遷移が存在するか？

2. Wall-A は恋人に会えるだろうか？ もし会えるなら、Wall-A の出発地点から Eva が待つ位置への道筋を示せ。もし会えないなら、不変条件の原理を使ってそのような道筋が存在しないことを示せ。保存不変条件をはっきりと表明し、証明すること。

   ヒント: \(x - y\) は保存されない。ただ、この値はどのように変化するか？

空腹のアリが無限に広がる二次元格子上に置かれている。それぞれのマスにはパンくずがあるか、何もないかのいずれかである。パンくずがあるマスは一筆書きできる道になっており、この道の最初と最後を除いた任意のマスは条件「隣接するマスの中に、パンくずがあるマスがちょうど二つある」を満たす。アリが置かれているのは、この道の最初または最後のマスである。例えば次の図でアリは北を向いており、南東方向に道が続いている。アリは最初のマスに最初に置かれたマスにあるパンくずを既に食べている。

アリは自身の前方にある食べ物の匂いしか感知できない。また、アリは記憶できることが少ないので、何らかの動作をした後に憶えていられるのは、その動作の直前に記憶・感知していた情報だけに依存する情報だけである。匂いと記憶を利用して、アリは前方に \(1\) マス進むか、左右に方向転換するかを実行する。アリは移動先にあるパンくずを食べるとする。

以上のシナリオは「アリの記憶」と「その他の情報 (残っているパンくずの位置など)」の組を状態とする状態機械でモデル化できる。この状態機械の詳細を説明せよ。有限長の任意の道に沿って置かれたパンくずを全て食べ切れるようにアリの「記憶」を設計し、さらに道の終わりを感知可能にすること。状態機械の可能な状態、遷移、入力、(存在するなら) 出力を正確に記述し、全てのパンくずを食べることを簡単に説明せよ。

最後の遷移は自己ループで構わない: 「終了」を出力する状態に無限にとどまってよい。なお、動作終了を表す状態を作って「終了」が一度だけ出力されるようにもできる。

通常のトランプカード一式が次の順番で積み重なっている:

このデッキに対して許されている操作はインシャッフル (inshuffle) とアウトシャッフル (outshuffle) の二つだけとする。両方の操作においてデッキは二等分され、上半分の山が右に、下半分の山が左に置かれる。そして左右の山のカードが交互に並ぶように二つの山を組み合わせることでデッキをシャッフルする。シャッフル後のデッキで一番上にあるカードはインシャッフルでは左の山に含まれるカードであり、アウトシャッフルでは右の山に含まれるカードである。

1. この設定を状態機械としてモデル化せよ。

2. 不変条件の原理を使って、インシャッフルとアウトシャッフルだけではデッキの上半分を黒いカードのみにできないと示せ。

   ヒント: 証明に適した不変条件を見つけるのは難しい！ 不変条件を利用する証明で洞察が必要になるのはこの部分であり、不変条件を見つけるための簡単な方法は存在しない。到達可能な状態を多く調べてパターン ── それらの状態に共通する何らかの性質 ── を見つけるのが標準的な最初の一歩である。

第 6.3.1 項で示した高速冪乗プログラムをモデル化する状態機械を考える。\(z\) の値が正整数 \(n\) であるような任意の状態にある状態機械は、そこから最大で

回の遷移の後に停止すると示せ。

ヒント: 強い数学的帰納法を使う。

この問題では、不変条件を利用して 15 パズル (fifteen puzzle) と呼ばれる有名なパズルに関する基礎的な性質を証明する。15 パズルでは \(4 \times 4\) の格子に \(1\), \(2\), \(\ldots\), \(15\) の正方形タイルが置かれ、\(1\) マスだけ存在する空きマスに隣接するタイルを動かす操作だけが許される。

タイルの標準的な初期配置を次に示す:

この配置を次の配置 (最高齢の著者が子供のころは「the impossible」と呼ばれた) にしたいとする:

このパズルは \(4 \times 4\) の数字の並びを状態とする状態機械でモデル化できる。\((\ast)\) や \((\ast\ast)\) と同じように、この数字の並びは \(1\), \(\ldots\), \(15\) の数字と一つの空きマスからなる。

この状態機械の遷移は空きマスを隣接するタイルと置き換える操作に対応する。例えば位置 \((2, 2)\) にある空きマスを位置 \((1, 2)\) にあるタイルと置き換える操作を次に示す:

これから不変条件の原理を使って、初期配置 \((\ast)\) を配置 \((\ast\ast)\) にする方法は存在しないことを示す。

まず、上述した状態機械の状態を次の二つの情報で表現すると定める:

• 数字 \(1\), \(\ldots\), \(15\) を配置されている順番に並べた列 ── 左から右、上から下に読み、空きマスは無視する。

• 空きマスの座標 ── 左上のマスの座標を \((1, 1)\)、右下のマスの座標を \((4, 4)\) とする。

1. この表現で「the impossible」の配置 \((\ast\ast)\) を表せ。

整数列 \(L\) の二要素の組が反転組 (out-of-order pair) とは、その組の小さい方が大きい方より \(L\) で後に並んでいることを言う。例えば、列 \((1, 2, 4, 5, 3)\) は二つの反転組 \((4, 3)\) と \((5, 3)\) を持つ。また、増加列 \((1, 2, \ldots, n)\) に反転組は存在しない。整数列 \(L\) の反転組の個数を \(p(L)\) と表記する。

上述の表現で表した状態を \(S = (L, (i, j))\) とする。つまり \(L\) は \(1\), \(\ldots\), \(15\) を何らかの順番で並べた列で、\(i\), \(j\) は \(4\) 以下の非負整数である。このとき \(S\) の偶奇性 (parity) \(\operatorname{parity}(S)\) を、\(L\) の反転組の個数と空きマスの列番号の和が偶数かどうかで定める:

2. 初期状態と目標の状態の偶奇性が異なることを確認せよ。

3. 状態の偶奇性が遷移で保存されることを示し、「the impossible」の配置 \((\ast\ast)\) が本当に不可能であると結論付けよ。

   ところで、偶奇性が一致する任意の二つの配置について、一方の配置をもう一方の配置にする操作の列が必ず存在する。パズルが好きなら、その方法を考えてみるとよいだろう。

Massachusettsマサチューセッツ 有料道路協会は Zakimザキム 橋に関する問題を抱えていた。技術コンサルタントが「\(1000\) 台より多い車が一度に橋に乗ると橋は崩壊する」と警告したからである。また、交通コンサルタントからは Zakim 橋でスピード違反ドライバーによる事故率が上昇していると警告を受けた。

これを受けて、協会は Zakim 橋を一方通行にして、入口と出口の両方で通行料金を徴収することを決定した (笑ってはいけない。これは Massachusetts である)。ただし、Zakim 橋を通過する車両が入口と出口で支払う通行料金は同じではない: 橋に入るとき \(3\) ドル、橋から出るとき \(2\) ドルを支払う必要がある。また、一度に橋に乗る車両の台数を \(1000\) 台以下にするため、橋の入口で徴収した料金と出口で徴収した料金の差が \(T_{0}\) ドル以下であるときに限って車両が橋に入ることを許可する仕組みを協会は考案した。

コンサルタントたちは以上のシナリオを状態機械でモデル化することにした。この状態機械の状態は非負整数の三つ組 \((A, B, C)\) であり、それぞれ次の意味を持つ:

• \(A\): 橋の入口の料金徴収所にある現金

• \(B\): 橋の出口の料金徴収所にある現金

• \(C\): 橋に乗っている車両の台数

\(C > 1000\) を満たす状態は橋が崩壊する状態であり、絶対に起こしてはいけない。橋が崩壊した状態からの遷移は存在しない。

毎朝 Zakim 橋が一般車両に開放されるとき、料金徴収所にはお釣り用の現金がいくらか存在し、さらに点検用の車両が既に橋に乗っている可能性がある。そのため、橋が崩壊していない任意の状態から始まるシステムを解析できる必要がある。そこで、橋が開放された時点で入口の料金領収所にある現金を \(A_{0}\) ドル、出口の料金領収所にある存在する現金を \(B_{0}\) ドル、橋に乗っている車両の台数を \(C_{0} \leq 1000\) とする。橋が開放された後は点検用の車両も入口と出口で通行料金を支払うとする。

1. 上述した \((A, B, C)\) の形をした状態の遷移を記述することで、橋を通行する車両と料金徴収システムの数学的なモデルを完成させよ。

2. 次の誘導変数を考える:

   \[ A,\ \ B,\ \ A + B,\ \ A - B,\ \ 3C - A,\ \ 2A - 3B, \]
   \[ B + 3C,\ \ 2A - 3B - 6C,\ \ 2A - 2B - 3C \]

   それぞれが次に示す性質のどれを持つか解答し、その理由を簡単に説明せよ:

   • 定数 (\(C\))

   • 狭義増加 (\(SI\))

   • 狭義減少 (\(SD\))

   • 広義増加かつ非定数 (\(WI\))

   • 広義減少かつ非定数 (\(WD\))

   • どれにも当てはまらない (\(N\))

協会は技術コンサルタントに \(T_{0}\) の計算と、一度に橋に乗る車の台数が \(1000\) を超えないことの検証を依頼した。

技術コンサルタントは次のように考えた: 橋を開放したときに乗っている車両の台数が \(C_{0}\) なら、橋には追加で最大 \(1000 - C_{0}\) 台が入場できる。よって \(A - B\) の増加が \(3(1000 - C_{0})\) 未満であれば、橋の上に乗っている車両は \(1000\) 台以下である。よって \(T_{0}\) を次のように定めればよい:

3. \(\text{(b)}\) の結果を使って、状態 \((A, B, C)\) に関する単純な述語 \(P\) であって次の条件を満たすものを定義せよ:

   • 初期状態 \((A_{0}, B_{0}, C_{0})\) で成り立つ。

   • 橋が崩壊した任意の状態では成り立たない。

   • 交通システムの保存不変条件である。

   解答がこれらの条件を満たす理由を説明せよ。そこから、この交通システムを使えば橋は崩壊しないと結論付けよ。

4. MIT から来た賢いインターンは、協会が定めた交通システムが安全であることには同意した: 橋は崩壊しないだろう。ただ、彼女はシステムがデッドロック (deadlock) に陥る可能性を上司に報告した ── 橋は崩壊していないにもかかわらず交通が全く進まない状態となる可能性がある。

   このインターンが意味したことをシステムの遷移に関する視点から説明し、彼女の指摘が正しいことを簡単に説明せよ。

机の上に \(102\) 枚のコインがあり、\(98\) 枚は表、\(4\) 枚は裏を向いている。許される操作は次の二つだけとする:

1. 選択した \(10\) 枚のコインを裏返す。

2. 表を向いているコインの枚数を \(n\) として、裏を向いた \(n + 1\) 枚のコインを追加する。

例えば、最初に \(9\) 枚の表向きコインと \(1\) 枚の裏向きコインを裏返すと、表が \(90\) 枚、裏が \(12\) 枚となる。この後に二つ目の操作を行うと \(91\) の裏向きコインが追加され、表が \(90\) 枚、裏が \(103\) 枚となる。

1. この状況を状態機械でモデル化せよ。状態集合、初期状態、遷移を注意深く定義すること。

2. 裏向きのコインが \(1\) 枚だけの状態に到達する方法を説明せよ。

3. 誘導変数を次のように定める:

   \[ \begin{aligned} C &::= \text{机の上にあるコインの枚数} \\ T &::= \text{裏向きのコインの枚数} \\ H &::= \text{表向きのコインの枚数} \\ C_{2} &::= \operatorname{parity}(C) \\ H_{2} &::= \operatorname{parity}(H) \\ T_{2} &::= \operatorname{parity}(T) \end{aligned} \]

   ここで \(\operatorname{parity}\colon \mathbb{Z} \to \left\{ 0, 1 \right\}\) は次のように定義される:

   \[ \operatorname{parity} (n) ::= \begin{cases} 0 & n \text{ が偶数のとき} \\ 1 & n \text{ が奇数のとき} \end{cases} \]

   これらの誘導変数の中で、次の性質を持つのはどれかそれぞれ答えよ:

   • 狭義増加

   • 広義増加

   • 狭義減少

   • 広義減少

   • 定数

   解答の正しさを証明する必要はない。

4. 不変条件の原理を使って、表向きのコインが \(1\) 枚だけの状態は到達可能でないと示せ。\(\text{(c)}\) で解答した事実を使う場合は、ここで注意深く証明すること。

ある学校でビーバー風邪 (beaver fever) が流行した。ビーバー風邪は鳥インフルエンザの変種であり、感染すると練習問題を解きたくてたまらなくなる、問題集を夜中まで解き続けるといった症状が出る。治療法は存在せず、自然に治ることもない。

この学校の教室は正方形の区画に机を置いて、そこに生徒が座るように設計されている。\(6\times 6\) 個の机が置かれた教室を表す図を次に示す。アスタリスクがビーバー風邪に感染した生徒を表す:

ビーバー風邪は急速に広まっていく。次の条件のいずれかを満たす学生は、次の日に感染した状態となる:

• 感染している (ビーバー風邪に治療法は存在せず、自然に治ることもない)。

• 二人以上の感染している生徒に隣接している。

ここで「隣接する」は座っている区画が辺を共有することを意味する。点だけを共有する場合は隣接するとはみなされない。つまり任意の生徒が隣接する生徒の人数は \(2\), \(3\), \(4\) のいずれかである。

上に示した状態から感染が広まっていく様子を次に示す:

この例では、あと数日でクラス全員がビーバー風邪に感染する。

この定理を証明せよ。

ヒント: 感染の状態を上図のような \(n \times n\) の格子としてモデル化する。このとき感染が広まる規則が状態機械の遷移を定める。広義減少な誘導変数を上手く見つけると定理は証明できる。

\(1\)-\(2\)-コマ置き換え (token replacing \(1\)-\(2\)) は黒と白のコマを使って遊ぶ一人用ゲームである。コマは色以外で区別できない。各ステップでプレイヤーは「\(1\) 個の黒いコマを \(2\) 個の白いコマに置き換える」または「\(1\) 個の白いコマを \(2\) 個の黒いコマに置き換える」の操作を行える。

このゲームは非負整数の組 \((b, w)\) を状態とする状態機械でモデル化できる。\(b\) は黒いコマの個数を表し、\(w\) は白いコマの個数を表す。

1. 次の述語の中から保存不変条件であるものを全て選べ:

   \[ b + w \cdot \operatorname{rem}(b + w, 3) \neq 2 \tag{6.5}\]
   \[ b + w \cdot \operatorname{rem}(b - w, 3) = 2 \tag{6.6}\]
   \[ b - w \cdot \operatorname{rem}(b - w, 3) = 2 \tag{6.7}\]
   \[ b + w > 5 \tag{6.8}\]
   \[ b + w < 5 \tag{6.9}\]

以降では、\(1\) 個の黒いコマが机の上にある状態から始まるゲームを考える。つまり初期状態を \((1,0)\) とする。

2. \(\text{(a)}\) で示した述語の中から、全ての到達可能な状態で真となるものを全て選べ。

3. 述語 \(T(b,w)\) を次のように定める:

   \[ T(b, w) \ \ \overset{\text{def}}{\longleftrightarrow}\ \ \operatorname{rem} (w - b, 3) = 2 \]

   次の主張を証明したいとする:

   主張

   もし \(T(b, w)\) が成り立つなら、状態 \((b, w)\) は到達可能である。

   この主張は「\(T\) が保存不変条件である」ではない点に注意してほしい。証明では、次の述語 \(P(n)\) を帰納法の仮定として用いる \(n\) に関する数学的帰納法が利用できる:

   \[ \begin{aligned} P(n) \ \ \overset{\text{def}}{\longleftrightarrow}\ \ \forall (b, w).\ & ((b + w = n) \ \operatorname{\text{\footnotesize AND}} \ T(b, w))\\ & \operatorname{\text{\footnotesize IMPLIES}}\ \ (b, w) \text{ は到達可能} \end{aligned} \]

   \(n \leq 2\) の場合がベースケースとなる。

   • ベースケースが証明されたと仮定して、帰納ステップを完成させよ。

   • ベースケースを証明せよ。つまり \(n \leq 2\) に対する \(P(n)\) の成立を確認せよ。

コマ切り替え (token switching) は黒いコマと白いコマを使って遊ぶ一人用ゲームである。このゲームは \(1\) 個の黒いコマが場に置かれた状態から始まる。各ステップで行える操作は次の二つのいずれかである:

1. \(1\) 個の黒いコマを \(2\) 個の白いコマに置き換える。

2. 黒いコマと白いコマの個数が同じでないなら、コマの色を反転させる: 全ての黒いコマを白いコマに置き換え、全ての白いコマを黒いコマに置き換える。

このゲームは非負整数の組 \((b, w)\) を状態とする状態機械でモデル化できる。\(b\) は黒いコマの個数、\(w\) は白いコマの個数を表す。初期状態は \((1, 0)\) である。

1. 初期状態からちょうど二つのステップで到達できる状態を次の中から全て選べ:

   \[ (0, 0),\ \ (1, 0),\ \ (0, 1),\ \ (1, 1),\ \ (0, 2),\ \ (2, 0),\ \ (2, 1),\ \ (1, 2),\ \ (0, 3),\ \ (3, 0) \]

2. 述語 \(F(b, w)\) を次のように定める:

   \[ F(b, w) \ \ \overset{\text{def}}{\longleftrightarrow}\ \ b- w \text{ が } 3 \text{ の倍数でない} \]

   次の命題を証明せよ:

   主張

   \(F(b, w)\) が成り立つなら、初期状態から状態 \((b, w)\) に到達できる。

3. 状態 \((11^{6^{7777}}, 5^{10^{88}})\) が到達可能でない理由を説明せよ。

   ヒント: \(F\) が保存不変条件であることを利用する場合は証明すること。

\(1\)-\(3\)-コマ置き換え (token replacing \(1\)-\(3\)) は黒いコマと白いコマを使って遊ぶ一人用ゲームである。各ステップでプレイヤーは「\(1\) 個の黒いコマを \(3\) 個の白いコマに置き換える」または「\(1\) 個の白いコマを \(3\) 個の黒いコマに置き換える」の操作を行える。

このゲームは非負整数の組 \((b, w)\) を状態とする状態機械でモデル化できる。\(b\) は黒いコマの個数を表し、\(w\) は白いコマの個数を表す。

このゲームの初期状態は \((5, 4)\) または \((4, 3)\) とする。

次の条件を満たす状態 \((b, w)\) を適格 (eligible) と定める:

この問題では、二つの初期状態から到達可能な状態と適格な状態の関係を調べる。

1. 次の述語 \(P(b, w)\) が保存不変条件だと示せ:

   \[ P(b, w) \ \ \overset{\text{def}}{\longleftrightarrow}\ \ \operatorname{rem} (b-w,\ 4) = 1 \]

2. 全ての到達可能な状態は適格だと結論付けよ。

3. 適格な状態 \((3, 2)\) は到達可能でないと示せ。

   ヒント: \(b + w\) は狭義増加である。

\(\operatorname{min}(b, w) > 2\) を満たす状態 \((b, w)\) を十分大きい (big enough) と定める。これから次の主張を証明する:

まず、次の事実が分かる:

実際、\(3 \leq \operatorname{min}(b, w)\) と \(\operatorname{max}(b, w) \leq 5\) を満たす \(9\) 個の状態の中で、初期状態 \((5, 4)\) と \((4, 3)\) だけが適格であることは容易に確認できる。初期状態は定義より到達可能なので、上記の事実は成り立つ。

4. 次の述語 \(Q(n)\) を帰納法の仮定として用いる強い数学的帰納法を使って、上記の主張を証明せよ:

   \[ \small\begin{aligned} Q(n) \ \ \overset{\text{def}}{\longleftrightarrow}\ \ \forall (b, w).\ &(b + w = n \ \operatorname{\text{\footnotesize AND}} \ (b, w) \text{ は適格かつ十分大きい}) \\ & \operatorname{\text{\footnotesize IMPLIES}} \ \ (b, w) \text{ は到達可能} \end{aligned} \tag{6.11}\]

   ここまでに示した事実を証明で使って構わない。

   ヒント: \(Q(n)\) は \(Q(n-2)\) を使って示す。

バケツに青い球と赤い球がいくつか入っており、青い球は赤い球より多い。条件「青い球が赤い球より多い」が満たされる限り、次の操作のいずれかを使ってバケツの球を追加・除去できるとする:

1. \(1\) 個の赤い球を追加する。

2. \(1\) 個の青い球を除去する。

3. \(2\) 個の赤い球と、\(1\) 個の青い球を追加する。

4. \(2\) 個の青い球と、\(1\) 個の赤い球を除去する。

次の質問に答えよ:

1. 最初バケツに \(10\) 個の赤い球と \(16\) 個の青い球が入っているとき、上記の操作を実行することで実現できるバケツの中にある玉の個数の最大値を答えよ。

任意の時刻でバケツの中にある青い球の個数と赤い球の個数をそれぞれ \(b\), \(r\) とする。

2. 操作 \(\text{(i)}\)-\(\text{(iv)}\) を適用してバケツの球を追加・除去するとき、\(b - r \geq 0\) が保存不変条件だと示せ。

3. 値域が非負整数である狭義減少な誘導変数を見つけ、それを使って命題「操作 \(\text{(i)}\)-\(\text{(iv)}\) を適用してバケツの球を追加・除去するとき、いずれどの操作も適用できない状態になる」ことを示せ。

この問題では問題 6.7 で考えた反転組をもう一度考える。

整数 \(1\), \(\ldots\), \(n\) を何らかの順番で並べた列を \(A\) とする。\(A\) の二要素の組が反転組 (out-of-order pair) とは、その組の小さい方が大きい方より \(A\) で後に並んでいることを言う。例えば、列 \((1, 2, 4, 5, 3)\) は二つの反転組 \((4, 3)\) と \((5, 3)\) を持つ。\(A\) の反転組の個数を \(t(A)\) と表記する。例えば \(t((1, 2, 4, 5, 3)) = 2\) が成り立つ。

列 \(A\) の一部の要素を並び替える \(3\)-回転 (rotate-triple) と呼ばれる操作がある。この操作は、\(A\) で連続する \(3\) 要素を最小要素が先頭になるように回転させる。例えば、列 \((2, 4, 1, 5, 3)\) の連続する三要素 \(4, 1, 5\) に \(3\)-回転を適用すると、この部分が \(1, 5, 4\) になる。つまり列全体は次のように変更される:

ここからさらに連続する三要素 \(2, 4, 1\) に \(3\)-回転を適用すれば、この部分が \(1, 2, 4\) になる:

列 \(A\) を状態に持ち、\(3\)-回転の適用に対応する遷移を持つ状態機械を考える。

1. 誘導変数 \(t\) が広義減少である理由を説明せよ。

2. 「反転組の個数が偶数である」が保存不変条件だと示せ。

3. 次のように状態 \(S\), \(T\) を定める:

   \[ \begin{aligned} S &::= (2014,\ 2013,\ 2012,\ \ldots,\ 2,\ 1) \\ T &::= (1,\ 2,\ \ldots,\ 2012,\ 2013,\ 2014) \end{aligned} \]

   \(S\) が初期状態のとき \(T\) に到達できない理由を説明せよ。

\(4\) 人の学生を \(4\) 社の企業に一人ずつ割り当てる必要があるとする。学生と企業の希望順位は次の通りである:

1. 婚礼儀式を使って、学生と企業の安定マッチングを二つ作成せよ。

2. 安定結婚問題のインスタンスが与えられたとき、解答が一意 (安定マッチングが一つしか存在しない) かどうかを判定する単純な手続きを示し、それが正しい理由を簡単に説明せよ。

婚礼儀式に Harryハリー という男性と Aliceアリス という女性が参加している。次の命題の中で保存不変条件であるものを全て選べ。それはなぜか？

1. Alice は Harry のランキングにいる唯一の女性である。

2. 誰からもセレナーデを歌われていない女性がいる。

3. Alice が Harry のランキングに残っていないなら、Alice には自身のランキングで Harry より上位の求婚者がいる。

4. Harry のランキングから Alice は消去されており、Harry がセレナーデを歌っている相手より Alice の方が Harry のランキングで上位にいる。

5. Alice が Harry のランキングに残っているなら、Alice のランキングで Alice の求婚者は Harry より下位である。

男女のランキングがどんなものであったとしても、任意の男性は自身の最適な妻の最悪な夫であると示せ。

ヒント: 「不穏カップル」の定義から直ちに従う。

同人数の男女が参加する婚礼儀式において、最終日にだけセレナーデを歌われる女性が必ず少なくとも一人存在する理由を説明せよ。

\(4\) 人の少年と \(4\) 人の少女が、異性の好感度ランキングを部分的に作成した:

1. ランキングの空白部分がどんな値だったとしても、次のマッチングは安定マッチングだと示せ:

   \[ (B1,G1),\ (B2,G2),\ (B3,G3),\ (B4,G4) \]

2. \(\text{(a)}\) の安定マッチングが男性にとって最適でも、女性にとって最悪でもないと示せ。つまり、このマッチングが婚礼儀式で得られることはない。

3. 少なくとも \(2^{n/2}\) 個の安定マッチングを持つような \(n\) 人の少年と \(n\) 人の少女のランキングの集合を示せ。

   ヒント: \(n\) 人の少年を \(n/2\) 個の組に分割し、同様に \(n\) 人の少女も \(n/2\) 個の組に分割する。\(k\) 番目の組に属する少年のランキングでは、\(k\) 番目の組に属する二人の少女が \(k-1\) 番目以前の組に属する \(2(k-1)\) 人の少女の直後になるようにランキングを作成する。\(k\) 番目の少女の組についても同様とする。さらに、\(k\) 番目の組に含まれる少年が \(k\) 番目の少女の組の中で上位に位置付ける少女のランキングでは、その少年がもう一方の少年より下位になるようにする。

第 6.4.1 項で示した安定マッチングを見つけるための婚礼儀式は、男女の人数が等しくない場合でも正しく動作する。以前と同じように、一夫一婦のマッチングが安定 (stable) とは「不穏カップル」を持たないことを意味する。

1. 未婚の男性および女性がいる場合にも対応できるように不穏カップルの定義を拡張せよ。安定マッチングでは全ての男性が結婚しているか、そうでなければ全ての女性が結婚していると示せ。

2. 男女の人数が等しくない場合でも婚礼儀式が安定マッチングを構築する理由を説明せよ。

何人かの集まりがあり、そこに属するそれぞれの人物に \(1\) 人の相棒 (buddy) を割り当てたいとする。相棒は同性でも構わない。全員が相棒にしたい人物のランキングを持つと仮定する。このとき安定 (stable) な相棒割り当てとは、これまで見てきた通常の (男女が分かれる) 安定結婚問題と同様の意味を持つ。それぞれの人物が図 \(\text{6.5}\) に示すランキングを持つとき、安定な相棒割り当てが存在しないことを示せ。Mergatroidマーガトロイド のランキングは解答に影響しないので図に示されていない。

安定マッチングの最も有名な応用は医学部の卒業生を医療機関に割り当てる問題での利用である。それぞれの医療機関は受け入れたい学生のランキングを持ち、それぞれの卒業生は所属したい医療機関のランキングを持つ。ただし、同人数の男女の安定なマッチングを見つける問題とは異なり、たいていの医療機関が受け入れられる卒業生の人数は \(1\) 人より多く、医療機関ごとに異なる。さらに、医療機関が受け入れ可能な卒業生の人数の和が実際の卒業生の人数に等しいとは限らない。

男女の人数が等しい場合の問題に対する婚礼儀式アルゴリズムを変更し、この一般性が増した状況に対応させる方法を示せ。特に、この状況に合うように安定マッチングの定義を変更し、婚礼儀式をどのように修正すべきか説明せよ。

\(3\) 人の少年と \(3\) 人の少女の安定マッチングであって、誰もランキングが \(1\) 位の人物と結婚しない例を示せ。解答が安定マッチングであることを簡単に説明せよ。その安定マッチングは婚礼儀式または男女を逆転させた婚礼儀式から得られるか？

同数の男女間の婚礼儀式で得られる安定マッチングにおいて、自身のランキングで上位半分に含まれる異性と結婚している人物を幸運 (lucky) と呼ぶことにする。幸運な人物が少なくとも一人いることを示せ。

ヒント: 男性が女性に拒絶される平均回数に注目する。

男女間の安定マッチングが二つあると仮定する。このとき任意の男性には一人目の妻と二人目の妻が存在し、任意の女性には一人目の夫と二人目の夫が存在する。

ある (一つ目または二つ目の) マッチングにおける結婚相手がもう一方のマッチングにおける結婚相手より自身のランキングで上位である人物を、そのマッチングにおける勝ち組 (winner) と呼び、あるマッチングにおける結婚相手がもう一方のマッチングにおける結婚相手より自身のランキングで下位である人物を、そのマッチングにおける負け組 (loser) と呼ぶことにする。二つのマッチングで結婚相手が変わらない人物は勝ち組でも負け組でないと定める。

これから次の命題を証明する:

1. \(\text{(WL)}\) の \(\rightarrow\) 方向は命題「勝ち組同士が結婚することはない」と同値である。この命題が不穏カップルの定義から直ちに従う理由を説明せよ。

\((\text{WL})\) の \(\leftarrow\) 方向は命題「負け組同士が結婚することはない」と同値である。この命題はマッチングにおける勝ち組の人数と負け組の人数に注目すると示せる。

2. 両方のマッチングにまたがって数えるとき、負け組の人数と勝ち組の人数が等しい理由を説明せよ。

3. 「負け組同士が結婚するとき、勝ち組同士も結婚していなければならない」と示すことで \((\text{WL})\) の証明を完成させよ。

4. 安定マッチングにおいて、任意の人物の結婚相手が最適なのは、その結婚相手の最悪な結婚相手がその人物自身のとき、かつそのときに限ると結論付けよ。

男女間の安定マッチングが二つあると仮定する。このとき任意の男性には一人目の妻と二人目の妻 (同一人物である可能性もある) が存在し、同様に任意の女性には一人目の夫と二人目の夫が存在する。任意の男性を二人の妻の中でランキングが上位の女性と結婚させることで、三つ目のマッチングを作成したとする。

1. この三つ目のマッチングが完全なマッチングである、つまり二人の男性と結婚する女性が存在しないことを示せ。

2. 三つ目のマッチングが安定だと示せ。

   ヒント: 問題 6.26 で示した次の事実を使って構わない:

   任意のマッチングにおいて、任意の人物が勝ち組となるのは、その人物の結婚相手が負け組のとき、かつそのときに限る。

   \((SL)\)

状態機械の遷移が可換 (commuting) とは、任意の状態 \(p\), \(q\), \(r\) で次の関係が成り立つことを言う:

状態機械の遷移が合流的 (confluent) とは、任意の状態 \(p\), \(q\), \(r\) で次の関係が成り立つことを言う:

ここで \(p \to^{\ast} q\) は「状態 \(p\) から状態 \(q\) に \(0\) 回以上の遷移で到達できる」を意味する。

1. 状態機械の遷移が可換なら合流的だと示せ。

   ヒント: \(p\) から \(q\) までの遷移の個数、そして \(p\) から \(r\) までの遷移の個数の和に関する数学的帰納法を使う。

2. 遷移を持たない状態を最終状態 (final state) と呼ぶ。合流的な遷移を持つ状態機械は、初期状態から到達可能な最終状態を最大でも \(1\) 個しか持たないと示せ。

第 6.4.1 項で説明した婚礼儀式では、毎日全ての男性が自身を拒絶した女性の名前を自身のランキングから消去する。しかし、複数の男性からセレナーデを歌われた女性が一人の求婚者を拒絶するように定めると、より簡単で柔軟な手続きが得られる。

具体的には次の通りである。柔軟婚礼儀式 (flexible mating ritual) の状態機械は通常の婚礼儀式と同じ状態を持つ: 各男性に対する、その男性を拒絶していない女性のランキングが状態となる。その上で遷移は「同じ女性にセレナーデを歌った (同じ女性がランキングの最上位にある) 二人の男性を選び、その女性のランキングで下位にある方の男性が女性から拒絶される」とする。唯一の違いは拒絶される男性が常に一人である点だけで、他は一切変わらない。

婚礼儀式の様々な性質を示すために利用した保存不変条件が柔軟婚礼儀式でも成り立つことは確認するだけの価値がある。保存不変条件が成り立つと示せれば、柔軟婚礼儀式が安定マッチングを構築して停止することも示せる。

ただ、一つ問題がある: これまでに見てきたように、特定の男女のランキングに対して安定マッチングは複数存在する。柔軟婚礼儀式では状態ごとに可能な遷移が複数あるので、最終的に構築される安定マッチングが異なる可能性がある。しかし、それは実際には起こらない: 柔軟婚礼儀式は必ず通常の婚礼儀式と同じ安定マッチングを計算して停止することが示せる。

これを証明するために、まず性質を一つ定義する: 状態機械の遷移が可換 (commuting) とは、任意の状態 \(p\), \(q\), \(r\) で次の関係が成り立つことを言う:

1. 柔軟婚礼儀式を表す状態機械の遷移が可換だと示せ。

2. \(\text{(a)}\) と問題 6.28 の結果を使って、柔軟婚礼儀式が必ず通常の婚礼儀式と同じ安定マッチングを構築して停止することを示せ。

評判の悪い \(4\) つの家族が \(4\) 人の不運な子供を養子にしようとしている。一つの家族は一人の子供を養子にでき、一人の子供は一つの家族の養子となれる。家族と子供の好感度ランキングを次に示す。好感度が高い順に並んでいる:

1. 子供と家族の異なる安定マッチングを二つ示せ。

2. \(\text{(a)}\) の解答を調べることで、子供と家族の安定マッチングが二つしか存在しないことを示せ。

   ヒント: 一般に、特定のランキングに対する安定マッチングの個数は \(2\) より大きくなる可能性がある。

第 6.4.1 項で説明した婚礼儀式は、男性と女性が同数のときに加えて、男性が女性より多いときにも正しく動作する。このことは以降で仮定してよい: そういった状況で婚礼儀式は不穏カップルが存在しないマッチングを構築する。ただし、「不穏カップル」の定義は「結婚相手のいない男性と結婚相手のいる女性の組であって、その女性のランキングで結婚相手よりその男性が上位にあるもの」を含むように拡張される。

Aliceアリス を特定の女性、Bobボブ を特定の男性とする。男性が少なくとも女性と同じ人数だけいるとき、婚礼儀式の保存不変条件となる性質を次の中から全て選べ:

1. Alice には自身のランキングで Bob より上位の求婚者 (自分にセレナーデを歌う男性) がいる。

2. Bob のランキングに唯一残った女性が Alice である。

3. Alice に求婚者がいない。

4. Bob のランキングでは、現在 Bob がセレナーデを歌う女性より Alice の方が上位にある。

5. Bob が Alice にセレナーデを歌う。

6. Bob が Alice にセレナーデを歌わない。

7. Bob はどの女性にもセレナーデを歌えない。

\(n\) を非負整数とする。\(n\) 人の男性と \(n\) 人の女性の安定マッチングを構築したいとする。

1. 安定マッチングが \(1\) 個しか存在しないような男女のランキングを構築する方法を示せ。解答が正しい理由を簡単に説明せよ。

2. Aliceアリス を特定の女性、Bobボブ を特定の男性とする。次に示す性質が婚礼儀式において保存不変条件かどうかを答えよ:

   1. Alice が Bob のランキングから消去されている。

   2. Bob のランキングに女性の名前が残っていない。

   3. Bob は Alice に対してセレナーデを歌う唯一の男性である。

   4. Bob のランキングに残っている女性は \(5\) 人より少ない。

   5. Bob のランキングにおいて、名前が消去されていない最上位の女性より Alice の方が上位にある。

   6. Alice に対する現在最良の求婚者より Bob の方が Alice のランキングで上位にある。

   7. Bob は自身の最適な結婚相手にセレナーデを歌っている。

   8. Bob は自身の最悪な結婚相手にセレナーデを歌っている。

   9. Alice は最適な結婚相手からセレナーデを歌われている。

   10. Alice は最悪な結婚相手からセレナーデを歌われている。