Recently in さんすう Category

秘書問題の続き。というか、関連したお話。

前のエントリを書いていてふと思い出したのだが、僕が尊敬する数学者の秋山仁氏の著作の中にも同じような話があった。僕のバイブルとも言える「皆殺しの數學」を紐解いてみる。

件の問題は「お見合いにおける決断の法則」の章で取り上げられている。「20人とお見合いをして結婚相手を見つける」とあるが、基本的なルールは秘書問題と同じである。ダイナミックプログラミングという技法を使って解くことができるそうだが、「数式がやたら長くなる」という理由から結論だけが記されている。

1. 最初の5人までは、絶対に結婚しない。
2. 6人目〜10人目の相手がそれまでの1位なら結婚する。
3. 11人目〜13人目の相手がそれまでの1位か2位なら結婚する。
4. 14人目〜15人目が3位以内ならその人と結婚する。
5. 16人目が4位以内ならその人と結婚する。
6. 17人目が5位以内ならその人と結婚する。
7. 18人目が7位以内ならその人と結婚する。
8. 19人目が10位以内ならその人と結婚する。
9. 最後まで結婚しなかったら、20人目の相手とシブシブでも結婚する。

秋山氏によれば、このガイドに従って決断を下せば、平均で20人中3位までの相手と結婚できるそうだ（「平均で」の部分には傍点が付いている）。しかしながらこれは、秘書問題の最適ポリシーとは似て非なるものだ。秘書問題に則るなら、最初の7人か8人（20×0.37＝7.4）をスキップして、それ以降の相手がそれまでの1位なら結婚するというガイドになる。文中には「確率の期待値というものを使って考える」とあるが、それ以上の詳しいことは書かれていない。

そこで、「ダイナミックプログラミング」をキーワードに検索してみたところ……いくつかの解説ページに辿り着いたのだが、内容が高等すぎてとても一朝一夕に理解できるものではなさそうだ。さりとて興味はあるので、僕なりに咀嚼できたらここで解説したいと思う。

ロイター配信の以下の記事が気になった。

記事中には「複雑な数学的分析から導き出された」とあるけど……正直、何をいまさらって感じだなぁ。というのも、数学パズル好きにとっては昔からよく知られた話だからだ。

応用確率論、統計学、決定理論の分野で特に研究されている問題に「秘書問題」というのがある。これは、後戻りできない順次決定という状況においてベストな選択をするにはどうすればいいかという最適停止問題の一種である。ここで誤解してはならないのは、ナンバーワンを選ぶのではなく、最善を選択する確率がもっとも高くなる方法を問うものだということだ。

秘書問題の場合、「n人の応募者をひとりづつ面接して秘書を1人雇いたい」というのが前提。目の前の応募者の不採用を決めないと次の応募者の面接ができないし、採用を決めればその時点で以降は誰も面接できない。もちろん、不採用者の中から「やっぱりあのコがいい」というのもルール違反だ。優柔不断な性格の持ち主には、なんともつらいシステムである。

仮に応募者が10人だとしよう。一番最初に面接した人を速攻で気に入って採用したなら、それが最善である確率は10ぶんの1である。容姿とかフィーリングなどのバイアス要素は抜きにして、ね。つまり、残る9人の応募者の中にも最善である可能性が均等に分布していると考えるわけだ。逆に、優柔不断な性格が災いして最後の1人になるまで決められなかった場合、必然的に10人目が採用となるわけだが、この場合もそれが最善である確率は10ぶんの1だ。が、たとえば最初の1人を不採用にした直後などは話が違ってくる。2人目を面接する際に判断材料が生まれるからだ。2人目が1人目よりも良いと思えれば採用と不採用の二者選択になるが、思えなければ必ず2人目を不採用にするはず。これを逆手にとり（?）、最初の何人かを無条件でスキップする方法が考えられる。以降の面接では、目の前の応募者とスキップした人たちとを比較すればいいから、判断がいくぶん楽になるだろう。しかしながら、スキップした人たちの中に最善が含まれていた可能性も十分にある。重ね重ね、つらいシステムであると言えよう。

