kigyostartupのブログ

読んだことを片っ端から忘れてしまうので、忘れないように、要約を記録することにしました。

離散数学「ものを分ける理論」 問題解決のアルゴリズムをつくる

20世紀に入ってコンピュータが発達すると、アルゴリズムによる問題解決の方法が考案され、そのひとつとして、ものを分ける問題解決の手順である、離散数学を取り上げて、カウント博士とワトソン助手が対話を重ねる形式で、様々なものの分け方を解説し、それぞれの手法がいつ誰によって考案されたものかを紹介する

離散数学「ものを分ける理論」 問題解決のアルゴリズムをつくる (ブルーバックス) [ 徳田 雄洋 ]楽天で購入

第1章では、ようかんを誰にとっても納得のいくように分ける方法として、同点1位法を解説し、ようかんの定理としますが、余りが生じたばあいに、それを廃棄することに全員が納得しなければなりません。

第2章では、前章の同点1位法で出てしまった余りを廃棄せずに、余りも納得のいくように分ける方法として、最初に切った人の絶対的優位を利用した後、分けるための判断基準が複数あるときの累積評価グラフを解説します。

第3章では、6種類のくだものを姉妹で分ける場合、姉と妹とでは好きなくだものが違うために、単純に半分こづつにもできないため、くだもの分割法と、その改良型である、くだもの分割法(勝者調整法)を用います。

第4章では、前章のくだもの分割法を未知数x,yを使った方程式や不等式で条件を整理しながら、兄弟でチョコとイチゴを分けるときのお互いの満足が最大になるように分けます。

第5章では、「三角形の中に三角形」問題にあるような、小三角形を積み上げた大三角形を用いて、隣接する小三角形を順次移動するときに、移動の規則によって、目的の小三角形が1個以上の奇数になる、三角形の建物定理を説明します。

第6章では、前章の三角形の建物定理を応用して、友人関係にある3人で、特徴の異なる三つの部屋を借りるときの、それぞれの部屋の家賃の組み合わせにもとづいて、誰がどの部屋を借りるのを公平に導いて家賃問題を解き、類似の8角形建物定理を紹介します。

第7章では、赤道上の180度正反対の2地点で、同一時刻に気温と気圧の組が等しい地点が2地点あることについて、前章の8角形の建物定理を用いて、ゴールの地点を求めることができることを示します。

第8章では、長方形を1/2にするときに、直線が長方形の中心を通るようにすれば、1/2にできると位置が無限にあることを応用した、ハム・サンドイッチ定理を解説し、続いて長方形のウェディングケーキを1/2にする方法として、2本ナイフ移動法を用います。

第9章では、友人同士の3人が、レストランでお任せ料理を頼んだら、長方形の大皿に嫌いなものがたくさん入っていていたときの、公平な分け方として、全体提案法を思い付きますが、この方法ではうまく分けられません。

第10章では、前章の料理問題に対して、分割するごとに人数を増やし、分割して手元にきた分に対して、その時に分け会う人数を分母に、1/2、1/3、1/4と繰り返す、人数増加法によって、公平に分けられることを示します。

第11章では、再び、ようかんの分け方で、今度は4人以上で公平に分ける方法として、1人が自分の基準で等分し、他の人がそれに異論を唱えたときに、異論を唱えた方に先ず大きいと思っている方を渡して優越感を満たしたうえで、残りを細かい破片に分けて、さらにそれらを分け会うことを繰り返すときに、常にに異論を唱えた人を優越にする、絶対的優位法を解説します。

第12章では、前章の絶対的優位法のように、何度も分割しない方法として、線分分割定理や三角形建物定理の一般定理から成る三角形分割定理、さらにそれに立体を用いた四面体分割定理を解説します。