Google面接問題の模範解答の追求
昨日は独力ですべてやってみましたが、検索やらいただいたコメントやら、総力を挙げて模範解答を考えてみました。なお、昨日とは異なり、問題は日本語訳のみ掲載します。原文にご関心の方は、昨日のエントリをごらんいただければ。
＃以後、より正しそうな解答を見つけたり教えていただいたりした場合には、随時訂正していきます。
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円／平方メートルあたりが大規模清掃の場合の相場のようなので、
- 1,347万×150≒20億円
＃上記のような計数が面接の場ですらすら出てくるはずもないので、実際にはシアトルの人口等からある程度の推測をする、ということなのでしょう。（住居よりも）オフィス関係の窓ガラス量の推計が難関ですが、シアトルの都市圏人口は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人の場合の、
- p＾（n−1）×n−p＾n×n
を加えたとき、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）＋・・・といった数列となるので、約分可能。したがって、
- 男の子の出生数／女の子の出生数＝（1−p）／p
であり、自然体と変わらない男の子と女の子の人口比率となります。
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台と仮定します。
以上から、
- 1億台×0.6／500＝12万人
＃シカゴの場合は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枚を受け取って生き延びることができます。
9月 11th, 2007 at 7:37:05
Q.8 の回答、すごくエレガントです(何処かで聞いたことのある理論のような気がしますが、正解を読んでも、腑に落ちるのにかなり時間がかかりました。)が、仮に自分が妻の立場だったとして、このロジックに気づいていても、自分以外の妻99人が、このロジックによる検証を経て、99日目に夫を殺さなかったのだと、確信出来ない限り自分の夫が浮気していた、と「知った」ことにならないですよね。
今の回答案を披露した上で、でも、こんな、複雑なロジックに全員が気づくと信じるのって、無理があるので、やっぱり何も起きない、ってのが正解なんじゃないでしょうか？
(コンピューターが、常に正常に動くって仮定して、システム組んではいけないよね！みたいなノリで。)
各妻の、夫の浮気検証課程(特に99日目)で、どれくらい他の妻のインテリジェンスの信頼性を要求する理論なのか、さっぱり判らないのですが。 その辺の、ロジックの安定性(と言うのでしょうか)に関する議論みたいなものが、評価の分かれ目なのでしょうか？ ひねくれすぎでしょうか？
Q10は、次に産まれる赤ちゃんの性別は、姉が何人いるかの影響を受けない話(independent)なので、自然体と変わらない男女比になる。 では、駄目なのでしょうか？
9月 11th, 2007 at 8:11:41
>スタックの伸張を見る問題
題意がいまいちつかめないのですけど。
デバッガが使えるならプログラムの適当な場所で止めてそのときのスタックポインタを見る。
最大どれぐらい使われるかを調べるのであれば、事前にスタック領域を特殊な数値(例えば0xBADFACE,xC0FFEE,0xDEADBEEFなど)で埋めておき、プログラム終了時にそれが書き変わっている部分を調べればいい。
9月 11th, 2007 at 12:56:10
Q4 多くのプログラミング言語(たとえばC言語)では，ある関数に局所的なデータ(変数)はスタック上に置かれ，関数呼び出しのたびにスタックが伸びて新たな領域を確保します．このとき，スタックがどちらに伸びるか(メモリ上の番地が増える方向か，減る方向か)をどうやって知るか，という問題かと．
C言語では，スタック中のデータ(変数)領域の番地を取り出すことが出来ますので，関数Aから関数Bを呼び出し，Aに局所的なデータの番地とBのデータの番地の大小を比較すれば良い，というのが素直な答だと思います．厳密には，C言語の規格では，このような比較の結果は未定義ですが，多くの計算機環境ではうまく結果が得られるでしょう．
Q10 これから子供を作る家族が，最終的に持つ男の子の数の期待値をQと置きます．
最初の子が男の子(確率1-p)なら，そこで子作りは終了．
最初の子が女の子であった場合(確率p)には，今後の男の子の数の期待値はQのままですから，
Q = (1-p) + pQ
と書け，整理するとQ = 1となります．
同様に，これから子供を作る家族が最終的に持つ女の子の数の期待値をRと置くと，
R = p + pR
と書け，R = p / (1 - p) となります．
したがって，男女比 Q : R = 1 : p/(1-p) = 1 - p : p
9月 11th, 2007 at 14:54:39
>Q = (1-p) + pQ
>R = p + pR
それぞれ、
Q = (1-p)・1 + p・Q (人)
R = (1-p)・0 + p・(1+R) (人)
と書いた方がわかりやすかったですね。
9月 11th, 2007 at 16:05:41
スクールバス
最後の１個のボールをどのようにして入れるか？ がわかりません。窓からだと上の方にムダな空間ができるでしょうし、バスの天井に穴をあけるのかな。
9月 11th, 2007 at 18:35:17
通りすがりさん
最後の1個はたぶん排気マフラーです。
いやそういうことでなく
lukeさん
C言語でいうところのスタック領域のサイズはスレッド実行中に増えたり減ったりしないので、スタックが「増える」「減る」というのは関数呼び出しとか変数の宣言や受け渡しによってスタックに積まれているデータ数が増減することを指していると思います。
通常スタック領域はメモリ番地の後ろから使われるそうですので
http://mikata.curiocube.com/hello/ch08_callstack.html
局所変数のメモリ番地が小さいほどスタックの上の方に積まれていることになりますが、この問題は任意のプログラム実行中にスタック内のデータが増減することをどうやって知るか、ということではないかと思います。
他のプロセスにアタッチしてメモリダンプをとるアプリケーションで見たメモリイメージのプログラム領域とスタック領域を勘で特定して、スタック領域が変化しているところを見ればわかるかなあ。（もちろん人力で見るんじゃなくてそういうプログラムを作って。）
9月 11th, 2007 at 20:29:06
Q8はまだ少し不十分な気がします。問題から各夫人は浮気ものが99人以上いることを知っている訳ですから、なぜ浮気ものが1人の場合を考えなければいけないか説明する必要が有ると思います。
つまり、浮気もの100人の場合を考えるためには99人の場合を考えなければ鳴らず、そのためには98人の場合を考え…と言うふうにして１人の場合まで持っていく方法を説明しなければいけないと思います。
Q17は半数に満たない場合否決なので、賛成が半数つまり賛成1、反対1の場合は可決ではないでしょうか。
この場合
2人:100,0
3人:99,0,1
4人：99,0,1,0
5人：98,0,1,0,1
になると思います。
Q14は期待値はその通りなのですが、パーティーを盛り上げるため賭けを受けるが正解です。(^_^)
9月 11th, 2007 at 23:02:02
面白いですね。私も直感で出来るものだけ参加ということで。
Ｑ７ 特にＢ地点を知らないという条件は無いので、行かなければならないのですから「Ｂ地点に行く。」、ちょっとひねると今現在Ａ地点にいるとう条件も無いので「Ａ地点に行き、引き続きＢ地点に行く。」だと思います。
Ｑ７ 戸棚が一杯のままでは探しづらいので、「戸棚以外のスペースも使って整理する。」という内容があればよいかと思います。
Ｑ８ 「その日のうちに男性が全員逃げ出す。」
Ｑ１０ １の出産における女子の出産の確立がＰであれば、後は同様の確立の積み重ねになるので、他の条件は考慮する必要が無いと思われます。よって答えは「変わらない。」
Ｑ１４ 同じ誕生日の人がいない場合の２ドルについて、自分が払うという条件が無いので、「賭けを受ける。」が正解かと思います。
原文を間違えて解釈していたらすみません。
9月 12th, 2007 at 8:33:52
＞獏さん
Q8は、10日のエントリへのコメントで望月さんがお示しのように、ロバート・オーマン（ノーベル経済学賞受賞者）が考案した設問とのことです。実は私も、望月さんのコメントをきちんと理解するのに時間がかかってしまいました（笑）。
Q10は、お示しのものでよいのかどうか私にはわからないのですが、私がポイントだと思ったのは、男の子は夫婦一組につき1人しか産まれないのに、女の子は複数産まれ得ることです。男の子である確率が55％であるとして、55％は男の子の一人っ子、30％は男の子1人・女の子1人ですが、17％は男の子1人・女の子2人・・・0.25％は男の子1人・女の子9人・・・0.00064％は男の子1人・女の子19人、といった具合に、どんどん確率は低くなるものの、女の子の数はどんどん増えていくわけです。この確率の低下と女の子の数の増加が釣り合っている、ということと理解しています。
＞cloudyさん
おっしゃっていることがちんぷんかんぷんなのはご容赦くださいm(_ _)m
＞lukeさん
Q4につきましては、おっしゃっていることがちんぷんかんぷんなのはご容赦くださいm(_ _)m
Q10については、ありがとうございました。修正いたします。
＞通りすがりさん
穴を開けても隅々までは難しいでしょうから、いっそのこと天井を切り開いてしまって、後で溶接するとか（笑）。
＞ぬ゛さん
Q17については、2人の場合は第1位（5人のときの第4位）には投票権がありませんので。
＞ishidaさん
Q14、思いつきませんでした。
9月 12th, 2007 at 9:34:54
webmasterには、またちんぷんかんぷんな話で申し訳ありません。
＞tockriさん
Intel x86やM68X00などのプロセッサは、プッシュするたびにスタックポインタが減るアーキテクチャですので、おっしゃるとおりスタック領域がメモリ空間の上端に置かれるのが普通です。しかし、逆にプッシュするとスタックポインタが増えるアーキテクチャもあります。また、RISCプロセッサではプッシュ・ポップに相当する命令がなく、コンパイラがどちらにするか選ぶことができますが、HPのPA-RISCなどでは「プッシュするとスタックポインタが増える」慣習を用いていたそうです。
スタックオーバーフローしないようにチェックしたい時（たとえばインタプリタをＣで書くときなど）、このスタックポインタの増減方向を知る必要があります。#defineで静的に与える処理系（rubyなど）もありますが、たとえばCLISPやGNU Common Lispは実行の開始時に自動判定しています。
原文の”How would you find out if a machine’s stack grows up or down in memory?”というのは、この自動判定の方法を尋ねているものだと思います。
9月 12th, 2007 at 9:37:30
あ、今調べたら、rubyはconfigure時にstack_growup_pという関数を使って定数STACK_GROW_DIRECTIONを自動判定しています。
9月 12th, 2007 at 10:58:15
Ｑ７（あれっＱ７が２つある罠）
正５角形ＡＣＤＢＥを考え、辺ＢＥが切れているものとします。
Ａ地点にいるとき、Ｂ地点は知らないけれどＢ地点に近いものとしては点Ｅをおしえてもらうことになって、そこで行き止まりになってしまいます。
したがって２、行き方を知らない場合、A地点よりもB地点に近い場所を教えて欲しい、だけでは足りません。
これはワールドワイドウェブの原理ですね。
Ａ地点において、Ｂ地点を知っている人を探すのではなく、先ほどの正５角形の例でいうと、
１、地点Ａから見える地点Ｃと地点Ｅにいる人に、Ｂ地点は見えるか？ 見えなかったらＡ以外の他の点は見えるか？ と聞く。
２、Ｃ：地点Ｂは見えないけれど、地点Ｄが見える
Ｅ：地点Ａ以外には見えない、という返事が返ってくる。
３、Ｃさんに対し、地点Ｄにいる人に、Ｂ地点は見えるか？ 見えなかったらＣ以外の他の点は見えるか？ を聞いてもらう。
４、Ｄ：地点Ｂが見えたよ。
５、Ｃ：Ｄさんが見えたと言ってるよ。
６、Ａ→Ｃ→Ｄ→Ｂと移動。
距離が長くなっても、３４５を準じ繰り返します。
地点Ｂへの道筋がわからない間は移動しないのがミソです。
9月 12th, 2007 at 11:07:23
はじめまして、論理的に考えられていて非常に面白かったです
ところでQ8.に関してですが
「自分の夫でない男が浮気するとすぐにそれを知ることが出来ますが」
というのは
浮気はわかるが誰かは判らないのか、その人名まで判るのかが大きな違いになると思います。
[人名がわかる場合]
女王が名前を明かすと明かされた妻は夫を殺さなくてはいけません。
しかし前提条件から男は全員浮気をしており、女達は夫以外の99人の浮気を知っていますから自分の夫もしているだろうと疑いつつ、女達は夫を殺したくないので誰も密告しあっていない均衡状態です。
名前を知ってしまった女は夫を殺したくなかったのだから復讐に女王の夫(王)の浮気を女王に伝え、女王は王を殺そうとするでしょう。
以上のことが予想されるので王は直ちに女王を捕まえ処刑します。
[人名がわからない場合]
女達は誰かは判らないが他の浮気の存在を知っています。
(浮気されるたびに判りますが同一人物が複数回浮気をしている可能性もあるので全員かどうかはわかりません)
あくまで「自分の夫が浮気していることがわかった」場合だけ殺さなくてはいけないので
次の日になっても「ああ誰か自分の夫の浮気を判っていない人がいるな」で終わります。
(他の人の浮気は感知していますから女王はそのことを言っているのだなと思うでしょう)
以上の結果になると思いますがどうでしょうか？
9月 12th, 2007 at 13:30:12
Google面接試験、Q17の正しい回答…
■Googleの面接試験、一体どのような質問をされるのか？
http://gigazine.net/index.php?/news/comments/20070909 (more…)
9月 12th, 2007 at 14:07:17
Q17の正しい回答は
９８：１：０：１：０
です。考え方は↓
残り人数が二人になった時は、投票権があるのが５位一人だけなので
０：１００
以外のどの提案でも４位死亡。よって
？：？：？：１：０
残り３人の時は
９９：１：０
で成立するので、３位は９８以下の何枚を提示してもyesとは言わない。よって
？：？：０：１：０
２位は自分の時に
０：９９：１：０
にしなければ確実に死ぬので一枚以上なら何枚でもyesという
よって答えは
「９８：１：０：１：０」
となります。
9月 12th, 2007 at 15:27:55
浮気の問題
２組だけの簡単なモデルで考えます。
Ａ夫人：Ｂ氏は浮気をしている。でも夫Ａは大丈夫、
Ｂ夫人：Ａ氏は浮気をしている。でも夫Ｂは大丈夫。
で、何もおきない。
翌日
Ａ夫人：Ｂ氏は浮気をしている（相手が自分なので確実に知っている。女王様もＢ氏のことを指している）のに、Ｂ夫人は夫を殺さなかった。ということは、Ｂ夫人は浮気者をＡ氏だと思っているんだわ。失礼しちゃう。えっ、何ですって。２人しかいないんだから、思っているんじゃなくて、じっさいに浮気したんじゃないの。
（Ａ夫人、Ａ氏を殺める）
Ｂ夫人：Ａ氏は浮気をしている（相手が自分なので確実に知っている。女王様もＡ氏のことを指している）、昨日は気づかなかったみたいだけれど、今日は気づいてＡ夫人はＡ氏を殺したわ。やっぱり、浮気者はＡ氏で、うちのひとは大丈夫だわ。
9月 12th, 2007 at 16:44:20
Q17
半数に「満たなければ」殺されるなら、半数（1：1や2：2）では殺されない（「過半数」ではなく「未満」だから）ので、5位には通常なら絶対に金貨は渡らない。
（つまり、1枚でも金貨が分けられる時点で5位は賛成する。）
また、4人になった時点で2：2で半数になって、「1位（元2位）99：それ以外の3人の中で一人に1」という形で決着が付くので、その時点での2位（5人の時点での3位）以下の者はどちらにしても1枚以上の金貨を得る見込みはない。
よって、5人の時点で、1位98：2位0：3位0：4位1：5位1となれば、どちらにしても1枚しか得る見込みのない4・5位のものは賛成をせざるを得ない。
（3位に一枚でも同じ。）
ただし、この場合、そんなことは先刻お見通しの2位が「1位に反対票を入れてくれれば俺の計画でお前に有利に配分するぜ」と1位以外の全員と個別に裏取引をする可能性があるので（海賊だから）、それを防いで「安全に」金貨を手に入れる為には、「1位34：2位0：3位0：4位33：5位33」とせざるを得ない。
他の者の可能性を考えると、
・2位
1位が死ねば、「元2位50：それ以外の誰か一人に50：他0」で決着が付き、その「誰か」を決めるのが2位であるからには、2位は人事権をフルに活用して3人を対立させ、安全かつ安定して最低50枚を手に入れる事ができる。
（残る3人に分け前のダンピング合戦をさせれば50枚以上手に入れられるが、土壇場で裏切られる事を考えると5位と50枚づつ山分けするのが無難。）
・3位
同じような働きかけで2位を殺せれば、5位と山分けで50枚を手に入れる事ができる。
（4位が納得すれば4位と山分けでも良いが、4位はうまくすると総取りが可能な立場なので、土壇場で裏切る可能性があるから、自分の立場を危険にさらさない5位との同盟を選ぶだろう。）
・4位
3位を殺せれば100：0で総取りできるが、5位はそれを知っているので無理。2位の潜在的同盟者で、5位のライバルといえる。
・5位
通常なら1枚も手に入れられない。2位か3位と組むことによって50枚を手に入れられ、4位以外の者が手を差し伸べてくる可能性が高い。
残りの4人の中では2位の立場がぬきんでて強いので、1位がそれを説明して4位・5位は安定して金貨を入手する事が難しい事を理解させれば、33枚という50枚よりは少ない枚数でも妥協が成り立つ可能性が高い。
つまり
・力関係
1>2>3>4>5
・安全に金貨を手に入れる可能性
2>1>5>3>4
となる。
（1位は自分を含めて最低3人に分配しなくてはならないので2位に劣る。5位は1位〜3位まで自由に組めるから優位。4位は総取りを警戒されるので最下位。）
9月 12th, 2007 at 18:26:21
Ｑ８の浮気者の村の問題ですが
前のエントリでも単純化した２組の村から想定して
解説されてる方がいらっしゃいましたが、
２組の場合はお互いの妻が
「相手は村内の浮気者を０と認識しているだろう」
と推測している状態だから
「村内の浮気者が１人以上いる」という
「共有情報の確定」が変化をもたらす訳です。
これが３組だと各妻は「自分は２人の浮気者を
認識しているが自分以外の夫婦は１人の浮気者
しか認識していないだろう」と推測している
状態になり、「浮気者は２人以上」という共有情報
の確定でなければ変化をもたらせません。
よって１００組の村なら各妻は
「自分は９９人の浮気者を認識しているが他の妻
は９８人の浮気者を認識しているだろう」と
推測している状態になり、女王は
「９９人以上の浮気者がいる」と宣言しなければ
何の変化も起こせないことになります。
つまり、最初の「何も起きない」で正しいのでは？
9月 12th, 2007 at 19:07:11
Q17について
私は「設問を友人から聞き取った際のミス」を支持します。
http://www.nishiohirokazu.org/blog/2007/09/google.html
原案では「提案者も含めて投票できる」となっているようです。
不確定要素のある設問で良しとするとは思えませんし、98%とという数字を間違うとは思いにくいので。
よって
「98,0,1,0,1」
9月 12th, 2007 at 20:38:05
翻訳についていくつか：
Q11 “observing a car”「車を見かける」だと思います。答は合ってるように思います。
Q14 「同じ誕生日の人１人につき１ドルずつ」「違う誕生日の人１人につき２ドルずつ」だと思います。これだとさらにわかりきった問題になってしまって、何か見落としがあるのかもしれませんが。
9月 12th, 2007 at 20:54:19
Q14の出所は、Googleの面接を受けて「時給契約でどう？」と言われて断ったという人：
http://www.shmula.com/31/my-interview-job-offer-from-go...
のようですが、どうも問題を間違えて記憶していた可能性が高いです。
9月 12th, 2007 at 21:08:09
コメントを読み直していたら、以前にも「通りすがり」さんがいらっしゃったのを発見してしまいました。
別の者です。
不注意で大変申し訳ございません。
再レスついでに少しコメントを。
女王ですが、何度考え直しても「Ｑ８ですが 」さんと同じ見解になってしまいます。2組に対する「1人」は100組に対して「99人」でなければ同等の結果となりません。
「何もおきない」では設問としてなりたたなすぎるので、境界条件に見落としがあると思っているのですが、どなたかご指摘いただけないでしょうか(笑)
しかし、以前のコメントにもありましたが、フェルミ推定系と、「○○の定理(問題)」のように、その問題に対する知識から境界条件を補えば答えが一つになるものと、問題解決への姿勢を問うものが混在していますね。
海賊や女王の設問は文章の言葉尻をひろってしまうと、解答の幅が広がってしまうので、求められているだろう落とし所を見つけなければいけませんし。
9月 12th, 2007 at 21:16:09
> luke 様
「本来の設問を模索する会」になりつつありますね・・・
> webmaster 様
この件について色々見ていた所、「googleで検索！」等の非論理的な解答や、言葉尻をつついて解答しているものが多くみられたのですが、こちらではみなさんが論理的にアプローチしようとしてらしたので、少々うれしくなってしまいました。
9月 12th, 2007 at 21:21:26
Q10についてですけど、
１回の出産の機会で生まれる新生児の性別の比率は変わらないので、
人口の男女比も変わらない
でいいのでは？
9月 13th, 2007 at 6:51:51
Q10についてですが、
直感的な理解として
女児が生まれる確率をp (0
9月 13th, 2007 at 6:53:07
＞lukeさん
よくわからないのですが（笑）、答えは
「当該システムにおけるスタックポインタの増減方向を確認した上で、その増減をチェックする。」
ということでいいのでしょうか?
Q14、実際のところどうなんでしょうかねぇ。
＞通りすがりさん
お察しのとおりインターネット上でのパケットの扱いからの連想ですが、ルーティングテーブルとしては「近い」だけではダメだ、ということですね。
浮気問題も同じ方という前提でお応えしますと、設問上はAとBの同時手順が前提となっているのでしょうけれど、実際にはまったく同時ということはあり得ず、おっしゃるようになってしまう可能性は出てきますね。しかし、夫殺しが他にばれるまで一定の時間がかかるとのこれまた現実的設定を加えると、そのタイムラグの間に他の家庭でも夫殺しが行われる＝事実上の同時手順、ということになるのかなとは思います。
＞mastacosさん
女王は「少なくとも1人が浮気している」と言うのみで、名前は言わないという設問と理解しています。
＞飛鳥さん
第2位は自分の時に自分の取り分として最大97:0:2:1で生きていられますよね?
＞ゲストさん
その手の交渉まで考え出すと・・・それはそれで高い評価が受けられるのかも（笑）。
＞Ｑ８ですがさん
前日のエントリへのmastacosさんのコメントへのお応えで詳しく書きましたが、3人の場合に自分以外の2人は1人の浮気しか認識していないとすれば、自分以外の2人は2日後に夫を殺すことになるので、そうでない＝自分の夫も浮気している、ということになるのではないでしょうか。
＞通りすがりさん（18です。さんですが、spamフィルタからひとつ復活させたので19番になっております。）
情報提供ありがとうございました。提案者も投票できるとなると、まったく違った話となってしまいますね。
浮気問題については、Ｑ８ですがさんへのお応えをご覧ください。
＞ゲストさん
言われてみますとそれでいいような気がするのですが、ちょっと自信がもてなかったりします。というのもたとえば、エントリの証明は子どもの数に上限が無いことが前提になっていますが、仮に上限を設けると、男子の比率が高まってしまいます（端的には、2人までしか産めない場合をお考えいただければと存じます）。でも、子どもの数に上限があったところで、「1回の出産の機会で生まれる新生児の性別の比率は変わらない」わけで、となれば同じことが妥当するのに男女比が変わってくる事例を示すことができてしまうように思えるのですが・・・。
9月 13th, 2007 at 7:01:50
すみません、切れてしまいました
女児が生まれる確率をp (0
9月 13th, 2007 at 7:44:46
webmaster 様
Ｑ１０で「上限を設ければ‥‥」とのことですが、失礼ながら上限まで女子が続き結局男子を持てない可能性を失念されていませんでしょうか。
9月 13th, 2007 at 7:52:56
>よくわからないのですが（笑）、答えは
>「当該システムにおけるスタックポインタの増減方向を確認した上で、その増減をチェックする。」
>ということでいいのでしょうか?
確認・チェックする方法を問うているので、より具体的な答がいるでしょう。
「関数Ａの局所変数へのポインタaを関数Ｂに渡し、関数Ｂの局所変数へのポインタbとの大小を比較する。
a b ならスタックは減る(grow downする)。
ただし、関数Ｂがインライン展開されないようにする（たとえば、Ｂを再帰的関数にする）必要がある。」
9月 13th, 2007 at 17:13:00
5=12=16の通りすがりです。
浮気問題。
その翌日。
Ａ夫人：Ｂ氏は浮気をしているのに、Ｂ夫人は夫を殺さなかった。ということは、彼女は、夫Ａを浮気者だと思っているし、じっさいしちゃったんだと思って、私は夫を殺したのに、なぜ未だにＢ夫人はＢ氏を殺さないのかしら。
Ｂ夫人：Ａ氏は浮気をしている（相手が自分なので確実に知っている。女王様もＡ氏のことを指している）、一昨日は気づかなかったみたいだけれど、昨日は気づいてＡ夫人はＡ氏を殺したわ。やっぱり、浮気者はＡ氏で、うちのひとは大丈夫だわ。でも、なんで、一昨日は気づかなかったのかしら。そうだわ。一昨日は、Ａ夫人は、うちの夫Ｂが浮気者だと思っていたんだわ。えっ何ですって。Ｂは誰と浮気するのよ。ここには、私とＡ夫人しか女はいないのに。そうか、夫ＢはＡ夫人とできていたのね。
（Ｂ夫人、Ｂ氏をつかまえる）
Ｂ夫人：あなた、Ａ夫人と浮気したでしょ。
Ｂ氏： しらない。
Ｂ夫人：でも、（これまで考えてたことをはなす）。
Ｂ氏：それはぜんぜん違う。でも、浮気をしたのは事実だ。実はＡ氏と。。。。ごめん。掟通り、君に殺されることにするよ。
9月 13th, 2007 at 17:24:02
連投です。
ゴルフボール詰込み問題。
ゴルフボールが十分に固く、バスの鉄板がそれなりに柔らかいとすると、ゴルフボールを詰めこむにつれ、バスは変形していき（ガラス素材部分は、あえて無視します）、球体にちかづくでしょう。そうなると、詰め込まれているボールはもっと多くなるのでは。また、鉄板部分がもっと十分柔らかければ、どんどん伸びていき、無限のボールがはいることになるのではないでしょうか。
ゴルフボールでなく水とか気体でも、詰め込むと当初容積よりいくらかは大きくなるわけです。でも、ガスをいれると、バスガス爆発してしまいます。
9月 13th, 2007 at 18:04:28
・浮気の村の件
解説ありがとうございます。理解しました。
３人でシミュレートしていたのに思い至れないとは・・・
完全に思考能力不足ですね・・・お手数おかけしました。
・男女産み分け
これは、最終的には数学的証明が必要とは思うのですが、感覚的(言葉が不適切か)な理解とすると、回数を限定して考えても同じ結論が導けます。
(私は最初ここから検証しました)
以下男(1)女(0)は等確率と仮定しておきます
[試行回数2回]
11
10
01
00
のパターンが等確率で発生するとして、設問の条件をあてはめると
1
1
01
が有効なパターンとなり、男が多くなりそうですが、実際は生む回数の制限がないので、すべてが女のパターンはいつか必ず男が生まれるため漸近的に100%有効と考えると、
1
1
01
00
で、男女比はかわりません。
もしくは、すべて女のパターンは題意からはずれたものとして、無効と考えた場合にも、試行回数を増やしていくと、全体におけるすべて女となるパターンがしめる割合は漸近的に0に近づきます。
[試行回数3回]
111
110
101
100
011
010
001
000
この場合、
1
1
1
1
01
01
001
000
となり、男女は同じ人数となります。
もしくはすべて女のパターンを抜くと男女比は
64%対36%
となり、
75%対25%
であった試行回数2回の場合よりも50%対50%に近づきます。
全く別の観点だと、一人でコインを投げ続けて、表が出たら1セット終了として、何セットも続けた場合に表が多くでるのかどうか、という問いと同等と思います。
たとえば10セット続けて結果を集計したとして、どんなルール付けあってもただひたすらコインを投げ続けているだけなので、神の手によって50%対50%に近づくだけです。
つまるところ試行(してしまったもの)をキャンセルできるルールや、試行結果を変更できるルールがない限り、本来の確率を人の手で操作する事ができないと。
googleの設問に対する解答としてはこの程度でもよいのかなと思いました。
9月 14th, 2007 at 3:27:34
浮気問題について先日のエントリの回答を拝見いたしましたが、つまり全ての妻が「村に浮気者がいないと認識している妻は存在し得ない」と認識することがトリガーとなって浮気者をあぶり出すという事ですね。
そうすると、村の規模にかかわらず３人目の浮気者が出た時点で、全ての妻が「村に浮気者がいないと認識している妻は存在し得ない」と認識することになりトリガーが引かれて浮気者があぶりだされ、浮気者は０に戻ってしまう・・・ひょっとすると３組以上の村において夫全員が浮気しているという状態は有り得ないというのが正解とか？
9月 14th, 2007 at 5:04:26
Q8の浮気夫婦村問題の正解は「今まで通りの生活が営まれる」だと思います。
村の女王が浮気者の存在を宣言する以前から、100人の妻は99人の浮気を知ることが可能でした。
ですから、まず村の女王の宣言が意味のあるものではありません。
また、女王の宣言に関わらず、99人の浮気を知ることができる100人の妻は、今までも自分の夫の浮気を疑っているでしょう。ここで気をつけなければいけないのは、「夫の浮気を確定すると、夫を殺さなければいけない」ということです。
村では男性全員がしてるような慣例的な行為に対し、殺害してまで罰を与えようとは思わないはずです。
加えて、「知ることができる」というのは「知らないこともできる」わけで、浮気の情報から耳を塞いで生活することも可能です。
100人の妻は、夫の浮気を感づきながら、知ることを避けて生活していると推測できます。
…と書いてて思ったのですが、問題文に「自分の夫が浮気してもわかりません。」とあるので、妻は夫の浮気を知ることができないじゃないですか！計算して夫の浮気を求めることを許容した場合、今までだって知ることが可能になってしまう…。
9月 14th, 2007 at 10:19:36
5=12=16=30=31の通りすがりです。（31は誰かツッコンでよ）
浮気問題。
一昨日からＤＴＤすら手につかずに断続的に考えていることは、
16は30でみたようにタイムラグを考慮しなくていいのですが、もし仮にその日のうちに１人の妻が暴発して夫殺しをした場合、この村に何がおきるか、ということです。その１人に全責任をなすりつけて、平穏無事でいられるのでしょうか？
9月 14th, 2007 at 10:36:54
5=12=16=30=31=35の通りすがりです。
地点問題
そもそもＢ地点への行き方を知らない人が、Ａ地点よりＢ地点に「近い」地点を認識できるでしょうか？ 「近い」という判断は、Ｂ地点への行き方を知っているからできるのではありませんか？
「Ａ地点よりもＢ地点に近い地点」ではなく、
「Ａ地点ではない地点を教えてもらう」ことで、いつかは（いつかは認識できないけれど）、Ｂ地点にたどりつきますね。
私の回答があっているという自信もないですけれど。識者の登場をおまちします。
9月 14th, 2007 at 19:15:25
Q9の浮気村(w)の答えは「何もおきない」でしょうね。もしくはこの設問の状態自体がありえないというのが解答になるかのどちらか。
もし「他人の浮気を知っていても口にしてはならない」のであれば、設問の前提条件から、100人の妻は自分の旦那以外の男99人の浮気を既に知っているので、全員が延々と「あいつの旦那は浮気してるのに、なんで殺さないんだ？」となるわけですね。何日たってもこの状態に変化はありません。
逆にもしも「お前の旦那は浮気している」と言うことができるのであれば、もっと話は簡単です。任意の2人が「私の旦那以外99人全員浮気している」といった時点で全員殺されます。もっとも、その前に次々殺されているでしょうけど。
もし女王が「99人浮気している」といえば話は変わります。
（女王自身が100人に含まれる場合）
女王が、自分の夫以外99人浮気しているというのだから、その時点で他の99人の妻は全員、自分の旦那の浮気を知ることができます。結果として女王の旦那は生き残るわけですね。浮気していても。
9月 14th, 2007 at 23:06:06
＞ishidaさん
いろいろ思い違いをしていたようです。おっしゃるとおりで間違いないように思います。週末に他の解答とあわせて手を入れます。ご指摘ありがとうございました。
＞lukeさん
ご教示ありがとうございました。ishidaさんにもお伝えしたように、週末にまとめて手を入れようと思っています。
＞通りすがりさん
アッー!
ゴルフボールは、バスの筐体が無限にのびることはないということで、延性についても仮定をおかなければならなくなりますね（笑）。
一人暴発した場合は、妻の間で浮気情報が流通しないという前提が変わらない以上、従来と同じということになるでしょう。
＞通りすがり19さん
おっしゃるとおりですね。恥ずかしい間違いをしてしまいました。
＞Ｑ８ですがさん
たとえば4人の村の事例を考えれば、他の3人の浮気に気づいているわけですから、当初から「村に浮気者がいないと認識している妻は存在し得ない」ということになりますが、その条件においても、次のとおり人数分の日数経過後に浮気がばれて夫は殺されることになります。
(1) 自分の夫が浮気していないとすれば、浮気しているのは3人のみ（仮にAa,Bb,Cc,Ddという夫婦を想定し、ここでの「自分」はAとします）、つまりbcdのみが浮気していて、BCDはそれぞれcd,bd,bcが浮気していることを知っている、ということになります（＝Aはそのように考えます）。
(2) この状態において、女王が誰か1人は浮気していると伝えます。
(3) Bにとって、浮気しているのがcdのみであるならば、Cはcを、Dはdを2日後に殺してしかるべき（bが浮気していない場合、Cはdの浮気のみを、Dはcの浮気のみを知っていることになりますが、1日後にCがcを殺さず、Dがdを殺さない段階で、Cは浮気しているのはdだけではないと、Dは浮気しているのはcだけではないと気がつくので）であるのに殺さないので、bも浮気しているとわかり3日後に殺すことになります（同様に、Cはcを、Dはdを3日後に殺すことになります）。
(4) しかるに3日後になってもBCDがそれぞれbcdを殺さない以上、(1)の仮定が誤りだったということになり、aが浮気していたとわかるので、4日後にAはaを殺します（同様にBCDはそれぞれbcdを4日後に殺します）。
もちろん、この入れ子になった論理構成の最小単位では「村に浮気者がいないと認識している妻は存在し得ない」ということがトリガーになるわけですが。
＞殺したくない人さん
Ｑ８ですがさんへのお応えの裏側になるのですが、妻(1)〜妻(100)がいるとして、妻(1)は「夫(2)〜夫(100)だけが浮気していて、でも妻(2)はそれを知らずに夫(3)〜夫(100)だけが浮気していると思い、その妻(2)は『妻(3)は夫(4)〜夫(100)だけが浮気していると思い、・・』」と考える余地があります。女王のコメントは、99日後に誰も夫を殺さないことと照らし合わせると、そう考える余地がないのだ、ということを示すことになるわけです。
＞連珠さん
殺したくない人さんへのお応えをご覧ください。
9月 15th, 2007 at 1:36:38
Aa Bb Ccの3組がいて実際の条件とは違ってaさんのみ浮気していない場合を考えます｡
[Bewaadさんの推論を元に考えます]
｢B(妻)がC(夫)だけ浮気していると思っている(逆に言えば､B(妻)はA(夫)が浮気していないと知っている)｣と仮定とすれば､C(妻)は誰も浮気していないと思っている､とB(妻)はと考えることになりますが､女王の誰か1人は浮気しているとの言葉を前提とすれば､C(妻)はA(夫)･B(夫)のいずれも浮気していないのだから浮気している1人はC(夫)と気づいて彼を殺すはずなのに殺さない=C(妻)も他の誰か1人の浮気に気づいている=B(妻)はその｢他の誰か1人｣がB(夫)だとわかって彼を殺すことになります｡
B(妻)がB(夫)を殺さないのですから､(実際にB(妻)はC(夫)が浮気していると判るので殺しません)
｢B(妻)がC(夫)だけ浮気していると思っている｣という仮定は…正しいですね｡
A(夫)が浮気していても浮気していなくてもB(夫)もC(夫)も殺されません｡
何故か仮定が正しいのにBはB(夫)を殺しません｡
つまり上の推論に誤りがあるのです｡
どこが誤りか？
それはB、Cの推論をするときにAの推論で得た結論をB、Cの推論の条件にしてしまっているのです｡
でもまあ、これ以上書くと問題視されかねない領域なので私も以上にしたいと思います(^^;;
参考：囚人のパラドックス(似たような推論の間違いを解説しています)
http://stardustcrown.com/reading/prisoners-paradox.html
9月 15th, 2007 at 12:36:00
さて、そろそろ皆さんが「Googleの設問」「Googleの入社試験」と連呼しているうちに、これらの問題が「全てGoogleオリジナルである」と誤解したり「自分はGoogleに入れそう」とか、判断基準がいつの間にかGoogleになるように誘導されています（ここに書き込みするような人は大丈夫でしょうけど）。
記者の意図がどうであれ、この記事はGoogleの認知度アップに大いに貢献していますね。面白い。
9月 15th, 2007 at 14:06:56
夫婦問題ですが、この問題文だけでは「何も起こらない」が正解だと思われます。
百組を簡単のため二組として推論します。
一日目。
Ａ妻「確かにＢ夫は浮気しているわ。Ａ夫はわからないわね。」
Ｂ妻「確かにＡ夫は浮気しているわ。Ｂ夫はわからないわね。」
よってＡ夫、Ｂ夫ともに生存します。
二日目。
Ａ妻「へえ、Ｂ妻はＢ夫が浮気しているかどうかは知らないんだ。Ｂ妻はＡ夫が浮気していると思っているわ。」
このようにＡ妻にはＡ夫が浮気しているかどうかはわかりません。わかるのはＢ妻がどう思ったかだけです。Ａ妻が『Ａ夫は浮気している』とわかるためには、問題文に次の条件甲ａが必要です。
条件甲ａ「Ａ妻は『Ｂ妻はＡ夫が浮気しているかどうかを知っている』ことを知っている」
この条件甲ａの下では、二日目のＡ妻の推理の『Ｂ妻はＡ夫が浮気していると思っているわ。』が『Ｂ妻はＡ夫が浮気していると知っているわ。』に変わります。
Ｂ妻についても同様に次の条件甲ｂが必要です。
条件甲ｂ「Ｂ妻は『Ａ妻はＢ夫が浮気しているかどうかを知っている』ことを知っている」
結局、次の条件甲が無ければ何も起こりません。
条件甲「妻は他の妻がその妻の夫以外の夫が浮気しているかどうかを知っていることを知っている」
条件甲の下では、二日目にＡ夫とＢ夫は殺害されます。
まだ正確に考えていませんが、三組のときには条件甲に加えて、次のような形の条件乙も必要になると思います。
条件乙「……を知っていることを知っていることを知っている」
初コメントが不躾な長文で申し訳ありません。
9月 15th, 2007 at 19:35:07
＞mastacosさん
お示しの例では、B（妻）はB（夫）を殺すことになります。C（夫）だけが浮気しているならば、最初にC（夫）が殺され（C（妻）はA（夫）・B（夫）が浮気していないことがわかるのに、誰か1人は浮気している＝それが自分の夫だと気がつくので）、A（妻）・B（妻）はそれを見てC（妻）は誰の浮気にも気づいていなかった＝A（夫）・B（夫）ともに浮気をしていない、とわかるのでそれで終わります。
しかしC（妻）はC（夫）を殺さないわけで、そこからB（妻）はC（妻）が他の誰かの浮気を知っているとわかり、A（夫）が浮気していない以上、それは自分の夫だと気づいて殺すことになります。
9月 15th, 2007 at 19:36:42
＞通行人さん
オリジナルがなにか、それを調べるのも面白いでしょうね。
＞マルさん
問題文の「どの妻も、自分の夫でない男が浮気するとすぐにそれを知ることが出来ますが、自分の夫が浮気してもわかりません」とは、それら条件を含意していると思っていましたが、どうなんでしょうかねぇ。
9月 15th, 2007 at 20:29:41
浮気の村の問題は、結局何人いようが(夫婦の数も浮気夫の数も)、
[ある妻が認識している浮気の人数] 日目
にその認識している人たちが全員殺されなければ
『自分が認識できない浮気もの＝自分の夫』
が存在するという結論になり、殺すしかなくなる。
という法則ですよね。
(完全に余談ですが、妻たち全員が十分に思慮深いのか！という疑問も少し納得できます・・・
むかしからそういう法則なんだと村全体に言い伝えられてるとか)
つまるところ、設問のケースだと毎日(いつ殺人がおこるかと)ヤキモキしながらすごすのではなく、99日目だけをひたすら待つんですね。99人の浮気者が見えてるわけですから。
一言だとうまく表現できませんが、この問題は「浮気をしていない夫が誰なのか」も自分の夫以外に関してははっきりわかる(という仮説が立てられる)という事がポイントになり、自分の夫が浮気をしていないとすると、他の妻は「自分が認識している浮気の人数-１」を浮気夫として認識しているはずだという仮説が生き、帰納的に解答を導けるものですね。
いくつか別見解が提示されていますが、私はwebmaster様の説明で模範(本当に模範なんてものが存在するなら！)解答という事で間違いないと思います
これを思いついた頭脳に敬服。
9月 16th, 2007 at 6:17:39
＞webmasterさん
条件甲は要するに『「どの妻も、自分の夫でない男が浮気するとすぐにそれを知ることが出来ますが、自分の夫が浮気してもわかりません」ということをどの妻も知っています。』というようなものですから、単なる『「どの妻も、自分の夫でない男が浮気するとすぐにそれを知ることが出来ますが、自分の夫が浮気してもわかりません」』とは異なる条件ではないかなと考えました。正確にはこれだと条件甲よりも強すぎる条件になってしまっていますが。
最終的には問題製作者に尋ねるしかない話だと思います。
9月 16th, 2007 at 11:30:21
Q2なんですが、元の英文だとheightとしか書いてないので
厚みをheightと見なした場合また変わってくるんじゃないでしょうか？
9月 16th, 2007 at 13:02:20
「Googleの面接試験」をまじめに考えてみる…
というわけでGIGAZINEの記事 「Googleの面接試験、一体どのような質問をされるのか？」 http://gigazine.net/index.php?/new (more…)
9月 17th, 2007 at 0:31:43
＞通りすがり19さん
私が考え付いたわけではなく、ノーベル経済学賞受賞者のオーマンが考案した問題（ということを望月さんに教えてもらったわけ）ですので（笑）。
＞マルさん
厳密にはおっしゃるとおりですが、オーマンの問題だという結論からの要請だと割り切るのかな、と。出題者があえてそこをオーマンの問題と違う条件にして、どのように答えが違うのかを問うているのではないのだろうなぁと勝手に思ってます。
＞数学は苦手なんですがさん
heightであれwidthであれlengthであれ、単位はm（やcm、mmなど）になりますが、面積はm2、体積はm3になります。この問題は、そこを問うているものだと理解しています。
9月 17th, 2007 at 15:55:06
浮気の問題は実はＱ９でしたね・・・・・
せっかくですからハンドルはこのままで。
元はノーベル賞学者の出題ですか。面接なら問題の解釈の幅もあるでしょうが、こういう場ではやはり唯一解のある純ロジックな問題であると仮定しないと議論が不毛になってしまいますね。
元問題があるならwebmaster様の解答で間違いないのかも知れませんが・・・・やはり自分としてはすっきりしないのであえて異論を述べてみます。
さて、女王の発言が村人の共通認識になんらの変化も引き起こせ得ない状況下でそれをトリガーとしたイベントが起こるという点にどうしても納得がいかないので改めて考えてみました。
「村に浮気者がいないと認識している妻は存在し得ないということが全妻の共有認識になる」ことをとりあえず条件１とします。
条件１が入れ子最下層のトリガーならやはり４人以上の浮気者がいる村においては１人以上の浮気者がいるという女王発言は妻たちの認識になんらの変化をももたらさないのではないかと思います。
４人の浮気者がいる村は浮気者の妻でさえ３人の浮気者を認識している状況ですね。自分の村が条件１を満たしていることを任意の妻が確信できるのは、その妻が３人の浮気者を認識した時ですから、ここで条件１がトリガーになるという仮定が真だとすると、３人目の浮気者が出た段階で（１００組の村において）９７人の無実の夫が殺されることになります。
するとこのロジックは、少なくとも４人以上の浮気者のいる村においては成り立たないということになります。なぜ、成り立たないのでしょうか。
ここでwebmaster様の先日の回答(38)をよく検討してみますと、（３）の（bが浮気していない場合、Cはdの浮気のみを、Dはcの浮気のみを知っていることになりますが、1日後にCがcを殺さず、Dがdを殺さない段階で、Cは浮気しているのはdだけではないと、Dは浮気しているのはcだけではないと気がつくので）の部分に疑問を感じます。
ここでＡの想定するＢの推論は「Ｃ、Ｄがお互いの夫の浮気を確定できないが故にＣ，Ｄは２人以上の浮気夫を認識していることが確定できる」というものです。しかし、Ａは「無条件に」Ｃ，Ｄが２人以上の浮気者を認識していることを知っています。ここで入れ子の最下層の状況がＡの認識とＡの想定するＢの認識でどう変わるかを示しますと
想定Ｂの認識：Ｃの認識している浮気者はＤのみ→１人の浮気者の存在が確定している状況で、ＣはＤが夫を殺さないことが自分の夫の浮気を意味すると確定できる。なぜなら１人以上の浮気者の存在が確定したことで、Ｄが村に浮気者がいないと認識している可能性が否定されたからである。
Ａの認識：Ｃの認識している浮気者はＢ，Ｄ→１人の浮気者の存在が確定しているだけの状況では、ＣはＤが夫を殺さないことが自分の夫の浮気を意味すると確定できない。１人以上の浮気者の存在が確定したことで、Ｄが村に浮気者がいないと認識している可能性が否定されたからでは無い。
よって、Ａは想定Ｂの「Ｃ，Ｄが１人の浮気者しか認識していない可能性を排除する推論」が誤りであることがわかり、そこから「想定ＢはＣ，Ｄがそれぞれ２人以上の浮気者を認識していると確定できない」ことがわかってしまいます。
もう少しわかりやすく整理します。一番上のＡを最上位の視点とするとそれぞれの段階の一段下の想定し得る認識数は以下のようになります。
Ａ ３
Ｂ ２or３以上
Ｃ １or２以上
Ｄ ０or１以上
このロジックはorの左辺の認識数である可能性を下から漸次否定することでorの右辺の認識数を確定することで成り立ちます。しかし、４人の浮気者の村においてはＡはＢ，Ｃ，Ｄがそれぞれはじめから二人の浮気者を認識していることを知っています。よって「Ｂ夫の浮気を認識せずに、Ｄが自分の夫の浮気を確定するかどうかで自分の夫の浮気を判定しようとするＣ」の仮定が存在し得ないため、Ｂ，Ｃ，Ｄがそれぞれお互いに「相手が１人の浮気者しか認識していないと思い込んでいる可能性」を否定できず、彼女らがそれぞれの浮気を確定できないことを根拠として彼女らが３人の浮気者を認識している、つまり自分の夫が浮気していると確定することができません。
つまり、４人の浮気者がいる村における認識数の段階は実際はこういう形になります。
Ａ ３
Ｂ ２or３以上
ＣＤ １or２以上
４人の浮気者のいる村では「村に浮気者は１人しかいないと認識している妻は存在し得ない」ということが全妻の共有認識になるようにする、つまり女王が「村には２人以上の浮気者がいる」と宣言しなければ誰も自分の夫の浮気を確定できないのではないでしょうか？
別の面から考えます。妻Ａから見て自分の夫が無実と仮定する場合、Ｂの認識する浮気者の数は自分の認識数−１です。ここでＢが自分の夫の無実を仮定していたとするならＢの想定するであろうＣ以下の妻の認識数は自分の認識数−２です。ここから先のＣ以下が自分の夫の無実を仮定した状況、すなわち自分の認識数−３の妻の存在を前提とするロジックは、そういう認識をしている妻がいかなる状況においても存在し得ないが故に破綻します。浮気者が３人の村では自分の認識数−２の認識をしている妻、浮気者が２人の村では自分の認識数−１の認識をしている妻、浮気者が１人の村では自分の認識数と同じ認識数の妻の存在する可能性がそれぞれ否定されることで自分の夫の浮気を確定できますが、自分の認識数−３以下の認識をしている妻は元々有り得ないが故に、４人以上の浮気者がいる村では、その存在を否定することが自分の夫の浮気の確定に繋げられなくなるわけです。
となると４人以上の村で女王発言がトリガーになる為に、女王がその存在を確定しなければならない浮気者の人数は「任意のＡの認識数−２」の認識数を持つ妻の存在可能性をまとめて否定できるだけの数でなければならないということになります。つまり４人以上の浮気者がいる村では「浮気者実数−２」以上の浮気者の存在を宣言する必要があるのではないでしょうか？
9月 18th, 2007 at 5:04:46
＞Ｑ８ですがさん
最初にQ9をQ8と誤記したのは私ですので、Ｑ８ですがさんには何の誤りもございません。
＞しかし、４人の浮気者の村においてはＡはＢ，Ｃ，Ｄがそれぞれはじめから二人の浮気者を認識していることを知っています。よって「Ｂ夫の浮気を認識せずに、Ｄが自分の夫の浮気を確定するかどうかで自分の夫の浮気を判定しようとするＣ」の仮定が存在し得ない
もちろんAはそう知っているわけですが、想定Bの主観的認識においてはCの存在を仮定できます。4組の夫婦の村で、aは本当に浮気をしておらず、Aがbcdの浮気に気がついている場合を想定してみてください。この場合であっても、「ＡはＢ，Ｃ，Ｄがそれぞれはじめから二人の浮気者を認識していることを知っています」が、しかしながらBCDはbcdを殺すことになるわけで。
9月 18th, 2007 at 16:47:11
前に最後と書いてまたQ9の浮気問題を書きます(^^;;
Common knowredge
http://www.us.kanto-gakuen.ac.jp/indo/kw/ck03b.html
を読みました。
でも第三者ではなく内部の人間(3人の帽子問題で言うならAが言ったような状態)
では成立しないよなあ、と思ったのですがよく問題を読み直して気付きました。
the queen of the village visits and announces
女王が言いました→女王が訪れて言いました。
つまり村の100組とは別の第三者が村を訪れて言った、と言うことを示しているのでしょう。
さらに女王と言うのも以前、王がいたが死んで女王になった→元妻なのでこの能力を持っていた。
と言うことを暗示しているのでしょう。
これでトリガーが引かれた理由も判ります。
で、Bewaadさんの解答通り100日後に全員の夫が死ぬ、と言うことで正答だと思います。
9月 18th, 2007 at 19:04:51
Q9で盛り上がっている所ですが、Q7別解を考えてみました。
この方法だと道の数が有限なら、ゴールに到達可能の場合、必ず有限の時間内に到達でき、到達不可能ならその事が確実にわかります。(時間はものすごくかかるような気がしますが)
bewaadさんの方法だと「分かれ道に誰もいなかったらどうするか」とか「ゴールできる保証があるのか」とか「そもそも到達できないときはどうするのか」の問題があると思います。そのかわり上手くいくと短時間でゴールできる訳ですが。
(1)スタート地点にスタート地点と判るマークを(例えばS)を書きます。
(2)
(2-a)まだ進んでない方向があれば、進む方向を決めマーク(例えば×)を書きその方向に進みます。(3へ)
(2-b)すべての方向にマークがついていればゴールにはたどり着けません。
(3)
(3-a)初めての(マークが1つもついてない)分かれ道に来たら来た方向にマーク(例えば○)を書きます。(4へ)
(3-c)初めてでない(マークが書いてある)分かれ道に来たら来た方向に(2-a)と同じマークを書き引き返します。(5へ)
(3-c)行き止まりなら引き返します。(5へ)
(3-d)ゴールなら終わり。
(4)進んだことのない(マークのついてない)方向から、次に進む方向を決め(2-a)と同じマークを書きその方向に進みます。(3へ)
(5)
(5-a)まだ進める(マークのついてない)方向がある分かれ道についたら(4)へ。
(5-b)すべての方向に進んで(マークがついて)いれば(3-a)でつけたマークの方向に進む。(5へ)
(5-c)スタート地点に戻ったら(2)へ。
9月 19th, 2007 at 0:34:47
Q4. 「a＜bならスタックは減ります（grow downする）」
「a＞bなら」の間違いでしたorz
9月 19th, 2007 at 1:50:30
Q3
シアトルには雨季があるので、そもそも窓拭きの仕事がない。
Q7
携帯でGoogleマップを使う。
9月 19th, 2007 at 6:07:54
＞mastacosさん
私も外部の者であることを前提にしていました。
＞ぬ゛さん
迷路で右手をずっと壁に触れさせて・・・というのと同じタイプの解法ですね。
ところで、本日付け足した私の解法もまた「『分かれ道に誰もいなかったらどうするか』とか『ゴールできる保証があるのか』とか『そもそも到達できないときはどうするのか』の問題」はないものと理解しているのですが、違いますでしょうか?
＞lukeさん
ご指摘を踏まえ訂正いたしました。
＞猿ましーんさん
雨上がりって、かえって汚れることも多いのではないでしょうか。
9月 19th, 2007 at 8:57:56
>bewaadさん
例えばスタート時点で「誰か」はどのように見つけるのでしょうか。適当な方向に進んで見つけようとしても、誰もいないところを堂々巡りをしてしまう可能性があります。
また、B地点への行き方を誰も知らなかったらどうなるでしょうか。それに全員に聞いたかどうかはどのように確認するのですか。
それに、同じ人に何度もたずねている可能性もありますよね。
9月 20th, 2007 at 0:04:18
すみません、56で言ってる、同じ人に何度も尋ねる可能性はないですね。
あと問題点の追加なのですが、尋ねた人が他の場所への行き方を1つも知らなかったらどうするのでしょうか。
9月 20th, 2007 at 19:56:55
＞mastacos様
女王自身が含まれることの影響を考えてみます。
まず、女王の夫が浮気をしていないならば、女王は実質外部からの宣言者と変わりありません。
１００組の村なら外部から宣言者が来た９９組の村になるだけです。
女王の夫が浮気していればどうなるでしょうか？まず１００組の村に浮気者が１人いて、それが女王自身の夫だとします。
女王が「１人以上の浮気者がいる」と言えば女王の夫以外の９９人の無実の夫が殺されるでしょう。
これは「９９組の浮気者が１人もいない村」に外部から来た女王が「１人以上の浮気者がいる」と宣言した時と同じ現象です。女王の夫とＡの夫との２人の浮気者がいる村ではどうなるでしょうか？Ａは女王が１人を認識しているなら、それは女王の夫しか認識していないＡ自身の夫だと考え、夫を殺すでしょう。３人ならＡはＢが夫を殺さないことからＢが女王の夫以外を認識していることを確定し、自分の夫を殺すでしょう。だだし、どの場合も女王自身は自分の夫の浮気を知り得ません。つまり「女王が認識しているのは女王自身の夫以外の誰かでしか有り得ない」が故に、実質的に女王は外部からの宣言者と同じ立場にしかなりえないのです。村は女王夫妻をカウントしない村と同じ状態になります。つまり「女王の夫を含む３人の浮気者がいる１００組の村」は「２人の浮気者がいる９９組の村に外部から女王が宣言しに来る」のと同じことになります。したがって４人の浮気者がいる村でも、それが女王の夫を含むなら「女王が外部から宣言しに来る３人の浮気者の村」と同じになるので、たしかに女王宣言がトリガーになり得ます。（もちろん女王の夫だけ殺されないわけですが）
しかし、５人の村ならトリガーになり得るでしょうか？
＞webmaster様
改めて表にしてみました。今まで通り女王は外部者とします。
orの含まれている部分が「想定される認識数」です。
前回は構造の最上位の視点をＡ固定としましたが、構造内での絶対位置をわかりやすくする為に最下段の方をＤで固定することにします。コメント欄では表の途中で改行されるので見づらいかも知れませんが、エディタ等にコピペすれば見やすくなると思います。——は入れ子の段の区切りです。
それぞれの段で「」でくくられた認識数である可能性が排除されたなら、最右辺の認識数であることを上段が確定できる構造です。
まず浮気者２人の村の場合です。表の意図を明確にする為にあえて２人の村の場合だけ説明してみます。
最上位の実視点者Ｃの想定する想定視点者Ｄは０人か１人の浮気者を認識している可能性があります。
しかし、「村の浮気者１以上」が確定すると、想定Ｄが浮気者は０人と認識しているならば想定Ｄは自分の夫を殺さなければならないことから、想定Ｄの認識している浮気者が０人である可能性が排除されて確実に１人以上の浮気者を認識していることになり、想定Ｄの認識数と自分の認識数が一致していることが確定しＣは自身の夫の浮気を確定できます。
ア）Ｃ １ （Ｃ自身） Ｄの認識数＝Ｃの認識数の場合夫を殺す
———————————————————————-
イ）Ｄ 「０」or１以上 （Ｃの想定するＤ）認識数０の場合夫を殺す
そのまま浮気者３人の村にあてはめるとこのようになります。
ア）Ｂ ２ （Ｂ自身） Ｃ、Ｄの認識数＝Ｂの認識数の場合夫を殺す
———————————————————————-
イ）Ｃ 「１」or２以上 （Ｂの想定するＣ）認識数１の場合夫を殺す
ウ）Ｄ 「１」or２以上 （Ｂの想定するＤ）認識数１の場合夫を殺す
———————————————————————-
エ）Ｄ 「０」or１以上 （Ｂの想定するＣの想定するＤ）認識数０の場合夫を殺す
さらに浮気者４人の村に「そのまま」あてはめるとこのようになります。
ア）Ａ ３ （Ａ自身） Ｂ、Ｃ、Ｄの認識数＝Ａの認識数の場合夫を殺す
———————————————————————-
イ）Ｂ 「２」or３以上 （Ａの想定するＢ）認識数２の場合夫を殺す
ウ）Ｃ 「２」or３以上 （Ａの想定するＣ）認識数２の場合夫を殺す
エ）Ｄ 「２」or３以上 （Ａの想定するＤ）認識数２の場合夫を殺す
———————————————————————-
オ）Ｃ 「１」or２以上 （Ａの想定するＢの想定するＣ）認識数１の場合夫を殺す
カ）Ｄ 「１」or２以上 （Ａの想定するＢの想定するＤ）認識数１の場合夫を殺す
———————————————————————
キ）Ｄ 「０」or１以上 （Ａの想定するＢの想定するＣの想定するＤ）認識数０の場合夫を殺す
３人の浮気者の村での実体Ｂの視点と４人の浮気者の村での想定Ｂの視点は一見同じように見えますが決定的な違いがあります。
３人の浮気者の村での実体ＢはＣ，ＤがＢと同じ視点までしか持ち得ないことを知っています。Ｂがまさに自分自身であるが故に「自分が３人の浮気者を認識していることは絶対有り得ない」ことを知っています。これは同時に「Ｂの想定するＣ，Ｄも３人の浮気者を認識していることは絶対有り得ない」ということです。
しかし、４人の浮気者の村での想定ＢはあくまでＡの想定内の存在でしかないが故に「３人の浮気者を認識し得る」のです。そして同時に想定ＢはＣ，ＤがＡの視点、つまり想定Ｂより一段上の視点から見る可能性があり、「３人の浮気者を認識し得る」ことと、Ｃ，Ｄが２段下の視点から見る可能性、すなわち上の浮気者４人の村の表でキの視点で見る可能性が有り得ないことを知っているのです。
キが有り得ないので、キを根拠とするオ、同様にカも確定できません。つまりＣ，Ｄの認識数が１である可能性を排除できないのです。
実在し得るのは自分の認識数-1の妻までしか有り得ない、その妻が想定し得るのは自分の認識数-2の妻までしか有り得ない、つまり入れ子が最大３段階までしか成り立ち得ないことが共有認識として存在する為にあくまで最上位推論者の想定内存在にすぎない人物の思考は無限に伸びるのでは無く、最上位推論者の認識によって制限されるのです。
ここで強引に３人の浮気者の村と同じようにロジックを押し通そうとした場合どうなるでしょうか？。
３人の浮気者の村においては実体Ｂの想定するＣがＤの認識数として考え得る可能性は最大想定可能数３からＢＣの夫の可能性を引いた（０or１）ですが、４人の浮気者の村においては想定Ｂの想定するＣがＤの認識数として考え得る可能性は実際は（０or１or２）になってしまうのです。なぜなら想定Ｂの思考世界にはＡの夫が浮気している可能性が含まれるわけですから。
したがって、「４人の浮気者の村の想定Ｂ」が「３人の浮気者の村の実体Ｂ」と同様の結論に至る為には、「Ａの夫が絶対に浮気していない」という前提が必要になります。しかし、そうなると「Ｂが３人の浮気者の存在を確信しているはずなのに夫を殺さないのは村に４人の浮気者がいるからだ」という結論になる前提条件が、そもそも「Ａの夫が絶対浮気していない」である為、ＡにとってはＡの認識し得ない浮気者が自分の夫以外にもう１人いなくてはならないという奇妙な状態になるのです。
webmaster様がコメント50で述べられた「4組の夫婦の村で、aは本当に浮気をしておらず、Aがbcdの浮気に気がついている場合」に「BCDはbcdを殺すことになる」のはBCDがお互いにaが浮気をしていると思っている可能性を完全に除外できるからです。
当初から有り得ない可能性キ）を表から排除して整理すると４人の浮気者の村の実際はこのようになります。
ア）Ａ ３ （Ａ自身） Ｂ、Ｃ、Ｄの認識数＝Ａの認識数の場合夫を殺す
———————————————————————-
イ）Ｂ 「２」or３以上 （Ａの想定するＢ）認識数２の場合夫を殺す
ウ）Ｃ 「２」or３以上 （Ａの想定するＣ）認識数２の場合夫を殺す
エ）Ｄ 「２」or３以上 （Ａの想定するＤ）認識数２の場合夫を殺す
———————————————————————-
オ）Ｃ 「１」or２以上 （Ａの想定するＢの想定するＣ）認識数１の場合夫を殺す
カ）Ｄ 「１」or２以上 （Ａの想定するＢの想定するＤ）認識数１の場合夫を殺す
想定Ｂの世界においてＣ、Ｄがお互いに相手の認識数を１だと思っている可能性が残るわけですから、Ａから見るとＢ、Ｃ、Ｄのトライアングルの間でお互いに決め手を欠いている状態になります。よってＡはＢ、Ｃ、Ｄが３以上を認識しているとは確定できません。
女王が１人では無く、「２人以上の浮気者がいる」と宣言すればＢ、Ｃ、Ｄが１人しか認識していない可能性がそれぞれの想定内から排除され、浮気者が全滅します。
9月 21st, 2007 at 0:17:01
＞ぬ゛さん
誰も知らないという可能性は見落としていましたが、蓬莱（の玉の枝）のような事例だとそうなりますね。ま、B地点の存在自体が確実でなければ不能命令の可能性がありますし、存在が確実ならば誰かは知っているということで。
＞Ｑ８ですがさん
mastacosさん向けについてですが、
＞まず１００組の村に浮気者が１人いて、それが女王自身の夫だとします。女王が「１人以上の浮気者がいる」と言えば女王の夫以外の９９人の無実の夫が殺されるでしょう。これは「９９組の浮気者が１人もいない村」に外部から来た女王が「１人以上の浮気者がいる」と宣言した時と同じ現象です。
女王の夫が浮気していると99人の妻は認識できるので、そのようなことにはならないのではないでしょうか?
で、私宛についてですが、
＞４人の浮気者の村での想定ＢはあくまでＡの想定内の存在でしかないが故に「３人の浮気者を認識し得る」のです。
は、Aが自分の夫は浮気していないと仮定した場合においての話ですから、認識し得るとすれば仮定条件を破ったことになってしまいます。
背理法、すなわちこの場合でいえば「aは浮気していない」と「bcdが殺されない」が矛盾するから「aは浮気していない」は誤り＝「aは浮気している」と導いているわけで、「3人の浮気者を認識し得る」とは「aは浮気していない」との仮定に反するということで、それが証明そのものといいますか、「ＡにとってはＡの認識し得ない浮気者が自分の夫以外にもう１人いなくてはならないという奇妙な状態」だからこそaの浮気が確実に推定可能になるわけです。
9月 21st, 2007 at 19:18:22
＞webmaster様
まず、上段についてですが、前提条件は「村人に女王を含む」ですから、女王も他の妻達同様自分の夫の浮気を認識し得ません。
村人達が「女王の夫＝女王の指摘する1人の浮気者」と解釈するなら「女王は自分自身の夫の浮気を認識し得る」ことになります。
次は下段についてですが、（「aは浮気していない」と「bcdが殺されない」）以前に（「aが浮気している」と「bcdが殺されない」）わけです。「aが浮気している」とBCDはbcdの浮気を確定できないのですから。だから「aは浮気していない」は誤り＝「aは浮気している」と導けません。aが浮気していても浮気していなくてもbcdの示す行動は同じわけですから。BCDがbcdの浮気を確定できるのはあくまで「aが絶対に浮気をしていない場合」だけです。
もし無理矢理に「ＢＣＤが３人の浮気者を認識している」を確定できるとするなら、それはa以外でなければならないし、「ＢＣＤが３人の浮気者を認識している」が確定できないとするなら、aは浮気している可能性があるがそれは確定できない、というだけのことなのです。
9月 22nd, 2007 at 13:03:06
第 4 問の問題文の和訳は「マシンのスタックがメモリ内で上向きに伸びるか下向きに伸びるかを知るにはどうしたらいいですか」あたりでしょう。
スタックが grow up, grow down することを「スタックが増える/減る」とは言わないと思います。「アドレスが増加する向きに伸びる」「アドレスが減少する向きに伸びる」と言う方がわかりやすいですが、原文の grow up, grow down に合わせました。
第 7 問の今の解答 (通りすがりさんのコメント 36 番) について。
この解答では Bewaad さんもコメント 59 番でおっしゃるように B への行き方を知る人がいないと到達できないのはもちろんのことですが、すべての地点 x について x への行き方を知っている人が一人はいると仮定してもまだ B に到達できない可能性があります。世界が二つに分断されていて、 B を含む側の地名が A を含む側でまったく知られていない場合などが挙げられます。
さらに、そういう知識の分断がない――厳密に言えば、任意の 2 点 x, y に対して x=z[0] から y=z[k] に至る地点の列 z[0], z[1], …, z[k] が存在して、 z[i] には z[i+1] への行き方を知る人がいる――と仮定しても、どの人に尋ねるかや、複数の地点への行き方を知る人に尋ねたときにどの地点への行き方を教えてもらえるかは今の方法では運次第で、運が悪いとやっぱり B に到達できない場合があります。例えば、
* 地点は A, B, C の 3 個しかない
* A には B, C への行き方を知る人がいる
* B には A, C への行き方を知る人がいる
* C には A への行き方を知る人はいるが B への行き方を知る人はいない
という状況では、上の意味での知識の分断がありません。しかし、 A で尋ねた相手が C への行き方を答えてしまうと B に到達できません。
9月 23rd, 2007 at 4:38:12
＞Ｑ８ですがさん
前段については、問題文そのものには不能条件が埋め込まれていないことを前提にしてましたので、女王が浮気者がいるといったところで、それは神託か何かでルールの埒外なんだろうということとして処理すべきだと思ってました。ま、ここはあれこれ考えても確証が見つかるはずもないところで、女王の宣言もまたルールに縛られるのであれば、おっしゃるとおりです。
後段については、背理法での仮定はすなわち絶対であるとして取り扱うことですから、絶対だというのが真でないからといって成り立たないといってしまえば議論ができないことになってしまうのではないでしょうか。たとえば、√2が無理数であることを証明しろという場合、よくあるのは有理数であると仮定し、√2＝p／qである場合には・・・として矛盾を導きますが、ここで√2＝p／qとは仮定であって絶対ではないのだ、と言ってしまえば証明はできません。
結局、「BCDがbcdの浮気を確定できるのはあくまで『aが絶対に浮気をしていない場合』だけ」で、BCDが確定できない＝「aが絶対に浮気をしていない場合」ではない＝「aが絶対に浮気をしている」という形で完結しているということとなります。貴見は最後の等号がおかしくて、「aが絶対に浮気をしていない」の否定は「aは浮気しているかしていないかのいずれかである」ということと理解していますが、それは先の√2が無理数であることの証明問題において、p／qで絶対に表すことができるとすると矛盾だと導いた際、p／qで表すことができるかもしれないしできないかもしれないから、無理数であるとは限らないとするようなものではないでしょうか。
＞fcpさん
訳文のご提示、ありがとうございました。
新しい解答ではどこで聞くかについては定めはなく、お示しのような場合においてはA地点に戻ればよい、ということとなるものと認識しています。
9月 24th, 2007 at 23:57:58
第 7 問の解答を誤解していました。ご指摘ありがとうございます。今の解答では質問する場所を特定していないので、たしかに分断がなければいつかは辿り着けますね。
次に質問する場所を選ぶ方法を指定しないのは、この問題に対する解答として十分かという点には疑問がありますが……このあたりは面接官が何を問いたくて質問しているかに依存すると思います。
面接官の意図は試験を受けたわけでもない身には想像するほかなく、絶対の自信はありませんが、僕はこの問題をグラフの基本的なアルゴリズムの知識を問う問題だと解釈したので、ぬ゛さんの解答 (http://bewaad.com/2007/09/11/263/#comment-18078) を推したいです。
(参考までに、ここでいうグラフというのは、都市の間の道路の構造や、ウェブのページ間のハイパーリンクの構造のように、頂点の間が辺でつながった構造のことです。詳しくは「グラフ理論」を調べてください。複雑な計算をするプログラムを書こうとすると、ウェブグラフに限らず様々な形でグラフが登場するため、 Google の入社試験でグラフのアルゴリズムが問うのは自然なことだと思います。)
9月 25th, 2007 at 23:29:37
＞fcpさん
グラフ理論のアナロジーとは思いつきませんでした。エントリでも書いたように、問題を読んだ瞬間にインターネット接続のアナロジーだと思いついたのですが、かえってそれに囚われてしまったようです。
9月 26th, 2007 at 11:21:11
Googleの面接試験に答えてみた…
GigazineさんのところにGoogleの面接試験なるものが存在していたのでいざといてみることにした。
てか本当にできるか超不安。 (more…)
11月 2nd, 2007 at 14:32:10
100組の夫婦の村なので100人の浮気夫がいるには、2人以上100人以下の浮気妻が居るのです。
自分の夫を殺したくない浮気妻Ａが妻Ｂに告げ口します。
「あんたの夫Ｂさっさとくびりなさいよ！」
妻Ｂは浮気していたら大声で喚きます。
「夫Ｃだって私と浮気したじゃないの！」
妻Ｃは浮気をしていなかったので無言で夫Ｃをかち割りました。
というわけで、一番の口軽女と浮気した夫から連鎖して貞淑な妻の夫までが殺されます。
殺される夫の数は１人以上100人以下です。
11月 14th, 2007 at 7:46:30
＞昼ドラだと…さん
ドロドロの愛憎劇となると、浮気も続けたいので、自分の浮気相手でない夫と浮気した、と嘘をつくとか（笑）。
1月 20th, 2008 at 1:48:32
だいぶ前の話ですが･･･
海賊の設問、１:９８:１:０:０じゃないかと。
「次の投票で賛成しても結果は同じ」という人が、１００％
賛成してくれるかわからないという考え方で。
３位が提案する「９９:１:０」がスタート地点で、これは動かないので、２位はこれをしのごうと思ったら「９７:０:２:１」を提案するしかありません。４位の確実な賛成のために増額せざるを得ず、５位を味方につけるには１枚必要。
１位は３人に「９８枚・１枚・１枚」を配分して２位の案をしのぐ必要があるので、次回に２枚が期待される４位はゼロにするしかありません。また５位に１枚だけでは、２位の案とメリットが同じなため、賛成の確証なく増額なしには取り込めません。しかし、この場合は２枚以上の分配は不可能ですので反対派とするべき。
すると、２位と３位の賛成が条件になるわけで、３位には１枚与えればベストの結果になりますが、２位の賛成を得ようと思えばプラス１枚の９８枚を与えるしかありません。そして自分に１枚を割り振って成立となります。
分け前よりも確実に生き残る方向で考えましたが、設問で言う「最大の分け前」のとらえ方が果たしてどうか･･･。
1月 23rd, 2008 at 3:55:26
＞モリゾーさん
＞この場合は２枚以上の分配は不可能
というのがよくわからないのですが、どういうことなのでしょうか?
2月 3rd, 2008 at 8:49:05
Q8はやはり何も起こらないと思いますね。
男全員が浮気したことがあって、自分の夫以外の浮気を知ることが出来るのなら、妻達は99人の浮気男を把握しているわけですし
女王が村人全員が浮気している、とでも言わない限り誰も殺すことはないじゃないでしょうか。
女王の宣言以前から浮気者がいるのは知っていたわけですし。
解答にある、1日待って誰も殺さなかったから自分の夫が…という論理だと
2日目に全員が同時に夫を殺す気がするのですが。
2月 3rd, 2008 at 8:49:31
Q9ですね。失礼しました。
2月 9th, 2008 at 14:42:22
男女比率の問題について。
正直非常に簡単な問題です、証明方法はいくつかあるでしょうが答えは全て１：１になるはずです。
仮に、重婚無し、国際結婚無し、離婚再婚無し、とします。日本においてはいたって平均的な考えだとは思います。
そうするとルールを守り続けた場合、人口が増える要素が無いので、最終的に「０：０」になります。
簡単だからこそ「１：１」と答えるような人間は雇わないと思いますがどうなんでしょうか。
私なら雇おうとは思いません。
3月 15th, 2008 at 13:31:59
Q9なんですが，私も70のう〜んさんと同意見です。
そもそも模範解答における「夫以外の男の浮気に気付く為には1人につき１日かかる」というルールは問題文のどこを読み解けば良いのでしょうか？
3月 20th, 2008 at 23:09:20
はじめまして。
模範解答を確認していて違うと思う解答がありました。
それはQ14で、賭けを受け入れないとの選択は
賭けを受け入れるが正解だと思います。
何故なら、パーティには
”あなたを含めて10人いて”
”あなたと同じ誕生日の人がこの中にいれば”
~~~~~~
とありますから自分も含まれることになります。
つまり、自分と同じ誕生日のものは100%（自分）
存在することになるので
”いる”方に賭ければ100%勝てる！
と思うのですがどうでしょうか・・・。
4月 14th, 2008 at 12:39:46
Q9.この村の掟では浮気や姦通は許されていません。この村の女達は掟には背きません。
とありますがでは男性たちは誰と浮気をしていたのでしょうか・・・ｗ
9月 1st, 2008 at 23:17:22
面白いので我がブログにコピペしてよろしいでしょうか？
コピペ元は掲載させていただきます