Life is beautiful

　このブログでも何度か書いたことがあるが、ソフトウェアを書くのに高度な数学が必要なケースはマレで、ほとんどの場合は中学生程度の数学で十分である。ただし、中学生時代の数学を「公式の丸暗記」でしのいで来たような人ではなく、「難しい応用問題をエレガントに解くのが楽くてしょうがなかった」ような人が向いているというのが私の持論だ。

　例として、以下の二つの数学の問題を見て欲しい。

例題１．時計の長針と短針は、１２時にちょうどピッタリと重なります。次にピッタリと重なるのは何時でしょう。

例題２．サイコロを２個、順番に投げることにします。１つ目のサイコロの目の方が二つ目のサイコロの目より大きい確率を求めてください。

　どちらも、中学生の数学を使って解ける問題ではある。例題１は方程式を使って解くことができるし、例題２は順列組み合わせの考えを適用すれば解くことはできる。しかし、それで満足してはいけない。

　プログラミングにしろ数学の計算にしろ、複雑になればなるほど「うっかりミス」は生じやすい。となれば、出来るだけミスの生じにくい、直感的でエレガントな解き方を見つけるべきなのである。極力バグを減らす。極力計算ミスをなくす。全く同じことである。その意味でも、「人間にミスはつきもの」という前提のもとで、「いかにミスが生じにくいような解き方・プログラムの書き方をするか」を常に真剣に考えるクセを身に着けておくことは大切である。

　ちなみに、ここまで読んで、「あれ、上の問題のエレガントな解法は教えてくれないのかな？」と思った人がいるとは思うが、あえて今日は答えは書かないでおくのでぜひとも自分で考えてみて欲しい。十分にエレガントな解き方にいたることが出来れば、計算は暗算でできるはずだ。別の言い方をすれば、どちらの問題も、紙と鉛筆を使わずに頭の中だけで、それも中学生程度の数学だけを利用して解けるのだ。

　成田エクスプレスに乗る前に、駅のキオスクで何気なく手に取った「週間ダイアモンド」に多湖輝氏の名前を発見。一度も直接合ったことはないが、私の大の恩師である。

　多湖輝氏の『頭の体操』を片っ端から読みあさったのは小学生の高学年のころだ。解けない問題の答えを見るのが悔しくて、一冊読むのに何ヶ月もかかってしまったのを覚えている。

　知的ゲームの楽しさ、既成概念に捕らわれない発想法、難しい問題に取り組む姿勢、柔軟な頭の使い方、など今の私を形作る上で幾つもの重要なレッスンを与えてくれたのが、この『頭の体操』シリーズだ。私は何につけても出来るだけ人と違う発想をしようと試み、誰も思いついたことがない事をすることに喜びを感ずるが、そのルーツは『頭の体操』にある。

　ソフトウェアの開発効率は、開発の過程で生ずるさまざまな問題をいかに効率よく解決して行くかにかかっているが、『頭の体操』で鍛えられた頭の柔らかさに何度助けられたか分からない。私は常々、「大半のソフトウェアの開発には中学生程度の数学で十分」と言ってきたが、今度からそれに「ただし、『頭の体操』で柔軟な頭の使い方をトレーニングしておくこと」を追加しよう。これからソフトウェアエンジニアを目指す学生ならば、微積分の問題を解く能力よりも、金貨問題を解く頭の柔らかさの方が、実戦では何倍も役に立つことを覚えておいた方が良い。

　今の日本の小学生は、低学年のころから塾で受験勉強をさせられるらしいが、そんな詰め込み型の教育が本当に日本の将来のためになるのだろうか、と不安になる。脳の発育にとって一番大切な時期を、極度にゆがんだ教育システムの中で過ごした子供達は、柔軟な発想が出来る大人になれるのだろうか？

　そもそも、今の受験システムは「勉強して一流大学に入れば、一流企業や役所に就職できて、そこが退職後の天下り先まで世話してくれる」という社会構造を前提として作られてきたわけで、その社会構造そのものが崩壊しつつある今、そんな受験勉強で子供の頭脳を疲弊させるより、『頭の体操』でも読ませてどんな時代が来ても柔軟に対応できる大人に育ててあげた方が良いような気がする。

　先日、宿題に出しておいた金貨クイズ、今回は計４名が正しい答えを送ってきた。予想に反して、そのどれもが私が用意していた答えと異なるものであった。予想外だったもので、検証に手間取ってしまったが、どれも正しく偽造品を見つけることの出来る手順であった。