結論から先に言おう。n人の秘書問題ではn×0.37人、つまり全体の37%までを無条件でスキップするのがベストである。以降の面接では、目の前の応募者がスキップした人たちよりも良いと思えた時点で採用を決めればいい。これだと約37%の確率で最善の応募者を選ぶことができる。たったの37%かって？　でもこの規則に従わなければ、最善を選ぶ確率はもっと低くなるのだ。もっとも、ナンバーツーやナンバースリーを選ぶ確率も含まれていることを考えれば、この「37%ルール」に従うことで「上位を選べる確率」はかなり高くなると言える。

ここでようやく、冒頭のロイターの記事に戻る。クレスウェル博士はおそらく、独身者が婚活期間に出会える相手の人数を30人ぐらいと仮定しているのだろう。30人の37%は11.1人。つまり、博士の「恋愛術」は秘書問題の焼き直しに過ぎない。ちなみに、秘書問題は「結婚問題」と呼ばれることもある（スルターンの持参金問題、最良選択問題とも）。

さて、37%という数字がどこから出てきたかといえば、これはネイピア数の逆数である「1／e＝0.367879441171442……」に因んでいる。ネイピア数とは自然対数の底として用いられる定数であり、秘書問題の最適ポリシーを積分によって……って、これ以上説明するとかなり難解な話になってしまうので、興味のある方はWikipediaの「秘書問題」の項目でも参照して頂戴。

Wikipedia - 秘書問題

セミの話の続き。というか、素数ゼミの話ね。

Wikipediaの「周期ゼミ」（「素数ゼミ」から転送）の導入部分にはこう書かれている。

さらに、アメリカの進化生物学者スティーヴン・ジェイ・グールドの著作「ダーウィン以来—進化論への招待」にも、周期ゼミに関する以下のような興味深い記述がある。

まったくもって不思議な現象だが、おそらく疑問点をまとめると以下のようになるだろう。

1. なぜ正確に周期発生するのか？
2. なぜ素数なのか？
3. 11や19も素数だが、なぜ13と17だけなのか？

あらかじめ断っておくが、これらの謎は完全に解明されているわけではない。前述したロイドとダイバスは、「捕食者飽食戦略」という仮説によって説明している。また、前回のエントリで書いた吉村仁氏は、氷河期と成長速度に関連づけた自説を説いている。

まずは捕食者飽食戦略から説明しよう。ホショクシャホーショクセンリャクとはなんともコムツカシイ言い回しではあるが、要は捕食者（この場合はセミを食べる他の生物。天敵）が食べきれないほど大量発生することで種を守る防衛策のことだ。グールドいわく、自然史とは捕食を回避するためのありとあらゆる「適応」の物語である、と。捕食者飽食戦略もそんな適応のひとつだが、これが成功するためには必要条件が2つある。発生のタイミングが正確であること、そして、捕食者がそのサイクルに順応できないよう発生頻度がごく稀であることだ。

セミの捕食者には鳥やクモ、カマキリ、スズメバチなどがいるが、それらの生活環（生物個体が発生を開始してから次世代の個体が発生を開始するまでのサイクル）はせいぜい2～5年だそうだ。もしも周期ゼミの発生周期がこの範囲であれば、セミが羽化する際（というか、土の中から出てきた瞬間）に捕食者の餌食となる。つまり、いくら大量発生しようとも絶滅へのカウントダウンは止まらない。では、単純に周期が長くなればいいのかと言えばそうではない。たとえば捕食者の繁殖の周期が5年だと仮定しよう。件のセミが15年周期だったとすれば、捕食者の生活環の3サイクル目と繁殖期が一致し、同じように餌食になってしまう。20年とて同じこと。要は両者の最小公倍数のサイクルで繁殖時期が一致してしまうのである。が、13や17という素数なら、そのサイクルをグンと引き延ばすことが可能になる。前述の例で言えば、5年と13年の最小公倍数は65年、5年と17年なら85年だ。16年ゼミの場合も80年だが、捕食者の繁殖のサイクルが5年ではなく4年であれば最小公倍数は16年になってしまう。つまり、捕食者の繁殖のサイクルが2～5年のいずれであっても最小公倍数を大きくできる数、それが素数というわけだ。

