Ad Network

あわせて読みたい

  • あわせて読みたい

« ファイナルファンタジーVII アドベントチルドレン 予約注文開始 | Main | アーキテクトという職種 »

ビル・ゲイツの面接試験-宿題の解答

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

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

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

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

 まず金貨を4個ずつ天秤に乗せて比べる(1回目)。このとき、左の皿に置いたコインを【ABCD】、右の皿に置いたコインを【EFGH】、残りの5つを【VWXYZ】と呼ぶ。

1.釣り合った場合、【VWXYZ】の中に偽造品があることが判明。
 【VWX】と【ABC】を比べる(2回目)
 1-1.【VWX】が重い場合、【VWX】の中に重い偽造品があることが判明 (b)
 1-2.【VWX】が軽い場合、【VWX】の中に軽い偽造品があることが判明 (b)
 1-3.釣り合った場合、【YZ】の中に偽造品があることが判明 (a)

2.【ABCD】が重い場合、【VWXYZ】の中に偽造品がないこと、【ABCD】の中に偽造品がある場合には重い偽造品、【EFGH】の中に偽造品がある場合には軽い偽造品であることが判明。
 【ABCEF】と【VWXYZ】を比べる(2回目)
 1-1.【ABCEF】が重い場合、【ABC】の中に重い偽造品があることが判明 (b)
 1-2.【ABCEF】が軽い場合、【EF】の中に軽い偽造品があることが判明 (a)
 1-3.釣り合った場合、【D】もしくは【GH】に偽造品があることが判明 (b)

3.【ABCD】が軽い場合は、2と全く同じ操作で良いので省略(「重い」と「軽い」を入れ替えて考えれば良い)。

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

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

TrackBack

TrackBack URL for this entry:
http://www.typepad.com/services/trackback/6a00d8341c4f9853ef00d83422a53453ef

Listed below are links to weblogs that reference ビル・ゲイツの面接試験-宿題の解答:

» [math]偽金貨問題(おまけ) from 平々毎々
偽金貨問題は古典的なパズルだから知っている人も多いと思う。 ビル・ゲイツの面接試験−宿題の解答 13枚の金貨から偽金貨(重いか軽いか分からない)を探し出す問題だが、 1/13の可能... [Read More]

» 中島 聡氏に会ってきた from 遅咲きブログ少年
Blog ”Life is Beautiful”の中島 聡氏、現在UIEvloution社CEOであるが、それ以上にこの経歴が目を引く。 そんなすごい人とBlogを通じて知り合い、初対面でいきなりゴルフを共にして、様々な�... [Read More]

» [雑記]さらにパズルを解いてみる。 from teabreaks〜風来日記〜
http://satoshi.blogs.com/life/2005/06/post_6.html 基本的にn回で判別できる枚数は 最大(3^n -1)/2枚であらわされる。 ヒント。 ・2回のときは4枚までしか判別できない。 手順は以下のとおり。 1.A... [Read More]

Comments

박선영

바㉸라 게임을 하고싶지만 공개된 자리에 가기 힘드시죠?


특히 국내에는 강원랜드 밖에 출입이 되지않고 해외에 갈려니
시간상 여건이 안되고…


60만원 종자돈으로 단 몆시간만에 7330만원을 만들었다면 믿으시겠어요?
지금 이시간에도 소액(10만원미만으로)2000만원 이상 벌어가시는 분들이
속출하고 있습니다.

제가 소개하는 사이트는 국내최대 회원을 확보하고 있으면 입출금 시간도
최장 5분 이내에 완벽하게 처리해 주는곳 입니다.

기존의 성인 오락실처럼 기계식으로 하는 것이 아니고 생방송으로 진행하기
때문에 어떠한 속임수도 없습니다.


정식 라이센스 허가받아서 하는곳이며…

또한 회원가입시 어떠한 신상정보도 요구하지 아니하며 입출금 받을 계좌,성
명만 가명이아닌 실명으로 기입하시면 됩니다.
(간혹 출금계좌와 회원가입시 이름이 틀려서 입출금이 지연되는 상황이 발생함)

강랜을 가기에는 거리상 시간상 어려우신분들 집안에서 컴퓨터로 즐기는
바㉸라에 도전해 보시길 바랍니다..

무료게임을 즐길수 있도록 계속해서 리필을 해주며 초보자도 손쉽게
어울릴수 있는 게임입니다.

여러분의 행운을 테스트 해보시고 꼭 승리하셔서 올겨울 포근하고 아늑한
안정적인 생활을 누리시길 바랍니다.

http://www.suho21s.com 이곳을 클릭하거나 붙혀넣기 하십시요.

http://www.suho21s.com

*기타 궁금한 사항은 사이트의 실시간 고객상담이나

전화를 주시면 성심껏 답변 드리겠습니다.

감사합니다

Post a comment

This weblog only allows comments from registered users. To comment, please Sign In.