［模範解答］
　まず考えやすくするために、中間ゴールとして、２回天秤を使ったところで、後１回で偽金貨が分かる状態にまで持って行くことにする。その状態には、

（a）２つの金貨のうちどちらかが偽造品だ判明している状態、
（b）３つの金貨に偽造品が含まれていることが判明しており、かつ、すくなくともそのうち２つが偽造品だった場合に本物より重い（もしくは軽い）のが分かっている状態、

の２通りがある。（a）の場合には、片方の金貨を本物の金貨と比べて見れば良いし、（b）の場合にはそのうち偽造品だった場合に本物より重いのか軽いのかが分かっている二個の金貨の重さを比べれば良い。

　まず金貨を４個ずつ天秤に乗せて比べる（１回目）。このとき、左の皿に置いたコインを【ＡＢＣＤ】、右の皿に置いたコインを【ＥＦＧＨ】、残りの５つを【ＶＷＸＹＺ】と呼ぶ。

１．釣り合った場合、【ＶＷＸＹＺ】の中に偽造品があることが判明。
　【ＶＷＸ】と【ＡＢＣ】を比べる（２回目）。
　1-1．【ＶＷＸ】が重い場合、【ＶＷＸ】の中に重い偽造品があることが判明 （b）
　1-2．【ＶＷＸ】が軽い場合、【ＶＷＸ】の中に軽い偽造品があることが判明 （b）
　1-3．釣り合った場合、【ＹＺ】の中に偽造品があることが判明 (a)

２．【ＡＢＣＤ】が重い場合、【ＶＷＸＹＺ】の中に偽造品がないこと、【ＡＢＣＤ】の中に偽造品がある場合には重い偽造品、【ＥＦＧＨ】の中に偽造品がある場合には軽い偽造品であることが判明。
　【ＡＢＣＥＦ】と【ＶＷＸＹＺ】を比べる（２回目）。
　1-1．【ＡＢＣＥＦ】が重い場合、【ＡＢＣ】の中に重い偽造品があることが判明 （b）
　1-2．【ＡＢＣＥＦ】が軽い場合、【ＥＦ】の中に軽い偽造品があることが判明 （a）
　1-3．釣り合った場合、【Ｄ】もしくは【ＧＨ】に偽造品があることが判明 (b)

３．【ＡＢＣＤ】が軽い場合は、２と全く同じ操作で良いので省略（「重い」と「軽い」を入れ替えて考えれば良い）。

　この問題につまずく人はたいてい、既に本物だと判明した金貨をリファレンスとして使えるということに気がつかないために苦労するようだ。特に、ステップ２に至った段階で、「せっかく１３個から８個に絞ることが出来たのだから」と、【ＶＷＸＹＺ】を頭の中から除いて考えてしまうようだ。

　ちなみに、模範解等を考えているうちに、この問題にある工夫をすると、１４個の金貨の中からでも偽造品を見つけられることが判明した。さて、その「ある工夫」とは何だか分かる人はいるだろうか？

　先日の「ビル・ゲイツの面接試験－クイズ編」に対して、メール、トラックバック、mixiなどを通じて沢山の方から答えをいただいた。そこでここで模範解答を発表。さすがに難しかったのか、全問正解者はたった一名であった。予想した通り、第三問が難関であったようだ。

［第一問］多くの人が正しく答えた通り、手順は以下の通りである。
（１）８個の金貨のうち６個を適当に選び、３個づつ天秤に乗せて比べる。
（２）片方が軽かった場合（３）へ、釣り合った場合（４）へ。
（３）軽かった側の金貨のうち２個を適当に選び、１個づつ天秤に乗せて比べる。片方が軽ければそれが偽造品、釣り合えば残りの金貨が偽造品。
（４）（１）で天秤に乗せなかった金貨２個の重さを天秤で比べ、軽い方が偽造品。

［第二問］８１個。
　天秤は、一回の操作で、「左が重い」・「釣り合う」・「右が重い」の３値の情報を与えてくれる。それを正しく利用すれば、一回の操作ごとに、答えの可能性を３分の一に減らすことが出来るのである。逆に言えば、一回の操作では答えが３通りある状態（つまり、３個の金貨のうちどれか一つが軽いと分かっている状態）から、どの金貨が偽造品か確定できている状態にまで絞り込めるのである。同じように二回の操作では、答えが９通りある状態（つまり、９個の金貨のうちどれか一つが軽いと分かっている状態）から、どの金貨が偽造品か確定できている状態にまで絞り込めるのである。つまり、k回の操作で、答えが「３のk乗」通りある状態（つまり、「３のk乗」個の金貨のうちどれか一つが軽いと分かっている状態）から、どの金貨が偽造品か確定できている状態にまで絞り込めるのである。この問題では、k=4なので、金貨の数は「３の４乗」となる。すなわち天秤を４回使えば、８１個の金貨の中から偽造品を見つけることができるのである。

