２つの最適化に関する数学問題について、紹介したい。頭の体操です。
１．お見合い問題：秘書問題とも呼ばれる。
秘書問題（secretary problem）は、賭けの最適停止問題の一種で、応用確率論、統計学、決定理論の分野で特に研究されている。結婚問題 (marriage problem)、最良選択問題 (best choice problem) などともいう。
これは、N人のひとと順に1回づつ会って、最も良いひとを決める問題である。応募者から一人の秘書を選ぶ問題と同じであり秘書問題ともよばれる。
ただし、N人のひとの順番はランダムであるので、N人の中の最良の人は何番目にいるかわからない。お見合いの場合、何人かを見送って、S回目以降、これまであったひとよりも良いひとが現れれば決定する作戦である。
問題は、最適なS（１＜ｓ＜N)は何か？。そして、その最適戦略で、N人中の最良の人が見つかる確率は何％ですかということです。
解法の詳細は、わたしのWikiにあります。==>お見合い問題：marrige problem
[お見合い問題の答]
N人のお見合いの場合は、最適なSは　N*(1/e)　(eはオイラー数であり、1/e=0.368)。すなわちをNに37%を掛けた回数（丸めて整数化）から、最適なKである。S-1人は見送って、それ以降の回では、いままでよりも良いひとが出現すれば決定する。
そしてこのときの最良のひとが、見つかる確率は、Nが大となれば1/e=0.368　約３７％に収束する。
この知見は、最近の少子化問題とも、関係があるかも知れませんね。
冗談ですが、もし20歳から男性を探し始め、36歳までの16年間の間に結婚しようとする場合、たくさんの男性を27歳までに観察し、それまでに出現した最良の人を超える男性が現れれば結婚するというのが、最適戦略ですが、・・・。この場合困ったことに最良の男性が見つかる確率は３７％ですから、やはり欲張らずにちょっとレベルダウンも認めて探さないと、結婚し子供をつくる確率は、低くなりますね。また相手に拒否される確率が高ければ、もっと早めに探し始めなければいけないということが数学的に示されています。
この問題は、最良のひとが見つかる確率P(S)をSの関数で定式化して、これを最大化する問題を解けばよい。作戦計画　OR問題ですね。
この問題の答えに、驚くべきことに、オイラー数またはネイピア数とよばれる　e = 2.71828・・・　が出てくる。不思議ですね。
実は、この1/eは、最適停止問題における1/e法則と呼ばれており、１９８４年に発見されて驚きの衝撃が走りました。一般にｎを大きくしても成功確率は1/eにだんだん近くなります。下限なのです。

１０人中最良の人を選ぶ方法は、3回見送り4回目から以前より良い人を選ぶ方法が最適であります。最良の人が選ばれる確率は、概ね0.4＝４０％ですね。
ただし、最良といってもN人のなかでの最良ですから、たくさんのひととあって決めたほうが良い人が見つかることになる。
さて、次に安定結婚問題の紹介です。
安定結婚問題
安定結婚問題とは、N人の男性とN人の女性が集まって、プロポーズを繰り返し、マッチングすることで、最適な組み合わせを見つける方法の問題です。
そして　安定とは、マッチングの結果　互いに現在組んでいる相手よりも好きであるペア （以下ブロッキングペアとする）が存在しないマッチングを安定なマッチングという。
安定といっても、安定的な結婚生活を探す問題ではありませんが、周りに現在の相手もっと好きな相手と結婚したペアがあれば、マッチングに問題があるのは確かです。
GaleとShapleyにより提案された解法
このアルゴリズムは、各ラウンド（繰り返し）において、各男性が順に最も好ましい女性（まだプロポーズを受け入れていない）にプロポーズする。各女性は(残された中で)好ましい男性には、maybeと答え、そして、暫定的に、結婚する。残りの男性にはNoと答える。好ましい男性が暫定結婚している場合はそれを解消して結婚できる。次のラウンジでは、同様である。残された各男性が引き続き、まだプロポーズしていない女性にプロポーズする。次に女性が引き続きmaybeならば暫定結婚、そうでなければかNOを表明する。もし好みの男性がいれば暫定結婚を解消して結婚できる。これを、残されたペアがいなくなるまで続けて、婚約しているペアの集合をマッチング結果として出力する。
この方法では、1人の男性が同じ女性に2度以上プロポーズしない、
女性は婚約すると独身に戻らない、
女性はプロポーズされる際その相手が悪くなることはない、
ということからこのアルゴリズムが、必ず結婚できること、有限回の操作で安定マッチングを必ず導いて終了することがいえる。