2010年8月13日金曜日

クイズ:12匹のねずみとチーズ

12匹のねずみがいます。この中で一匹だけ変わったねずみがいます。そのねずみは他の11匹の普通のねずみとは違うペースでチーズを食べます。ただ分かっているのは「違う」ペースというだけで、他の11匹より早く食べるか遅く食べるかは分かりません。手元にあるチーズを使ってこの変わったねずみを割り出したいのですが、以下の条件のもと、最低いくつのチーズが必要でしょうか(必要なチーズの数が少なければ少ないほど、良い答えになります)。

ちなみに知られているベストアンサーがあるらしいのですが、私はどうしてその数で割り出せるのか今でも分かりません。私の答えはしばらくしてから投稿しますが、その答えはベストアンサーよりもひとつ余計にチーズを使います。
    ≪条件≫
  • 時計を使ってはいけないので、時間計測はできない。
  • 複数のねずみが、ひとつのチーズに群がってもよい。
  • 手元にあるチーズはどれも同一だが、その形状はいびつで、食べかけの形状からは残り何分の一というような判別はできない。
  • 変わったねずみ以外の11匹の普通のねずみは、みな同じペースでチーズを食べる。
  • 仮に、普通のねずみ11匹の中から2匹 A, B を選び出しそれぞれにひとつずつチーズを与えた場合、A, B は同じタイミングで食べ終わるものと考えてよい。
  • 好きなタイミングでねずみ(or 複数のねずみ)からチーズを取り上げてよい。その取り上げたチーズは食べかけとして再利用してよい。
  • 食べかけのチーズをねずみ(or 複数のねずみ)に与える場合は、それは新しいチーズとしてカウントしなくてよい。

追記:
以下の大事な条件が抜けていました。すみません。
  • ふたつの(もしくはそれ以上の)チーズの大きさが等しいかどうかを、目分量で相対的に比較することはできない。
具体的にはこういうことです。最初に12匹のねずみを4つのグループ (A,B,C) (D,E,F) (G,H,I) (J,K,L) に分けます。そして、それぞれのグループにチーズを与えます(この時点でチーズを4つ使っている)。仮にAが遅いねずみだったとすると、(A,B,C) のグループに食べかけが残り、それ以外のグループは同じタイミングでフィニッシュします。ここから次のステップとして、(A,B,C) の食べかけと同じ「残量の」食べかけを作りたいとしましょう。しかし、次のようなことはできません:(A,B,C) だけを再びひっぱりだしてきて、新しいチーズ#5を与えて同じ残量のたべかけを作る。なぜこれができないかというと、目分量で大きさの相対比較ができないため、いつ彼らにストップをかけていいかわからないからです。すなわち、すでに作られている食べかけチーズを横において、今まさにがりがり削られているチーズ#5の大きさを時々刻々観察し、横の食べかけとそろそろ同じ大きさになったかな、なったかな・・・なった、はいストップ!ということができないということです。もちろん時間計測もできないので、それもうまくいきません。