［第三問］１３個
　この「偽造金貨が重いか軽いか不明」なケースにおいては、金貨がN個の場合、可能な答えはＮ通りではなく、２Ｎ通りとなる（１個目が軽い、１個目が重い、２個目が軽い、２個目が重い、…）。第二問の解説で述べたように、天秤を３回使える場合、最大２７の可能性から一つの答えに絞り込むことが可能である。つまり、２Ｎが２７を超えない最大の整数、Ｎ＝１３（金貨１３個）が、最適の手順で天秤を３回使った場合に偽造品を見つけ出すことが出来る最大値である。

［第五問］金貨の数を２のべき乗である８にすることにより、二分法を使うようにミスリードしている。　
　少し前の記事でも書いたが、エンジニアは、８だとか１６だとかいった２のべき乗に過敏に反応する性質がある。金貨の数を最大の９個にせず、あえて８個にすることにより、「これは金貨を半分に分けては比べていく二分法を使えば良いんだな」とミスリードするのである。面接に来た学生の多くがこのミスリードに引っかかるのだ。

［第六問］log23ビット。log23は２を底とした３の対数、約１．５８５。
　出題の時にも書いたが、この問題は、「情報理論」を単位をちゃんと取得した情報学科の学生にしか答えられない問題である。そんな学生であれば、１ビットでは０と１の２値を、２ビットでは０、１、２、３の４値を表すことができることは知っているので、天秤を一回使って得られる、「左が重い」・「釣り合う」・「右が重い」の３値のデータに含まれる情報量は、１ビットより多く、２ビットより少ないことは分かるはずだ。後は、高校でならった数学を応用して、log23ビットという答えにたどり着く。

　ちなみに、賢明な読者は気づいたと思うが、「第四問」の答えは今回はまだ提示しない。あまりに多くの人が第三問でつまづいてしまったために、このクイズのハイライトであり、一番面白い「第四問」にチャレンジする機会を与えずに答えを提示してしまのは、あまりにもったいないと思うのである。

　そこで、あらためて第四問を書き、今回の宿題とする（ブログで宿題を出してはいけないルールなど無い^^）。

［第四問］ここに１３個の金貨があり、そのうち一つだけがとてもよく出来た偽造品で、他の金貨よりわずかに重さが違う（重いのか軽いのかは不明）ことだけが分かっています。天秤を使ってどの偽造品を見つけ出したいのですが、天秤を一回使用するたびにお金がかかるので、出来るだけ最小の手数で偽造品を見つける必要があります。どうしたら良いでしょう。

　ちなみに、この問題をためしに私の会社の社員（全員アメリカ人）に出した所、正解を出してきたエンジニアもいたのだが、以下のような答えも返ってきた。

・金貨を机の上にならべて天秤で何度も叩く。キズのつき方が他と異なるものが偽造品である。
・金貨を使って店で買い物をし、しばらくしてから返品することにより、偽造品を本物と取り替えてしまう。

まともな答えが出せない時は、こんな答えを返してくるところがいかにもうちの社員である（笑）。

　先日書いた、「ビル・ゲイツの面接試験－私の場合」がとても好評だったので、調子に乗ってもう一つ披露しよう。今回は問題のみを書くので、頭の体操と思って楽しんでいただきたい。

［第一問］ここに８個の金貨があり、そのうち一つだけがとてもよく出来た偽造品で、他の金貨よりわずかに軽いことだけが分かっています。天秤を使ってどの偽造品を見つけ出したいのですが、天秤を一回使用するたびにお金がかかるので、出来るだけ最小の手数で偽造品を見つける必要があります。どうしたら良いでしょう。

［第二問］上の問題と同じ（他の金貨よりわずかに軽い偽造品が一つだけ混ざっている）条件で４回まで天秤を使っていいとすると、最大で幾つまでの金貨の中から偽造品を見つけ出すことが出来るでしょう。

［第三問］今度は少し条件を変えて、偽造品は「本物と少し重さが違う」ことは分かっているのですが、重いのか軽いのかは不明だとします。この場合、３回まで天秤を使っていいとすると、最大で幾つまでの金貨の中から偽造品を見つけ出すことが出来るか予想してみてください。