と、ここまで書いても、まだ3番目の疑問点が明らかになっていないことにお気づきだろう。11年ゼミや19年ゼミはなぜいないのか、という謎についての説明がまだである。

とはいえ今回も長くなってしまったので、続きは、また。

電車の額面広告に日能研の「シカクいアタマをマルくする。」を見つけると、どうしても自力で解いてみたくなる。夢中になりすぎて、目的の駅をやり過ごすこともあるぐらいだ。

で、今日見つけた問題はこちら。

A君の頭が悪すぎる件はさておき、僕の考え方はこうだ。

1から20までの整数のうち、「2のつく数字」は2、12、20の3つ。2のつく数字を覚えた時点で、それまでに覚えていた6個の数字を忘れるから、3つめの「2のつく数字」を覚えた時点で6×3＝18個の数字が帳消しになり、A君は2、12、20だけを覚えている状態である。あとは残った17個の数字を覚えればいいから、最終的には（6＋1）×3＋17＝38日かかる、と。

ところが、だ。日能研のウェブサイトで解答を確認したところ、正解は44日とある。

しばらく悩んだが、なんのことはない、僕の考え方は3番目の条件にある「覚えた順が古いものから6個忘れてしまう」を満たしていなかったのだ。つまり、「2のつかない数字」を6個覚えてから「2のつく数字」を覚えると、確かに最初の6個は帳消しになるが、この時点で覚えた「2のつく数字」が「覚えた順が一番古いもの」になってしまうため、その次に別の「2のつく数字」を覚えたときに、最初に覚えた「2のつく数字」が優先的に忘れられてしまう……って、文章だといまいち説明しにくいけど、要は必要条件の一部を無視しちゃってたわけですね。

正解の手順を確認し、なるほどと納得。というか、中学入試問題のレベルじゃないっすよ。

日能研 - コラム・読み物 - シカクいアタマをマルくする。 - 2009年8月掲載

時節柄というか、日蝕の話。

世の中的には「日食」という表記のほうがメジャー（実際にGoogleの検索結果でも「日蝕」が22万4000件だったのに対して「日食」は9000万件とダントツに多かった）なようだが、日食は日本食堂の略称に思えて仕方がないので、ここではあえて「日蝕」と書く。

さて、今月22日に観測できるのは「皆既日蝕」である。皆既（かいき）とはあまり一般的ではない言葉だが、これは「すべてが尽きる」といった意味合いである。日蝕は太陽の手前に月が重なる現象だが、太陽よりも手前の月のほうが「見かけの大きさ」が大きく、太陽がすっぽりと隠れてしまうことを皆既日蝕という。逆に月のほうが小さければ太陽のふちが輪のように見えることになり、こちらは「金環蝕」と呼ばれる。ちなみに、皆既月食というのはあるが、金環月蝕はない。月蝕では金環蝕は起こり得ないからだ（月に映る地球の影は月よりも大きいため）。

なぜ皆既日蝕と金環蝕の2パターンの日蝕が起こるのか？　これを説明する前に、もっと根本的な疑問である「太陽と月の見かけの大きさがどうして同じぐらいになるのか？」を解いておこうと思う。太陽は太陽系の惑星群よりも格段に大きく、ましてや地球の衛星である月なんかとは比べようがないぐらいに馬鹿でかい。一方、地球からの距離を考えると、月は比較的近い位置にあるが、太陽はかなり遠い。というか、想像もできないぐらい途方もなく遠い。