13 件のコメント:

  1. 4つ・・・?!
    (ただしねずみがチーズを食べるペースは時間の経過によらず一定と仮定)

    返信削除
  2. > Hideki
    そう、それがベストアンサー;)
    どうやってその数字にたどりついたか凄い興味あり!

    返信削除
  3. テニス@ピッツバーグで何回か御世話になった海道です。
    「5」までは分かったのですが、「4」は昨晩丸々使ったのに、まだ、解けていません。

    返信削除
  4. > 海道さん
    ご無沙汰しております!いかがお過ごしですか?現在もピッツバーグにいらっしゃるんですよね。私はもうテニスしないまま一年が経とうとしてます。バリバリテニスしてた学部時代には考えられなかったことですが^^;
    「5」いけましたか!いずれ、私も「5」の解法を別エントリで載せますね。もしも「4」が解けた日にはご教示ください、ぜひ・・・!

    返信削除
  5. ひょんな事から先ほどこの「12匹のねずみとチーズ」の記事を見つけて気になりましたので「4」の回答をコメさせていただきました.(随分時間差はありますが...)

    「4」の僕なりの答え:

    赤組(A,B,C) 青組(D,E,F) 黄組(G,H,I) 緑組(J,K,L)と適当に4つのグループに最初に分けておく(途中でばらけてもわかるように各組のネズミには各組の名前の色マーカをつけておく).
    話を簡単にするために仮に特殊なネズミは赤組のAくんと仮定する.

    (i) 特殊なネズミAくんが早食いの場合

    赤,青,黄,緑の各々にチーズを1個ずつあげる(4個全部最初から消費).特殊なネズミAが含まれる赤組がチーズを食べ終わると同時に, 残りの3組から残ったチーズを同時にとりあげる. 赤組にいるA,B,Cにこの残った3個のチーズ(全部同じ量のはず)をよーいどんで同時に上げて, 一番早いものが早食いのAネズミだとわかる.(中古チーズの消費はカウントされないので,最初に使ったチーズ4個がトータル消費量)

    (ii)特殊なネズミAくんが遅食いの場合

    赤組(A,B,C)と青組(D,E,F) を組を混ぜた赤青組に新品チーズ1個, 黄組(G,H,I)と緑組(J,K,L)を混ぜた黄緑組に新品チーズ1個を与えて(チーズ2個消費),どちらか一方の組がチーズを食べ終わると同時に, もう一方から残ったチーズをとりあげる. 次に, その遅かったチームである赤組か青組のどちらかに特殊ネズミがいるのがわかったので, 今度は赤黄組に新品チーズ1個と青緑組に新品チーズ1個を与えて,一方の組がチーズを食べ終えたらすぐさま遅い方の組からチーズをとりあげる(チーズをさらに2個消費, トータル4個消費). この時残ったチーズは最初にとりあげたチーズと同じ量のはず(なぜならどちらも6匹の普通ネズミからなる組 VS. 5匹の普通ネズミ+1匹の特殊ネズミからなる組 で競争しているから).ここで,この2回の試行でともに遅かったグループに含まれる赤組に特殊ネズミAくんがいる事がわかる.
    2つの試行で残った2つの中古チーズを赤組(A,B,C)の中からランダムに選んだ2匹に与えて速度を比べる. 同時に食べ終えたら, その2匹は同じ速度の普通ネズミであるので, 残り一匹が特殊ネズミのAだとわかる. どちらか一方が早く食べ終われば, 選んだうちの遅い方が特殊ネズミのAという事になる.

    以上です. 間違っていましたら, ご指摘くださいませ.

    返信削除
  6. 何度もコメ書いてしまいすいません.
    遅くても早くても (ii)の方法であれば関係なく特殊ネズミがわかりますので, (i)は忘れて下さい.

    「チーズ4個」の回答

    赤組(A,B,C) 青組(D,E,F) 黄組(G,H,I) 緑組(J,K,L)と適当に4つのグループに最初に分けておく(途中でばらけてもわかるように各組のネズミには各組の名前の色マーカをつけておく).
    話を簡単にするために仮に特殊なネズミは赤組のAくんと仮定する.

    4つのグループを大きく2つのグループに分けて, 異なる組み合わせで新品チーズを1個づつ与えて2回競わせる(トータル4個消費)
    (例 赤青 vs. 黄緑, 赤緑 vs. 黄青)
    2回の試行で,一方のチーズがなくなると同時に遅い方からチーズをすぐに取り上げる. (2回とも同じ量のチーズが残るはず)
    2回の試行から共に??で合った方の組(仮定では赤組)に特殊ネズミがいる事とこの特殊ネズミが??で特殊である事がわかる.
    次に, この特殊ネズミがいるとわかった組(赤組)の中から適当に選んだ2匹のネズミに, 先ほどの2回の試行で残った同量の中古チーズをあげて競わせる.
    同時に食べ終えたら, 残り一匹が特殊ネズミAくんだとわかる. もし, どちらか一方が先ほどの推察からわかった??で食べ終えたらそのネズミが特殊ネズミAくんであるとわかる 

    返信削除
  7. 僕も挑戦していますが、ytokudaさんの場合の「赤青 vs. 黄緑, 赤緑 vs. 黄青」の2回試行して両方とも前者が勝ったとしても、その結果が「赤組が速かったのか」と「黄組が遅かったのか」の判別がつかないと思います。疑似コードを書いてみて、矛盾に気がつきました。

    返信削除
  8. > ytokudaさん
    投稿してくださってありがとうございます!

    私もチーズ4つでの答えが気になっていたので、楽しみにytokuda さんのロジックを追わせていただきました。最初に投稿していただいたときに疑問に思ったのは、最初にねずみ達をグループ分けする際、その分類の仕方が、特殊ネズミが早食いか遅食いかがすでに分かっているという仮定に基づいているという点でした。そこで、しばらく私はつまずいてしまいました。すなわち、赤青組に新品チーズ1個, 黄緑組に新品チーズ1個を与えて実験を始めた結果、特殊ネズミが早食いくんの場合もあるわけです。そうなると、上記のロジックがどう変わってくるか考えておりました。

    そんな折、二度目の投稿をいただいて、またロジックをワンステップずつ追わせていただきました。赤青 vs. 黄緑, 赤緑 vs. 黄青という設定で実験をする。どちらにおいても、遅い方からチーズを取り上げ、最終的に二つの残量の同じチーズを作る。ここまでは理解いたしました。ここで私に浮かんできた疑問は、この時点でどのように特殊ネズミのいるグループをひとつに絞れるかということです。言い換えますと、私にはひとつに絞りきれない理由がありました。仮に、実験結果が以下のようになったとします。
    赤青 vs. 黄緑 → (赤青)食べ残し・(黄緑)間食
    赤緑 vs. 黄青 → (赤緑)食べ残し・(黄青)間食

    遅いネズミが赤にいると仮定すると上記のような結果になります。しかし、早食いのネズミが黄にいても上記と同じ実験結果になると思うのです。二つの異なる仮定が同じ実験結果を生み出すため、その実験結果からどのようにして一意に最初の仮定にたどりつけるかをずっと考えておりました(すなわち、この実験結果からどのように特殊ネズミが早食いか遅食いかを判断し、かつその所属グループを特定するか)。

    実はここでつっかえていたため、その後に続くytokudaさんのロジックについていっておりませんでした。私は何か見落としているでしょうか。あるいは、上記のような疑問があっても、その後に続くytokudaさんのロジックを追えば、最終的にはそれが解決されるでしょうか?もしよろしければ、fill in していただければと思います。

    あと時間を割いて丁寧にアプローチを書いてくださってありがとうございます!

    返信削除
  9. > yuaokiさん
    自分のコメントを投稿した後で、yuaokiさんのコメントに気がつきました。ytokudaさんアプローチについて、私と同じ箇所で疑問を持たれたようですね。まだ疑問を抱えているものの、ytokudaさんのアプローチはとても面白いので、これをヒントに私も自分でもう少し考えてみます。

    返信削除
  10. syukiさま, yuaokiさま

    お騒がせしています, ytokudaです.

    皆様のご指摘の点私も自分のコメを書きながら,
    これじゃ, 早いか遅いかわかってる前提でないと4個では解けない...と思い, 気持ち悪いまま夜な夜な過ごしています.
    こちらも何か進展がありましたら, コメさせていただきますので, 今後ともよろしくお願いします.

    また, こういった解けそうで解けない丁度良い頓知問題がウェブで公開されると, 知らない者同士でもコメを書きながらこんなに盛り上がれる事に新鮮さを感じ, 楽しませて頂いております. googleの問題といい, アメリカの企業の試験はおもしろいものが多いですね. 今後もおもしろい頓知問題がありましたら, どこかに掲示して一緒にディスカッションさせて頂けますと幸いです.
    何はともあれ, とりあえずまずはこのネズミとチーズの問題を解いてすっきりする事が先ですが...

    >>syukiさま,
    一つだけ確認しておきたいのですが,
    チーズの大きさの比較は, どんだけ小さいチーズの残りと大きいチーズの残りであっても肉眼(数値計算以外の方法)では無理という前提なんですよね?

    返信削除
  11. Shintaro Kaido2010年11月4日 5:16

    海道です。
    まだ、納得できるところまで、解いていないのですが、盛り上がっているので、僕もまぜて下さい!

    スタート時点のグルーピングは以下の通りです。

    チーズ1: 1A,1B,1C
    チーズ2: 2A,2B,2C
    チーズ3: 3A,3B,3C
    チーズ4: 4A,4B,4C

    スタート後、ある程度、時間が経ったら、ストップ。
    ここで、グルーピングの変更をします。

    チーズ1: 2A,3B,4C
    チーズ2: 3A,4B,1C
    チーズ3: 4A,1B,2C
    チーズ4: 1A,2B,3C

    再スタート。 チーズが完食される順を記録。

    ケース
    1A遅い: チーズ4>チーズ1>チーズ2=チーズ3 (チーズ2&3が最初になくなる。 次にチーズ1、最後はチーズ4)
    1A早い: チーズ4<チーズ1<チーズ2=チーズ3 (チーズ4が最初になくなり、次に3がなくなる。)
    1B遅い: チーズ3>チーズ1>チーズ2=チーズ4

    これだと、チーズ4つで済みますが、いくつか問題があります。

    問題シナリオ1:

    1.普通のネズミが食べるスピード=毎秒5%と仮定。
    2.変わったネズミ(1Aとする)のスピードは毎秒20%。
    3.実験をスタート。 そしてストップした時点で2秒経過していた(という事にする。)。
    4.この時点では。。
    チーズ1: 20%残っている
    チーズ2: 70%残っている
    チーズ3: 70%残っている
    チーズ4: 70%残っている
    5.グルーピング変更の後、再スタート。
    6.フィニッシュの状況は。。
    チーズ1: 1.33秒で完食
    チーズ2: 4.66秒
    チーズ3: 4.66秒
    チーズ4: 2.33秒

    という事でNG回答になってしまいます。

    グルーピング変更にストップした時点でのチーズの状況 
    が曲者でしょうか。 ストップ時に一番小さいチーズが半分以上、残っていればOKだと思うのですが。

    3. ストップ時=1秒経過。
    4.
    チーズ1: 70%
    チーズ2: 85%
    チーズ3: 85%
    チーズ4: 85%
    6. 
    チーズ1: 4.66秒
    チーズ2&3: 5.66秒
    チーズ4: 2.83秒

    このケースはOKですね。
    後は、この回答がOKになるクライテリアを求める事が残っているのですが、楽しそうなので、不完全ながらポストさせて頂きました。

    返信削除
  12. > ytokudaさん
    >一つだけ確認しておきたいのですが,
    >チーズの大きさの比較は, どんだけ小さいチーズの
    >残りと大きいチーズの残りであっても肉眼(数値計算
    >以外の方法)では無理という前提なんですよね?
    はい、そう理解しています。

    >今後もおもしろい頓知問題がありましたら, どこか
    >に掲示して一緒にディスカッションさせて頂けます
    >と幸いです.
    他にもいろんな頓知問題があると思いますが、私がパズル系で次に読みたいのはこの本ですね(amazon.jpで注文すると送料が高くなるので、おそらく私は原著にあたります)。


    あと、私が就職活動中に使っていたインタビュー練習用サイト CareerCup にもたまに頓知問題が載っています。

    > Kaidoさん
    返信前にロジックを追わせていただく時間をください、すみません^^;

    返信削除
  13. syukiさま

    お世話になっております,
    ytokudaです.

    お忙しい中,ご回答及び興味深い頓知問題関係の貴重な情報ありがとうございました!
    私ももし何か面白い問題を見つけましたら, ご連絡差し上げたいと思います.
    ネズミ問題はまだですが...

    返信削除