CMU には TartanTrak というキャリアサイトがあります。Linkedin や Monster.com 同様、そこに履歴書をアップロードしておくと、会社の側から「あなたの履歴書見つけました」という形でコンタクトしてくる場合があります。12月の頭に、そのベンチャーキャピタルからコンタクトがあって電話インタビューに応じたことがありました。社員数10人強の少数精鋭の会社で、インタビュー質問もやはりタフでした。残念ながら、答えを出すのにかなりの助けを借りてしまい、電話インタビュー 2nd ラウンドで落ちてしまいましたが、質問が面白かったのでここに載せてみます。両方とも 2nd ラウンドで出された問題です。
[問題1]
ここに正六面体の普通のサイコロが2つあります。それぞれ A, B と呼びましょう。A のサイコロは、1つの面が赤く塗られ、残り5つの面は青で塗られています。B のカラー分布は分かりません（ただし色は赤と青のみと考えてよいです）。この2つのサイコロ A, B を使って次の実験を繰り返しました。一回の実験で行うことは、両手にサイコロ A, B を持ち、同時にそれらを転がし、出たそれぞれの色を確認することです。さて、実験の結果、半分の確率で A と B の色は一致し、半分の確率で A と B の色は一致しませんでした（実験回数を限りなく多くしているから半分の確率と言ってさしつかえないと、実際のインタビューでも言われました）。さて、この実験結果から B のサイコロのカラー分布はどのようになっていると思いますか？
[問題2]
ここに100個の文があります。それぞれ 0 から 99 までナンバーが振られており、次のようなことが書かれています。
文 0 「この中に正しい文はたかだか 0 個存在する」さて、正しい文はいくつあるでしょう？
文 1 「この中に正しい文はたかだか 1 個存在する」
文 2 「この中に正しい文はたかだか 2 個存在する」
・・・
文 98 「この中に正しい文はたかだか 98 個存在する」
文 99 「この中に正しい文はたかだか 99 個存在する」
問題2は、ぱっと見た感じだと結城先生の数学ガール第3巻の冒頭にある問題「正直者は誰？」に少し似てるかもしれませんね。
3分ほど考えただけなので、あってるかどうかは知りませんが、
返信削除1. 赤:3 / 青:3
２個目のサイコロで赤が出る確率をpとして、1/6*p+5/6*(1-p)=1/2。p=1/2。求めた後に、この条件だと一つ目のサイコロの色分布に関わらず、2個とも同じ色になる確率は1/2になるのかと納得。
2. 50個
i番目の文が正しいと仮定すると、i番目以上の文はすべて正しくなるので、正しい文の数は100-i。i番目の文はi個正しい文があると主張しているので、100-i=iとなるiを求めて50個。
@Eiji さん
返信削除ご回答ありがとうございます。問題1は、まさにおっしゃる通りです。問題2は、i番目の文が主張していることは、正しい文がたかだか(at most) i個ある、ですのでそこから導かれるのは不等式 100 - i <= i すなわち 50 <= i となります。最終的な答えは Eiji さんのおっしゃる通り 50 です。50 <= i まで来たら、残りの仕事は i の upper bound を見つけてあげるだけになります。
しかし、3分ほどとはビックリです。すごいです、インタビューエースになれます！
ああ、確かに私の2.の議論は正確ではないですね。議論の方向性を変えずに修正すると、i-1番目の文は間違いでi番目の文が正しいと仮定すると正しい文の数は100-i。i-1番目が間違いでi番目が正しいという仮定は正しい文がi個あるという仮定等しいので、100-i=i。
返信削除（厳密にはn番目が正しくてm(>n)番目が正しいことがありえないことも言わないといけませんが、省略ということで）
3分で出来たとはいえ、目の前に文章で問題が書いてあって、なんのプレッシャーもない状態と、電話で時間的なプレッシャーありの状態ではかなり違いますから、実際のインタビューではこうは行かないとおもいます(^^;
@Eiji さん
返信削除ご名答です！うーん、素晴らしい。