ニルヴァーナ Google面接試験、Q17の正しい解答

Google面接試験、Q17の正しい解答

■Googleの面接試験、一体どのような質問をされるのか？
http://gigazine.net/index.php?/news/comments/20070909_google_job_interview/

■Google面接問題の模範解答の追求
http://bewaad.com/2007/09/11/263/

■Googleの面接試験にありがちなこと
http://news4vip.livedoor.biz/archives/51050686.html

17の海賊の問題について、どこにも正しい解答が出てないみたいなので一応書いておこうかと。

17.
5人の海賊がいて、彼らは1位から5位にまでランク分けされています。1位の海賊は100枚の金貨をどのように分けるかというプランを提案する権利があります。残りの海賊はこのプランに投票する権利があり、賛成が半分に満たない場合には1位の海賊は殺されます。1位の海賊の分け前を最大にしてなおかつ彼が生き残るにはどうすればいいですか？（ヒント：一人の海賊は結局、金貨の98％で終わる）

これが正しい解答↓

残り人数が二人になった時は、投票権があるのが５位一人だけなので
０：１００
以外のどの提案でも４位死亡。よって
？：？：？：１：０

残り三人の時は
９９：１：０
で成立するので、３位は９８以下の何枚を提示してもyesとは言わない。よって
？：？：０：１：０

２位は自分の時に
０：９９：１：０
にしなければ確実に死ぬので１枚でも貰えればyesと言う。

よって答えは

「９８：１：０：１：０」

となる。
みんな考え方が逆だ。

それにしても偶数位と奇数位。
どっちが勝ち組でどっちが負け組なのか……。

<<無題 | ホーム | 曇りのち雨>>

２位の人に１枚を与えてなだめるのは無理です

http://gigazine.net/index.php?/news/comments/20070909_google_job_interview/
からたどってきました。
初めて書き込みさせていただきます。

２位は自分の時に
０：９９：１：０
にしなければ確実に死ぬので１枚でも貰えればyesと言う。

と書かれていますが、これは誤りだと思います。
３位の人の賛成を得なくても、４位・５位の人の
賛成を得て助かることができるので、
９８：０：１：１
で十分なはずです。安全策をとるにしても
９６：０：２：２
とすれば十分すぎると思います。
となると、１位の人は２位の人を抱きこむのは
得策ではないですね。次のターン（２位の人が
分配する）になったときに「０枚」になってしまう
３位の人を抱きこむのが得策ではないでしょうか？

2007/09/20(木) 16:48:17 |
URL |
マリ #.uC3Pteg
[ 編集]

まず最初に一つ。
これは、なだめるとか、安全策とか、抱き込むとか、そういう問題では無いハズです。
もしコレがそういう問題ならば、全員に２０枚ずつ配って仲良しクラブやってりゃいいんです。

この問題には、前提となる考え方が二通りあります。
ひとつは、海賊達は自分たちが確実に金貨を獲得可能なギリギリの線で賛成する。
ひとつは、海賊は最大枚数を獲得可能なチャンスが来るまでは反対する。

自分は後者の考え方を採用しています。
理由はまぁ色々とあるのですが、簡単に言えば

前者の条件だと確実性のある解答が「97:0:1:0:2」になるから

です。
設問内に「98」という数字が示されているので、こっちの考え方は誤りだと判断しました。

この問題は、問題自体に幾通りかに解釈出来る要素が存在するので、絶対にコレが唯一の解答だと言える解答は存在しません。
恐らくは、コレを面接問題で使用する側もそれを解っていて、相手の思考能力を見るために敢えて出題しているのでしょう。
その中で自分が正答と信じるのはコレだ、という事です。