すべからく物体は、遠くにあれば遠くにあるほど見かけの大きさは小さくなる。そんなことは日常の領域で理解できる。でも、まったく異なる位置関係にある太陽と月の大きさが、地球から見るとうまい具合に釣り合ってるって、ものすごいことだと思いませんか？

右の図を見てほしい。月と太陽の大きさや位置関係とは似ても似つかないが、単純なモデルに置き換えてみた。右側の点Oが観測者の位置だとするなら、2つの物体が図のような位置関係にあれば、両者の見かけの大きさは同じになる。視線の広がりにぴったり合っているからだ。この状態において、各々の物体の半径の比（r：R）は点Oからの距離の比（d：D）に等しい。なぜって？　図の上半分の補助線が作り出す2つの三角形（直角三角形）の相似条件……みたいな説明は割愛するが、とにかく、r：R＝d：D であれば、両者の見かけの大きさは同じになる、と。これを前提条件として話を進めますよ。

地球を基準に考えると、月までの距離は「月の公転半径」、太陽までの距離は「地球の公転半径」に相当する。両者とも一定ではないため平均値になるが、調べてみたところ前者は38万4400km、後者は1億4959万7870kmであった。つまり、月を1とすると太陽は389.172399となる。一方、月の直径は3474.3kmで、太陽の直径は139万2000km。月を1とすると太陽は400.656247だ。半径の比も直径の比も同じなので、前提条件に照らし合わせると、r：R≒d：Dでおよそ1：400となり、両者の見かけの大きさはほとんど同じであると言える。天文学の専門用語で言い換えれば「月の視直径と太陽の視直径は非常に近い数字である」となる。

前述したとおり、実際には月、太陽ともに地球からの距離は一定ではない（月も地球も公転軌道が真円ではないため、平均公転半径より短いときと長いときがある）。日蝕が起こった時点での距離の比率（太陽÷月）が400を超えていれば、月よりも太陽のほうが見かけの大きさが小さくなり、皆既日蝕となる。逆に400を下回れば金環蝕になるというわけだ。

今朝配信された時事ドットコムの記事から。

返せなかったら殺されてしまうのかとか、それともベニスの商人みたいな屁理屈が通用するのかとかはさておき、個人的に気になったのは「年365％」という金利。日本だと利息制限法により、元本が10万円未満の場合の年利は20％以下でなければならない。この365％という年利がどれだけ法外なものかを確かめるために、ちょっとしたシミュレーションをしてみよう。

日本のローンでもっとも一般的な返済方式は「元利均等方式」。大ざっぱに説明すると、毎回の返済額が一定になる返済方式だ。また、大手のカードローンで契約極度額100万円以下の場合、年利12％というのが相場のようだ。仮にこの方式で10万円を年利12％で借りて1年間12回払いで返済すると、月々の返済額はいくらになるか？　元利均等方式の計算式はちょっと複雑なのだが、結論を先に言えば約8900円。完済時の返済総額は約10万6600円となる。

では、ラトビアの金融業者も同じようにローンを組んでくれたとしよう。上限いっぱいの9万2000円を1年間12回払いで返済。年利は365％だ。これだと月々の返済額は約2万9200円。完済時の返済総額は約35万円となり、借入額の4倍近くの金額を支払うことになる。

ちなみに、途中の割賦返済が一切なく、1年後に耳を揃えて返す場合はもっと悲惨だ。元本9万2000円に対して利子が33万5800円。返済総額はじつに42万7800円である。

Mod 10 checkについての補足。というか、どちらかといえば横道なお話。

ネット上にあるMod 10 checkのサンプルコードをいくつか見ていて、ふと疑問が。手順中の「偶数番目の数字を2倍し、その数が10以上だったら10の位と1の位を足す」という部分の「10の位と1の位を足す」の処理を、単に「9を引く」にしているものが多く見られたからだ。

