Math Battle [ 0037: 25頭から1着から3着を確定 ]

[ 0037: 25頭から1着から3着を確定 ]

[ 浅見多絵さんの出題 ]

25 頭の機械式の馬がいます。
これらはあらかじめプログラムされたスピードで走り、
何回走っても常に同じタイムです。

レースは 1 回あたり 5 頭まで。
それぞれのレースではタイムは測りません。着順だけを判定します。
同着はないとします

この条件で全体の 1 着、 2 着、 3 着を特定するには
全部で何レースすればいいでしょう？
意外な発想が必要です。

[ 千手春弥さんの回答 ]

Google の面接試験でしたね。私が自分の会社を起業する直前までいた会社。

まず、全体を 5 頭ずつの 5 グループに分け、それぞれのグループでレースをします。
これで計 5 レース。
それぞれ 1 着の馬を A1, B1, C1, D1, E1 と呼ぶことにします。
次は A1, B1, C1, D1, E1 の 5 頭を走らせます。
これで計 6 レース。
A1 が全体の 1 着だったとします。
次が面白い。 A2, A3, B1, B2, C1 を走らせるわけです。
これら以外に全体の 2 着あるいは 3 着の可能性のある馬はありません。
なぜなのか、考えてください。
これで計 7 レース。
全体の 2 着と 3 着が確定できます。