パズルを解いてみた

vol.6 今回は、日本からシリコンバレーにやってきて働いている石塚さんの話(2/2)の中で紹介されている、インタビューに用いられるパズル・クエッションを解いてみた。近い内に必要になるかも知れないので。必要にならないのに越した事はないが。

『競馬トラックが一つあり、競走馬が25匹いる。一度に走れるのは5匹まで。タイムは計測できないとして、一番早い5匹を選ぶには何セット走らせる必要があるか』

僕の答え: 10レース

セットアップ:競走馬を5頭づつ5つのグループに分ける。
レース1-5:グループ毎に走らせ、グループ内で順位をつける。
レース6:各グループで一番早い馬を走らせる。これで、1番早い馬が見つかる。
レース7:レース6で一番早い馬がいたグループの中でその次に早い馬とレース6で一番になれなかった残り4頭を走らせる。これで2番目に早い馬が見つかる。
レース8:レース7で一番早い馬がいたグループの中でその次に早い馬とレース7で一番になれなかった残り4頭を走らせる。これで3番目に早い馬が見つかる。
レース9:レース8で一番早い馬がいたグループの中でその次に早い馬とレース8で一番になれなかった残り4頭を走らせる。これで4番目に早い馬が見つかる。
レース10:レース9で一番早い馬がいたグループの中でその次に早い馬とレース9で一番になれなかった残り4頭を走らせる。これで5番目に早い馬が見つかる。

だれか僕の答えがあっているか教えて下さい。

Advertisements

4 thoughts on “パズルを解いてみた

  1. 9回まで減らせた。
    たぶん、6レースを工夫することで8回までは減らせそうな気がする。

    速い馬5匹を探せば良いだけで、速い馬の中での順位は特に求められていないのがミソだと思う。

    6レースまで同じ
    その後6レースの1着のいるグループを第1グループ、2着のいるグループを第2グループとタグ付けして、それぞれのグループの順位順にソートするとこんな風になる。
    1) 1,2,3,4,5
    2) 1,2,3,4,5
    3) 1,2,3,4,5
    4) 1,2,3,4,5
    5) 1,2,3,4,5
    )が6レースの順位それぞれの数字は1~5レースの順位。
    んで、6レースの順位を先に持ってきて1~5レースの順位を後ろに持ってきて、それぞれ 1-1(6レース1位グループでのレース1位) や5-1(6レース5位グループでのレース1位)とすると。

    2-5,3-4,3-5,4-3,4-4,4-5,5-2,5-3,5-4,5-5 はリストラ出来るので候補から外す。これで10匹の馬が候補から外れる。
    (なぜならそれらの馬に到達する前に少なくとも5匹のそれより速い馬が存在するから)
    という事で、1-5,2-4,3-3,4-2,5-1 で7レース目を始める。
    このレースで1位以外の馬はリストラ対象になるので1位以外の馬は消える。これで、14匹の馬が候補から外れる。
    そして、1位の馬とひとつ繰り上げた馬を入れて第8レースを行う。
    この時、8レースの勝者のひとつ前の順位の馬以外が勝った時には1位以外の馬はリストラ出来るので18匹の馬が候補から外れる。
    8レースの勝者の馬が2位で同グループのひとつ前の馬が1位の時には1位と2位の馬を残し17匹を候補から外す。
    また、同じ事をして第9レースを行うと今度はびり2匹or3匹をリストラすると残りの5匹が該当する馬だと思われる。

    実際の順位が
    01,02,06,07,25
    03,08,10,16,20
    04,05,11,23,24
    09,12,13,19,21
    14,15,17,18,22
    だったとき
    第7レースで勝つのは3-3
    第8レースは1-4,2-3,3-3,3-4,4-1でレースを行う。
    勝つのは3-2
    第9レースは1-3,2-2,3-1,3-2,1-2 でレースを行う。
    1-2,3-1,3-2,1-3,2-2 の順位なので1-3 と2-2を候補から外して1-1,2-1,1-2,3-1,3-2を速い馬5匹と選出できる。

    が、成立すると思うけどどう?

    第6レースを各グループ3位ぐらいで行うことにより8レースでけりがつかないかなぁって気がするんだけどどうだろう?

  2. Hikaru-san,
    回答どうもありがとうございます。一点質問ありです。
    Hikaruさんの回答では、2-1の馬は第7レース以降出場してこないが、2-1は1-2,1-3,1-4、と1-5より早いかどうか分らないので、もうひとっ走りしないといけなくない?

  3. 2-1は、3-1よりは速いので 1-3より3-1が速いことが証明できた時点で1-3,1-4,1-5よりは早いので問題ない。
    2-1と1-2のどちらが早いかはこの方法では分らないけど、この設問だと選ばれた速い馬5匹内の順位は特に聞いていないから問題ないかと。
    基本は自分より速い馬が少なくとも5匹以上いる場合、その馬は候補から外すと言う戦略で考えています。

  4. > 2-1は、3-1よりは速いので 1-3より3-1が速いことが証明できた時点で1-3,1-4,1-5よりは早いので問題ない。

    1ー3が3-1が速い事をレース9で証明できなかったら、もう一回必要ですよね?どう?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s