しばらく思案してみて気付いたのは、1桁の数字を2倍して2桁になった数は、5×2＝10、6×2＝12、7×2＝14、8×2＝16、9×2＝18の5とおりしかあり得ないということ。そして、10の位はすべて1である。このことを踏まえれば、代数を使って証明するのもぐんと楽になる。

10の位をa、1の位をbとする。件の2桁の数は10a＋bで表わされる。「10の位と1の位を足す」はa＋b、「9を引く」は10a＋bー9ということになるが、a＝1という前提条件があるのでこれらは1＋bおよび10＋bー9と置き換えられる。結果的に両者ともb＋1で同じである、と。

ここまで書いて急に思い出したが、昔からある数字当ての手品も似た法則を利用している。ドラマ「TRICK2」にも登場していた記憶があるが、やり方は以下のとおり。

1. 相手に好きな数字を思い浮かべてもらう
2. その数に（たとえば）誕生日の月と日を足してもらう
3. 9を掛けてもらう
4. 1桁になるまで、すべての桁を合計してもらう
5. 最初に思い浮かべた数を足してもらい、その数を聞く

あなたはその数から9を引くだけで、相手が最初に思い浮かべた数字を当てることができるというわけだ。たとえば、相手が思い浮かべた数字が5で、誕生日が2月15日だとしよう。

1. 5
2. 5＋2＋15＝22
3. 22×9＝198
4. 1＋9＋8＝18、1＋8＝9
5. 9＋5＝14

14から9を引けば5。見事に数字が当てられましたね。タネ明かしはまたの機会にでも。

クレジットカード詐欺の話の続きね。

今回の摘発のニュース記事をいくつか読んだのだが、どうも「クレジットマスター」のことをよく知らずに書かれたらしきものが少なくない。あるサイトでは「詐欺の手法」、別のサイトでは「ソフトウェアの名前」といった感じに。門外漢である僕が自分なりに調べてみて分かったのは、実際にこの名前のソフトウェアが存在するということ。どうやら有効なカード番号を生成するものらしい。で、僕が想像するに、クレジットマスターもしくは同等の機能を持つプログラムによって得られたカード番号をオンラインショップなどで不正使用する詐欺の手口自体も、いつしかクレジットマスターと呼ばれるようになったのではないか、と。

ちょっと話がややこしくなるが、前述した「有効なカード番号」イコール「使用可能なカード番号」とは限らない。むしろ、そうである可能性はかなり低い。

女の子から無理矢理聞き出した携帯の電話番号を想像してほしい。それが11桁じゃなかったり、最初の3桁があり得ない数字になっていたり、あるいは数字じゃないものが含まれていたりすれば、デタラメな番号だってことは即座に分かる。彼女のほうもそんなことは承知なので、その場では男が納得するよう「それっぽいけど自分のじゃない番号」を教えるだろう。実際にかけてみると、現在使われておりません云々のメッセージが流れるか、どこかの知らないオッサンに繋がる、と。プログラムが生成した「有効なカード番号」もこれと同じで、カード番号の決まり事に則ってはいるが、それが実際に使える可能性は限りなくゼロに近いということだ。

では「カード番号の決まり事」とは何か？　VISAカードを例にとると、まず16桁であること（かつては13桁のものもあったらしいが、今でも流通している可能性はないと考えていいらしい）。先頭（左端）の数字が「4」であることと、これを含めた先頭4桁がVISAカード固有の番号であること。そしてもうひとつ、Mod 10 checkで「有効」になることだ。

Mod 10については補足が必要だろう。別名を「Luhn formula」と言い、クレジットカードに限らずその筋（?）では割と一般的なアルゴリズムである。手順は以下のとおり。

1. 右端から左向きに偶数番目の桁の数字をそれぞれ2倍する
2. 2桁になった場合は10の位と1の位を足した数とする
3. それらの数字と奇数番目の数字をすべて足す

