昨日は独力ですべてやってみましたが、検索やらいただいたコメントやら、総力を挙げて模範解答を考えてみました。なお、昨日とは異なり、問題は日本語訳のみ掲載します。原文にご関心の方は、昨日のエントリをごらんいただければ。
#以後、より正しそうな解答を見つけたり教えていただいたりした場合には、随時訂正していきます。
Q1.スクールバスにゴルフボールは何個入るか?
フェルミ推定という定番の問題のようです。つまりは、ドレイクの方程式のように推定すべき事項を考え出して、それぞれに推定値を当てはめて試算値を出す、という方法で答えを求めることとなります。
この問題の場合、
- (スクールバスの(空間の)容積×球体を詰め込む場合に隙間にならない(=球体で占められる)部分の比率)/ゴルフボールの体積=詰め込めるゴルフボールの個数
という式に推定値を当てはめていく、ということになるでしょう。
スクールバスの大きさを、L10m×W2.5m×H3mとし、壁や窓の厚さはネグリジブルだとすると、容積は75立方メートル。エンジンや座席などのゴルフボールを詰め込めない部分やロードクリアランスの体積がこの容積の1/3だと仮定すると、50立方メートルにゴルフボールを詰め込むことになります(後の計算の便宜を考え立方センチメートルに換算すれば、5,000万立方センチメートル)。
ゴルフボールは直径42.67mm以上でないとならないとのことなので、計算の便宜上直径44mmとすると、体積は4/3×π×2.2^3≒45立方センチメートル。球を空間に充填する場合、ケプラー予想(って、証明されたので「定理」の方がいいのかしらん?)から最大で74.04%にしか詰め込めないということになるので、
- (5,000万×0.7404)/45=822,666.66…
となり、82万2,666個のゴルフボールが詰め込めることとなります。
#面接の場での対応となると、ゴルフボールの大きさは直径4cmといった程度の近似でいいでしょうし、隙間の掛け目も0.6とか0.7といったものでかまわないのでしょう。
Q2.あなたは5セントコインほどのサイズに縮んでしまう。質量は今現在のオリジナルの密度を維持している。そしてあなたはガラスのミキサーに投げ込まれる。ミキサーの刃は60秒で動き出す。さぁ、あなたはどうする?
#昨日のエントリのもので間違ってはいないようなので、再掲します。
5セントコインが直径2cmとして、約1/100の長さに縮むと考えられます。同じ密度のまま重さも少なくなるとのことですが、となれば重さは体積に比例するので、長さの3乗=約1/100万の重さになります。他方、筋力は筋肉の断面積に比例するので、長さの2乗=約1/1万の力となります。
したがって、体重に対する筋力の割合は約100倍となるので、縮む前に垂直とびで身長の1/3飛べるとして、縮んだ後は100×1/3=身長の約33倍の高さまで飛べることとなります。2cmの身長の33倍ですから66cm飛べるようになるので、ミキサーから飛び出して逃げられます。
#安全を見て縮尺を1/80、垂直とびの高さを身長の1/4としても、80×1/4=20倍で40cmは飛べますが、それほど大きなミキサーはないでしょうから、やはり飛び出して逃げることは可能でしょう。
Q3.シアトルのすべての窓ガラスを洗浄するとして、あなたはいくら請求しますか?
おそらくこれもフェルミ推定で解くべきものと考えられるので、そのやり方で。
この問題の場合、
- シアトルのすべての窓ガラスの表面積×窓ガラス洗浄の面積当たり単価=シアトルのすべての窓ガラスを洗浄した場合の市場価格
という式が考えられます。まず、窓ガラス=板ガラスとみなしてその生産量を求めると、日本の2006年の総生産量は27,874千換算箱、日本の世界シェアが1994年の25%から不変と仮定すると世界の総生産量は11万1,496換算箱となります。
ガラスをどれだけ使うかはGDPに比例すると仮定すると、アメリカのGDPシェアがだいたい世界の30%なので、全アメリカでの板ガラス消費量は33,500千換算箱となります。シアトルは人口で全米第25位、加えて各種産業が集積しているので、その一人当たりGDPが州平均で最も高いコネチカット州のそれと同じだと仮定すれば、シアトルでは49,852ドル×57万3,911人=286億ドルの付加価値生産があると推計されます。アメリカの名目GDPが13.2兆ドルですから、シアトルのシェアは0.22%となるので、板ガラス消費量は72.5千換算箱ということとなります。
年間のフローがそれだけだとしてストックがどの程度になるかですが、ガラスのグリーンハウスの耐用年数が20年以上とのことなので、20年で入れ替わると仮定すればストック量は72.5×20=1,450千換算箱。1換算箱は9.29平方メートルに当たるので、シアトルのすべての窓ガラスの表面積は1,347万平方メートルとなります。
ガラス洗浄の面積当たり単価は、さすがに日本のもので代用させてもらうと、ぐぐるとだいたい150円/平方メートルあたりが大規模清掃の場合の相場のようなので、
#上記のような計数が面接の場ですらすら出てくるはずもないので、実際にはシアトルの人口等からある程度の推測をする、ということなのでしょう。(住居よりも)オフィス関係の窓ガラス量の推計が難関ですが、シアトルの都市圏人口は400万弱ということで多くの者が流入して120%近くにはなると仮定し、労働者数が30万人(シアトル市内で20万、市外から10万)程度だとあたりをつけるといったところでしょうか。
Q4.マシンのスタックがメモリ内で増えるか減るかしているのをどのようにして見つけ出しますかマシンのスタックがメモリ内で上向きに伸びるか下向きに伸びるかを知るにはどうしたらいいですか?(fcpさんのコメントを踏まえ訂正しました。(9/23訂正・追記))
#lukeさんの解答より。
関数Aの局所変数へのポインタaを関数Bに渡し、関数Bの局所変数へのポインタbとの大小を比較します。ここで、a>bならスタックは減ります(grow downする)。ただし、関数Bがインライン展開されないようにする(たとえば、Bを再帰的関数にする)必要があります。(9/18追記)(9/19訂正(不等号の向き))
わかりません。
#IT業界でご活躍の方のご協力をいただければ幸いです。
Q5.あなたの8歳の甥にデータベースについて3つの文で説明しなさい。
昨日のエントリにいただいたゲストさんの解答より。
お前にも女友達がいるだろ? 彼女たちが好きな色、花、彼女たちの誰が誰と仲がいいかをお前は知っている。それがデータベースだ。
Q6.時計の長針と短針は一日に何回重なりますか?
メイルでいただいた解答より。
(解法1)長針は1日当たり24周する一方、短針は1日当たり2周しかしないので、長針は短針を22周の周回遅れにする=22回追い抜く=22回重なります。
(解法2)長針は1分当たり6度進み、短針は1分当たり0.5度進むので、長針が1周する間に短針は0.5×60=30度進み、長針が30度進む5分の間に短針は0.5×5=2.5度進み、その次の1分後までに長針は短針を追い越すことができるので、長針と短針が重なる間隔は1時間5分強。24時間を1時間5分で割ると22余り10分なので、22回(ちなみに1時間5分強は、正確には1時間5分27秒になります)。
#昨日のエントリの解答でも間違ってはいないのですが、あの方法で解くならば、0時1分から翌日の0時0分59秒で考えた方が楽でした。
Q7.あなたはA地点からB地点に行かなくてはならない。そこに到着できるかどうかは知りません。どうしますか?
#通りすがりさんの解答より。
A地点および自分が行き方を知っている場所以外の場所への行き方を誰かに聞き、行き方を教えてもらった場所がB地点でなければ、その場所以外への行き方を誰かに聞き(たとえば、C地点への行き方を自分が知っていて、D地点への行き方を聞いたならば、C・D地点以外への場所への行き方を聞き)・・・とB地点への行き方を教えてもらうまでそれを繰り返し、教えてもらったらその行き方でB地点へ行きます。(9/18追記)
#昨日の解法に自信があるわけでもないのですが、間違っていると決まったわけでもないので、とりあえず再掲します。
A地点において、B地点を知っている人を探し、
B地点への行き方を知っているかどうか、
行き方を知らない場合、A地点よりもB地点に近い場所を教えて欲しい、
と尋ねます。1.で行き方についての回答が得られればそのとおりにB地点に行き、得られなければ2.で教えてもらった場所に行き、同じことをB地点に着くまで繰り返します(ただし、2.の「A地点」はそのとき質問している場所になりますが)。
Q8.シャツでいっぱいの戸棚があるとします。特定のシャツを見つけるのは非常に難しいです。簡単にシャツを見つけるためにどのように整理しますか?
#これもQ67(9/13訂正)と同じく、とりあえずの再掲です。
- ハンガーに掛けられたものが並んでいるとして、その状態で一目で識別可能な特徴で階層化します(半袖か長袖か、各色、無地かストライプか、等。まずは半袖で白で無地のグループ、その隣が半袖で白でストライプのグループ、といった具合)。
- 次に、シャツの特徴を洗い出し、yesとnoで答えられる質問を最大数のグループで差異化できる程度(最大で10枚のグループがあるならば4問(2^4=16)程度)考えます。
- 2色の洗濯バサミを用意し、2.で考えた質問の答えがyesならある色、noなら別の色を質問の数だけ袖に挟んでいきます。
- シャツを見つける際には、まずグループで絞込み、洗濯バサミを見て特定します。
Q9.100組の夫婦からなる村で、男性は全員浮気したことがあります。どの妻も、自分の夫でない男が浮気するとすぐにそれを知ることが出来ますが、自分の夫が浮気してもわかりません。そしてこの村の掟では浮気や姦通は許されていません。自分の夫が浮気していることがわかった妻はその日のうちに自分の夫を殺さなければならないという掟があります。この村の女達は掟には背きません。ある日、村の女王が言いました。この村には浮気をしている男が少なくとも1人はいる。さて、この村に何が起きますか?
#質問の訳文は、tockriさんのものに替えました。
昨日のエントリにいただいた望月衛さんの解答より。
100日後めに夫は全員殺されます。というのも、もし浮気をしている夫が1人なら、村の女王の言葉を受けてその日に誰も殺されなければ、その夫の妻は誰の夫の浮気も関知できないにもかかわらず誰か1人浮気している=浮気をしているのは自分の夫だと消去法で特定でき、翌その日に自分の夫を殺します。浮気が2人なら、その夫の妻は自分の夫以外の 1人(仮にaとします)の浮気にのみ気づくわけですが、もし浮気をしているのが1人なら既述の消去法でaの妻はaを殺すはずなのに殺さない=aの妻も誰か1人の浮気に気づいている=a以外にもう1人浮気している夫がいて、それは自分が気づかない自分の夫だと認識でき、2日後めに自分の夫を殺します(同様にaの妻もaを2日後めに殺します)。浮気が3人(仮にx、y、zとします)なら、xの妻はyとzの浮気に気づいていますが、浮気しているのがyとzだけならば既述のとおり2日後めにyとzが殺されるはずなのに殺されない=yとzの妻も2人の浮気に気づいている=yとz以外にもう1人浮気している人間がいて、それは自分が気づかない者であるxだと認識でき、3日後めにxが殺され、同じようにyとzも殺されます。
以後同様に考えれば、この問題でいえば99日後めまで誰も殺されないので、すべての妻が自分が気づいている99人の浮気者以外にもう1人浮気者がいる=自分の夫が浮気していると認識することとなるため、100日後めにはすべての妻が「自分の夫が浮気していることがわか」り、「その日のうちに自分の夫を殺」すことになります。
#9/18に一部訂正しました。
Q10.ある国では人々は生まれてくる子には男の子だけを欲しがりました。そのため、どの家族も男の子を産むまで子供を作り続けました。この国では男の子と女の子の人口比率はどうなりますか?
#ishidaさんの解答、ゲストさんの解答および通りすがり19さんの解答より。元の解答も誤りではないので、削除はしませんが・・・。
次の子どもを作るか作らないかの判断にどのような条件を設定しようとも、作ると判断した結果産まれてくる子どもの男女比に対しては、その条件は何ら影響を及ぼさないので、自然体での男女比と何ら変わりはありません。(9/18追記)
#もうちょっとエレガントな証明があると思いますが、枠組みは間違っていないはずなので、とりあえず再掲します。
自然体で女の子が産まれる可能性をp(0<p<1)とすると、
- 1人目で男の子が産まれる可能性は1−p
- 1人女の子が産まれた後に2人目で男の子が産まれて男の子1人・女の子1人となる可能性はp×(1−p)
- 2人女の子が産まれた後に3人目で男の子が産まれて男の子1人・女の子2人となる可能性はp^2×(1−p)
- n−1人女の子が産まれた後にn人目で男の子が産まれて男の子1人・女の子n−1人となる可能性はp^(n−1)×(1−p)
これを言い換えれば、
- 子どもが1人だけの場合、男の子1人で、その確率は1−p
- 子どもが2人だけの場合、男の子1人・女の子1人で、その確率はp×(1−p)
- 子どもが3人だけの場合、男の子1人・女の子2人で、その確率はp^2×(1−p)
- 子どもがn人だけの場合、男の子1人・女の子n−1人で、その確率はp^(n−1)×(1−p)
以後同様に考え、この国での男女比は、
- 男の子の出生数/女の子の出生数=(1−p)+p×(1−p)+p^2×(1−p)+・・・+p^(n−1)×(1−p)+・・・/p×(1−p)+2×{p^2×(1−p)}+・・・+(n−1)×{p^(n−1)×(1−p)}+・・・
分子を(1−p)で、分母をpくくると、
- 男の子の出生数/女の子の出生数=(1−p)×{1+p+p^2+・・・+p^(n−1)+・・・}/p×[1−p+2×p×(1−p)+・・・+(n−1)×{p^(n−2)×(1−p)}+・・・]
ここで、分母中の大括弧の中身を考え、子どもの数がn人の場合について展開すると、
- n×p^(n−2)−n×p×p^(n−2)−p^(n−2)+p×p^(n−2)
- =n×p^(n−2)−n×p^(n−1)−p^(n−2)+p^(n−1)
- =p^(n−2)×(n−1)−p^(n−1)×(n−1)
となり、これにn−1人の場合の、
- p^(n−3)×(n−2)−p^(n−2)×(n−2)
とn+1人の場合の、
を加えたとき、n人の場合のp^(n−2)についてはn−1人のそれとの合算でp^(n−2)だけが残り(p^(n−2)×(n−1)−p^(n−2)×(n−2)=p^(n−2))、p^(n−1)についてはn+1人との合算でp^(n−1)だけが残り(p^(n−1)×n−p^(n−1)×(n−1)=p^(n−1))、これをすべてのnについて行えば、結局のところ分子の中括弧の中身と同様に、1+p+p^2+・・・+p^(n−1)+・・・といった数列となるので、約分可能。したがって、
であり、自然体と変わらない男の子と女の子の人口比率となります。
Q11.高速道路で30分間に自動車が存在する確率が0.95である場合、10分間では確率はどれぐらいになりますか?(確率は一定であると仮定します)
#昨日の再掲です。
30分間に自動車が存在する確率が0.95ということは、それを構成する3回の10分間のすべてに自動車が存在しなかった確率が0.05ということになるので、10分間に自動車が存在しない確率は0.05の三乗根。よって、10分間に自動車が存在する確率は1−0.05の三乗根。
#電卓で適当に近似すると、約0.6315となります(0.05の三乗根が約0.3685)。
Q12.時計を見ると3時15分でした。長針と短針の間の角度は?(ゼロではありません)
#昨日の再掲です。
短針は1時間に360/12=30度進むので、その1/4である15分間には7.5度進みます。3時15分には長針は3時に短針が存在していた場所にあるので、長針と短針のなす角は7.5度。
Q13.4人の人々がぐらぐらするロープの吊り橋を渡って夜にキャンプへ戻る必要があります。不幸にも懐中電灯は一つしかなく、17分しか使えません。吊り橋は懐中電灯なしで渡るにはあまりにも危険で、吊り橋は同時に2人しか渡れません。しかも、各人は歩くスピードが違います。ある者は橋を渡るために1分かかり、別の者は2分かかり、3番目の者は5分かかり、最後の者は10分かかります。どのようにすれば17分で全員が渡りきることができますか?
#昨日の再掲です。
- 1分と2分が行って2分
- 1分が戻って1分で計3分
- 5分と10分が行って10分で計13分
- 2分が戻って2分で計15分
- 1分と2分が行って2分で計17分
Q14.あなたは友人たちなどとパーティをしており、全員であなたを含めて10人います。友人の一人が賭を提案してきました。あなたと同じ誕生日の人がこの中にいればあなたは1ドルもらえます。あなたと同じ誕生日の人がいない場合には友人が2ドルもらいます。あなたはこの賭を受け入れますか?
- ある友人が私と同じ誕生日でない確率は364/365=0.997。
- 私以外の9人全員が私と同じ誕生日でない確率は0.997^9=0.976。
- 賭けの期待値は1×(1−0.976)−2×0.976<0なので、受け容れない。
#昨日の再掲ですが、単純に考えても簡単すぎるようでもあり、誕生日=月は問わないとすれば、次のようになります。
- ある友人が私と同じ誕生日でない確率は30/31=0.97
- 私以外の9人全員が私と同じ誕生日でない確率は0.97^9=0.74
- 賭の期待値は1×(1−0.74)−2×0.74<0なので、受け容れない。
Q15.全世界でピアノの調律師は何人いますか?
これもQ1同様フェルミ推定といいますか、エンリコ・フェルミはシカゴにピアノの調律師は何人いますかと出題したそうで、よりオリジナルに近いものです。
この問題の場合、
- 世界中のピアノの台数×1台当たり年間調律頻度/調律師1人当たり年間調律数=調律師数
という式が考えられます。
世界中でのピアノの販売規模は年間51万台ですが、ストック/フロー比率が全世界で日本と同じだとすれば、日本では1,000万台/5万台とのことなので、世界中のピアノ台数は約1億万台となります。ストックのうち休眠比率がこれまた日本と同じだとすれば、約7割が休眠ということとなり、7,000万台は調律されないとし、日頃から使われている3,000万台は平均年2回だとすれば、全体を平均した1台当たり年間調律頻度は0.6回ということになります。
調律師1人当たり年間調律数については、ある経験豊富な調律師の方は30年間で2万数千台を調律されたとのこと、単純に計算すれば年700台〜900台ということになりますが、それほどお呼びがかからない調律師の方もいらっしゃるでしょうから、平均すれば年500台と仮定します。
以上から、
#シカゴの場合は100〜200人が妥当な推計とされる(Q1のリンク先をご覧ください)ようですが、人口300万(から推計される世帯数・世帯当たりピアノ台数)を前提とするので、単純計算でいえば世界人口66億に対してはその2,200倍、すなわち22万人〜44万人となります。世界平均がシカゴ並みとは考えづらいので、世界平均がシカゴ平均の1/2〜1/4になるとの上記解答は、だいたい同一線上のものといえるでしょう。
Q16.あなたは同じサイズのボールを8つもっています。そのうち7つは同じ重さですが、1つはほかのものよりもわずかに重いです。秤を2回だけ使ってこのわずかに重いボールを見つけるにはどうすればいいですか?
#昨日の再掲です。
- 任意の3個ずつを秤で比べる。
- 1.の結果、いずれかの皿が重ければ、その3つのうち任意の2つを秤で比べ、
- どちらかが重ければ、それが「わずかに重いボール」。
- 等しければ、比べなかった残る1つが「わずかに重いボール」。
- 1.の結果、それら3個ずつが等しければ、残る2つを比べ、重い方が「わずかに重いボール」。
Q17.5人の海賊がいて、彼らは1位から5位にまでランク分けされています。1位の海賊は100枚の金貨をどのように分けるかというプランを提案する権利があります。残りの海賊はこのプランに投票する権利があり、賛成が半分に満たない場合には1位の海賊は殺されます。1位の海賊の分け前を最大にしてなおかつ彼が生き残るにはどうすればいいですか?(ヒント:一人の海賊は結局、金貨の98%で終わる)
tockriさんのエントリおよび昨日のエントリにいただいたguestさんの解答より。
- 残り人数が2人になってしまったら、4位:5位の分け前提案を0:100にしない限り、5位の投票によって4位は殺される。
- 残り人数が3人になった時、3位:4位:5位の分け前提案を100:0:0にしても4位は賛成して可決される。(どうせ反対しても0か死しか残らないので)
- 残り人数が4人になった時、2位:3位:4位:5位の分け前提案を98:0:1:1にすると4位と5位は賛成して可決される。(4位と5位は残り3人になったら0枚になってしまうので)
- したがって、残り人数が5人の時、1位:2位:3位:4位:5位の分け前提案を98:0:0:1:1にすると4位と5位が賛成する(反対して4人になっても変わらないので)ので、この提案で98枚を受け取って生き延びることができます。
#設問の「98%」要件を満たすのはこちらですので、webmasterの解答ではなくこちらが正解となるわけですが、どちらでも一緒だから賛成してくれるというのは反対される可能性もあるわけで、確実に生き残るならばやっぱり昨日のように97枚だよなぁ、とは負け惜しみ。
#オリジナルの問題では提案者にも投票権があるのだとの通りすがりさんの情報に基づけば、次のとおりとなります。
- 残り人数が2人になってしまったら、4位は自分の賛成票で必ず自分の提案を可決できるので、4位:5位を100:0とする。
- 残り人数が3人になった時、3位:4位:5位の分け前提案を99:0:1にすると3位と5位が賛成して可決される。(5位は残り2人になったら0枚になってしまうので)
- 残り人数が4人になった時、2位:3位:4位:5位の分け前提案を99:0:1:0にすると2位と4位が賛成して可決される。(4位は残り3人になったら0枚になってしまうので)
- したがって、残り人数が5人の時、1位:2位:3位:4位:5位の分け前提案を98:0:1:0:1にすると4位と5位が賛成する(3位・5位は残り4人になったら0枚になってしまう)ので、この提案で98枚を受け取って生き延びることができます。