［第四問］第三問で予想した数の金貨の中から、天秤を３回だけ使って「本物と少し重さが違う」偽造品を見つける手順を示してください。

［第五問］（心理学の問題）第一問で、私が金貨の数を９個ではなく８個としたのはどうしてでしょう。

［第六問］（情報科の学生のみ）天秤を一度使うごとに、ある一定の「情報」が得られるのですが、その情報量は何ビットでしょうか。

　答えは、このブログのコメント欄でも、自分のブログに書いてトラックバックしていただいても良い。特に第三問で設定した問題を、第四問として自分自身で解くところがミソなので、ぜひとも楽しんでいただきたい。

　マイクロソフトの採用面接がユニークであることは、「ビル・ゲイツの面接試験－富士山をどう動かしますか」という本で一時話題になった。もちろん、私自身もマイクロソフト本社で面接官として数え切れないほどのエンジニアの面接を担当し、自分なりに工夫して作り出した試験問題を幾つも用意していた。今日は、その一つを披露して、得意のうんちくを展開しよう。

［問題］
二次元座標上に、それぞれの辺がX軸・Y軸と平行に置かれた長方形Aと長方形Bがあるとする。その時、長方形Aと長方形Bが一部でも重なるかどうかを判断する条件式を書け。フォーマットは、CやJavaなどのコンピューター言語でも良し、単なる数式でも良い。制限時間は３０分。ただし、考えていることを声に出し、ホワイト・ボードを使って自分の考えのプロセスを説明しながら解くこと。

　もし、これからプロのソフトウェア・エンジニアを目指そうという理科系の学生がこのブログを読んだのであれば、いったんここでストップし、まずは自分自身でこの問題にぜひチャレンジして欲しい。とても良い頭の体操になるはずだ。

　マイクロソフトにおける採用面接、特に大学を卒業したての新人の採用面接で一番重視しているのは、「raw intelligence」である。直訳すれば、「生（なま）の知性」である。そこには、「知識は必要に応じて付ければ良い。一番大切なのは、新しい知識をすばやく見に付け、それを応用して難しい問題を解決する知性だ」という会社としての確固たる信念がある。

　その方針に従って学生を面接するには、単に「今まで学校でどんなプロジェクトをしてきたの？」とか、「どんな言語でプログラムが書けますか？」などという悠長な面接をしていてもほとんど役に立たない（そもそも、その手の情報は既に提出された履歴書に書いてある）。自分の受け持ちの３０分から１時間の間に、どれだけその人の「raw intelligence」にチャレンジするディスカッションができるかが勝負となるのだ。面接官によっては、先の本のタイトルにもあるように、「あなたなら富士山をどう動かしますか」などと、あえて簡単な解答が無い問題を出すことにより、脳みその柔軟さを測る作戦に出たりするのである。

　私の場合は、上の問題のように一見シンプルだが複数の解き方のある問題を出すことにより、（１）問題を解きながら、どうやったらより簡単に答えにたどり着けるかを探る習慣があるか、（２）複雑な問題をより単純な複数の問題に分割して考えるというトレーニングを受けているか、（３）解答のエレガントさ・シンプルさにこだわるタイプか、を測る作戦を採用していた。

　この問題を初めて見た場合、ほとんどの学生は、まずは２つの長方形のさまざまな交わり方をホワイト・ボードに書き始める（学生が既にこの問題を解いたことがあるどうかは、この段階で見極めなければならない。そうであると判断すれば、別の問題に切り替える）。そこで多くの学生が、この問題が意外に複雑であることに気が付く。長方形の交わり方には上下左右の関係を別々に考えれば、１６通りもの交わり方があるのだ。ここで、その１６通りの交わり方をそれぞれを式にして、ホワイト・ボードを埋め尽くし始める学生がいるのだが、そのアプローチを取ると、ほとんどの場合規定の時間内に答えを書き終えることが出来ないし、作業の煩雑さゆえにどこかで必ずケアレス・ミスをする。こっちは、そんな煩雑な作業に取り掛かる前に、「こんなに手間だけがかかる問題をこの面接官が出すはずがない。もっと簡単な方法があるはずだ。」と気が付くような学生を求めているのである。

　そこで、賢い学生は、ここで一旦手を止めて考え始めるのである。「もっと簡単に解く方法があるはずだ。なんとか、この問題を、より単純な複数の問題に分割できないだろうか？」。ここまで来れば、次のステップにたどり付くのは時間の問題である。そして、「ひょっとしたら、X座標とY座標を別々に考えても良いのではないだろうか？」と気づくのである。先ほどの図を見ながらこれを検証するにはそれほど時間がかからない。