この手順で算出された数字が10の倍数になっていれば、Mod 10 checkは「有効」となる。それでは、「4532683520687270」という番号を例に計算してみよう。

1. 7×2＝14、7×2＝14、6×2＝12、2×2＝4、3×2＝6、6×2＝12、3×2＝6、4×2＝8
2. 14になった桁は1＋4＝5、12は1＋2＝3とする
3. 0＋5＋2＋5＋8＋3＋0＋4＋5＋6＋8＋3＋2＋6＋5＋8＝70

70はまぎれもなく10の倍数なので、この番号は「有効」である。繰り返すが、実際にこの番号を使って詐欺がはたらけるというわけではないので、早合点しないように。もひとつついでに言えば、実在するクレジットカードの番号を書き写したわけでもないから念のため。

カード番号のうち加入者ごとにユニークな部分（VISAカードの場合は16桁のうちの11桁）も、何らかの法則に従って割り振られていると思われる。チェックサムとかチェックディジットと呼ばれる右端の1桁は、カード番号をMod 10 checkで「有効」にするための調整用だろう。

長くなってしまったが、まだまだ書きたいことがあるので続きは、また。

右は本日夕方のGoogle急上昇キーワードランキング。5位に「クレジットマスター」がランクインしているのは、おそらく以下のニュースを知った人たちがこぞって検索したためと思われる。とりあえず、NIKKEI NETの記事から引用。

まぁGoogleで検索してみたところで、手口の詳細がすぐに見つかるとも思わないし、よしんば知り得たとしても実行するにはリスクが大きすぎると思う（現に摘発されてるしね）。とりあえずここでは、皆さんがこのニュースを読んで普通に抱いたところの「クレジットカードの番号って、計算で割り出せるものなの？」という疑問を基に、僕なりに解説してみようと思う。

クレジットカードの番号は16桁の数字である。じつはAMEXは15桁、ダイナースは14桁なのだが、とりあえず16桁で考えてみよう。この番号がものすごく単純な仕組みだと仮定するなら、0000000000000000から9999999999999999までの1京（1兆の1000倍）とおりの組み合わせが存在することになる。そして、たとえ地球上の60億人が1枚ずつ有効なカードを保有していたとしても、ランダムに選んだ16桁の数字がどれかと一致する確率は1万6666ぶんの1である。まぁ実際には60億枚もないどころか、先進国の労働者全員が持っていると仮定してもせいぜい数百万枚とかのオーダーだろうから、確率はさらにその数千ぶんの1ぐらいになる。

しかしながら、上記の考察はいろんな部分で間違っている。まず、カードの所有者ごとにユニークに付与される番号は、16桁すべてではない。先頭の数桁はカード会社特有の番号、末尾1桁はチェックサムだからだ。チェックサムとは誤り検出符号のことで、クレジットカードの場合はカード番号の各数値に決められた手順の計算を施し、最終的に1桁の数値が算出される。

……えっと、すいません。書いてるうちに眠くなったので続きは、また。

三平方の定理（ピタゴラスの定理とか鉤股弦の定理とも言いますね）じゃなく、あえて三角関数を使う方法も試してみよう。何のため？　いやぁ、もののついでですよ。

それではまず、右の図（ちょっとだけ変えました）を見てほしい。x：y＝4：3 ということは tan θ＝3/4 となるので、逆正接関数を用いて θ＝tan^-1 3/4≒36.87 と分かる。あ、この手の計算は関数電卓がないとできません。また、角度は便宜上ラディアンではなくディグリーで扱います。なので、θは約36.87度（36.87°）ってわけね。

θが決まったので、sin θ＝sin 36.87≒0.6 と求められる。さらに、sin θ＝y/z なので、y：z＝3：5。ちなみに、余弦関数を使って cos 36.87≒0.8、x：z＝4：5 という求め方も可能。いずれにしても、これで x：y：z＝4：3：5 という先のエントリと同じ結果が得られました。

と、えらそうに書いてはみたものの……合ってるのかな？