vol.6 今回は、日本からシリコンバレーにやってきて働いている石塚さんの話（2/2）の中で紹介されている、インタビューに用いられるパズル・クエッションを解いてみた。近い内に必要になるかも知れないので。必要にならないのに越した事はないが。
『競馬トラックが一つあり、競走馬が25匹いる。一度に走れるのは5匹まで。タイムは計測できないとして、一番早い5匹を選ぶには何セット走らせる必要があるか』
僕の答え： １０レース
セットアップ：競走馬を５頭づつ５つのグループに分ける。
レース１－５：グループ毎に走らせ、グループ内で順位をつける。
レース６：各グループで一番早い馬を走らせる。これで、１番早い馬が見つかる。
レース７：レース６で一番早い馬がいたグループの中でその次に早い馬とレース６で一番になれなかった残り４頭を走らせる。これで２番目に早い馬が見つかる。
レース８：レース７で一番早い馬がいたグループの中でその次に早い馬とレース７で一番になれなかった残り４頭を走らせる。これで３番目に早い馬が見つかる。
レース９：レース８で一番早い馬がいたグループの中でその次に早い馬とレース８で一番になれなかった残り４頭を走らせる。これで４番目に早い馬が見つかる。
レース１０：レース９で一番早い馬がいたグループの中でその次に早い馬とレース９で一番になれなかった残り４頭を走らせる。これで５番目に早い馬が見つかる。
だれか僕の答えがあっているか教えて下さい。
Life after reading Startup 
9回まで減らせた。
たぶん、6レースを工夫することで8回までは減らせそうな気がする。
速い馬5匹を探せば良いだけで、速い馬の中での順位は特に求められていないのがミソだと思う。
6レースまで同じ
その後6レースの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匹の馬が候補から外れる。
そして、１位の馬とひとつ繰り上げた馬を入れて第8レースを行う。
この時、8レースの勝者のひとつ前の順位の馬以外が勝った時には1位以外の馬はリストラ出来るので18匹の馬が候補から外れる。
8レースの勝者の馬が2位で同グループのひとつ前の馬が1位の時には1位と2位の馬を残し17匹を候補から外す。
また、同じ事をして第9レースを行うと今度はびり2匹or3匹をリストラすると残りの５匹が該当する馬だと思われる。
実際の順位が
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レースを各グループ３位ぐらいで行うことにより8レースでけりがつかないかなぁって気がするんだけどどうだろう？
Hikaru-san,
回答どうもありがとうございます。一点質問ありです。
Hikaruさんの回答では、２－１の馬は第７レース以降出場してこないが、２－１は１－２，１－３，１－４、と１－５より早いかどうか分らないので、もうひとっ走りしないといけなくない？
2-1は、3-1よりは速いので 1-3より3-1が速いことが証明できた時点で1-3,1-4,1-5よりは早いので問題ない。
2-1と1-2のどちらが早いかはこの方法では分らないけど、この設問だと選ばれた速い馬5匹内の順位は特に聞いていないから問題ないかと。
基本は自分より速い馬が少なくとも5匹以上いる場合、その馬は候補から外すと言う戦略で考えています。
> 2-1は、3-1よりは速いので 1-3より3-1が速いことが証明できた時点で1-3,1-4,1-5よりは早いので問題ない。
１ー３が３－１が速い事をレース９で証明できなかったら、もう一回必要ですよね？どう？