　X座標だけに着目して考えれば、交わり方は４通りだ（AがBを含む場合、BがAを含む場合、AがBの左端と重なっている場合、AがBの右端と重なっている場合）。そしてそれぞれの交わり方の検証には、2回もしくは３回の比較演算が必要である。これならホワイト・ボードを埋め尽くせずに式が書ける。多くの学生は、このアプローチが正解にたどり着く道と信じて、式を丁寧に書き始める。

　この問題のすばらしい所は、これでもまだ「最もエレガントな」解答では無いことだ。多くの学生はこの時点で満足してしまうので、「良く出来たね。でも、もっとエレガントな方法があるんだけど気が付かない？」と催促してあげる必要がある。ここで、相手の目がチャレンジ精神に燃えてキラキラ輝き始めたらとても良いサインだ。

　この次のハードルは、就職がかかった面接というプレッシャーのかかった場で越すのは学生には少し難しいので、「確かに交わり方は４通りだけど、もう少し簡単に交わっているかどうかをテストする方法があるんだよ」などのヒントを出してあげる必要がある。この段階で「交わらない場合は（AがBより右にある、AがBより左にある、の）２通りしかない」ことに気が付けば、もう正解は目の前である。後は自動的に、交わらないことの検証には比較演算が１回づつしか必要ないことに気が付き、結果として、トータルで４回の比較演算とわずかな論理演算だけ（プログラムにすればわずか2行で）でこの問題が解けてしまうことに気づくという仕掛けである。一部の学生は、この段階で、最初から交わらない場合を考えていれば、XY座標を分割して考える必要が無かったことに気がつくのだが、そこまで３０分でたどり着けるのはごく一部の学生だけだ。

　ちなみに、この手の問題を使って面接する場合には、学生を適当に励ましながら、正しい方向に導いてあげることが必要だ。そのプロセスの中で、こちらのガイドラインやヒントにどのくらい敏感に反応してくるか、エレガントな解答にどのくらいこだわっているか、などかが分かってくるのだ。

　もし、理科系の学生でこの問題が解けなかった人がいたとしても、ショックを受ける必要はない。大切なことは、上で述べたような、よりシンプルでエレガントな解決法を常に探す気持ちを大切にして、自分自身を鍛えて行くことだ。一つの答えが出たところで満足せずに、「もっとエレガントな手法はないか、もっとシンプルな答えはないか」と考える姿勢を養うことが大切だ。学校の試験であれば、答えを提出してしまえば終わりだが、仕事でろくでもないプログラムを書いてしまうと、後々までタタられるのだから。

［追記］好評に付き、「ビル・ゲイツの面接試験－クイズ編」というのも書きました。面接官としてのうんちくは抜きにして、単に問題だけを書いたので、頭の体操だと思ってチャレンジしてみてください。

　これまで、単なるニュース記事の紹介やウェブサイトの紹介はしまいと努めてきたのだが、あまりにもよく出来た（というか楽しい）IQテストのサイトを見つけてしまったので、紹介する。

　http://www.iqtest.dk/main.swf

　今まで試したIQテストは、「簡単すぎて時間ばかり競うもの」だったり、「やたらと難しくて、IQを計っていると言うよりは、特殊なパズルを解く能力を測っている」だったが、これは難しさのバランスがとても良く出来ている。

　４０分で３９問を解けと説明文にあるので、「そんなの１０分で解いてやる！」と思い切り侮（あなど）って始めたら、しっかりと４０分かかってしまった。３０問目を過ぎたあたりからすぐに答えが分からないのが出始め、そういったものを飛ばしながらやっていても解けるものを解くのに３０分以上かかり、残りの１０分で取りこぼした数問に取り掛かったが、最後の最後に残した２問が、やたらと難しく、「あてずっぽを入れる」という屈辱を味わうハメにあった。

　ちなみに、一つだけ注意点がある。かなり「理科系頭」向けのIQテストになっているのだ。私のような理科系の人間にとっては、問題を解くのも楽しいし、結果として表示されるIQも結構良い（これは私にとって「良く出来たIQテスト」の必須条件＾＾）。文科系頭の人がやると、結構キツイかもしれない。結果が悪くてショックを受けても私のせいにしないでいただきたい。そういう人には、大人のセンター試験（下のリンク）の方がお勧めかも知れない。

　http://www.sourcenext.com/mail/