知乎使用者2011-09-21 18:33:05

7次

首先分成5組A，B，C，D，E，賽5場

得到a1，b1，c1，d1，e1，假設a1>b1>c1>d1>e1 （這裡可以改變序號，但不改變次序）

推出a1為第一的馬，d1，e1不可能是前三的馬，所以d1，e1不用參加最後一場。

同時推理出可能是第二第三的馬是：a2，a3，b1，b2，c1 ，（推理理由，有兩匹以上比它快的就自動出局）

然後a2，a3，b1，b2，c1再賽一場，其中前二的馬即是第二，第三的馬。

還要證明

7次是最少的答案，這需要證明6次不可以

。。雖然我可以肯定答案是7次，但是證明的思路整理不好。。

知乎使用者2015-03-03 12:23:37

正確答案： 7 場。

推理過程：

你可以先詢問面試官，「最快」的意思，是不是指比賽時總能贏？在真實情況下並非如此。但倘若你假設， A 在比賽中跑贏了 B ， A 就無可爭議地跑得更快，這就極大地簡化了這道謎題。

面試官會告訴你，這麼想沒有問題，比賽就是為了選出跑得最快的馬。通常，你會下意識地想，至少需要 5 場比賽。任何一匹馬都可能排名前三，所以，你必須讓所有的 25 匹馬都參加比賽。可每次只讓 5 匹馬參賽，少於 5 場比賽沒法讓所有的馬都參賽。

很好。接下來你的結論會是：只有 5 場比賽還不夠。第一輪，把 25 匹馬分為 5 組，每組裡的馬只跑一次，只跟同組的馬匹競爭。一輪比賽結果大概會是這樣：

第一名：「奔騰」

第二名：「北舞」

第三名：「凱速」

第四名：「上將」

第五名：「跳影」

你無法斷定「奔騰」是 25 匹馬裡跑得最快的，甚至無法擔保它能排進前三名。舉個極端情況下的相反例子：其他 4 場比賽中跑得最慢的馬，也可能比「奔騰」跑得快，因為它的速度可能在 25 匹馬裡排第 21 名。

那麼，從這場比賽裡我們是否瞭解到什麼東西呢？當然了。我們瞭解到這 5 匹馬的排名情況。我們還了解到，「上將」和「跳影」可以排除在外了。既然它們在這一輪比賽裡排不進前三，那麼在所有的 25 匹馬裡，它們同樣不可能排進前三。。這個道理，也適用於其他輪比賽裡的第 4 名和第 5 名。每一輪比賽可以排除掉兩匹馬。在第一輪的 5 場比賽中，我們可以刷掉 10 匹馬，留下 15 匹馬競爭前三名。

第二輪，即第 6 場比賽，要測試在最初 5 場比賽中表現出色者。合理的方案是讓 5 匹上一輪比賽的「第一名」對戰。就這麼做吧！讓「奔騰」和其他 4 場比賽的第一名跑一回。結果可能會是這樣：

第一名：「易歌爾」

第二名：「奔騰」

第三名：「終結者」

第四名：「紅朗姆」

第五名：「菲爾拉普」

這一次，我們又可以排除兩匹馬，「紅朗姆」和「菲爾拉普」。從這一次的比賽結果看，它們不可能是 25 匹馬裡的前三名。我們還了解到，「易歌爾」是所有馬裡跑得最快的！如果問題問的只是 25 匹馬裡跑得最快的是誰，那麼答案就是「易歌爾」。

可我們要的是前三名。我們不光可以排除掉「紅朗姆」和「菲爾拉普」，還可以排除掉第一輪比賽中所有敗給它們的馬。敗給它們的馬跑得更慢，而我們又已經知道「紅朗姆」和「菲爾拉普」進不了前三了。

接下來是「奔騰」。從這場最新的比賽結果來看，它有可能是所有馬裡跑得第二快的。但以下可能性仍然存在：第一場比賽排在「奔騰」之後的「北舞」，是所有馬裡跑得第三快的。那麼，最終排名就是「易歌爾」、「奔騰」和「北舞」。第一場比賽中排第三的「凱速」，現在出局了。

「易歌兒」第一次比賽時排在它後頭的第二名和第三名，仍在候選之列。這兩匹馬的速度完全有可能比「奔騰」快，因為它們並沒有比試過。

總之，現在候選名單裡還有 6 匹馬。它們是：本場比賽的前三名；與本場比賽第一名在第一場比賽中獲第二、第三名的兩匹馬；在第一場比賽中僅次於本場比賽第二名的一匹馬。

我們已經知道「易歌兒」是跑得最快的馬，因此，讓它參賽沒有任何意義了，於是就只剩下 5 匹馬。自然，第三輪，我們會讓這 5 匹馬進行第 7 場，也是最後一場比賽。第 7 場比賽的前兩匹馬就是所有 25 匹馬中跑得第二快和第三快的。

總結一下：先進行 5 場資格賽；之後讓資格賽的第一名們進行冠軍爭奪賽，本場比賽的獲勝者就是所有馬裡速度最快的；再對邏輯上仍有資格的 5 匹馬進行最後一場比賽。這次比賽裡的前兩名，就是 25 匹馬裡跑第二和第三快的。

知乎使用者2017-02-09 15:38:58

答案肯定是七次，之前很多人答得都很對了。

所以我打算給七次是最優解一個小證明。

我們要證明的是，需要最多比賽次數最少為七次。

我們知道，比出第一名的最多次數最少也得六次。

仿此，我們證明六次比不出前二名即可。

首先，每次賽跑至少排除掉三匹馬獲得前兩名的可能。

其次，如果每次賽跑中有之前輪次的第一沒有獲得第一，那麼還能多淘汰掉一匹馬，同時這匹馬喪失再以這種方式淘汰其他馬的資格= =

以後一種方式理論上最多額外淘汰五匹馬，但這是不可能總實現的。因為事先比賽流程是確定的，如果前兩名已經排在裡面了，它們是不可能被淘汰的。

這樣就淘汰不了總共18+5匹馬，證明了最少需要七次。

王波2017-02-10 23:13:10

看了大佬們的回答，自己理一下“自己認為”簡單的思路：25匹馬，均分5組，編號a，b，c，d，e組

步驟一：各組組內比賽，比出各自小組第一，記作a1，b1，c1，d1，e1，同理各小組第二記作a2，b2，…………（此步驟進行了5場）

步驟二：a1，b1，c1，d1，e1比賽，比出前三，第一x1，第二y1，第三z1（此步驟進行了1場）

步驟三：易理解沒入選的其他兩小組成員全部淪陷，那麼此時選前三，z1所屬小組後四位沒戲了，y1所屬小組後三位沒戲了，x1所屬小組後兩位沒戲了，此時總決賽第一是x1，第二第三在x2，x3，y1，y2，z1五位中決出，誰第二，誰第三看這場比賽（此步驟進行一場比賽）

綜上5+1+1=7

qu89pe2017-03-01 07:11:35

25匹馬看成25個點，每次比賽在參賽的5匹馬之間引入4條有向邊，1->2->3->4->5，數字表示參賽馬的成績排名。這樣最後能形成一個有向無環圖， 我們需要得到的是前三名的節點a， b， c， 其中a->b->c， 並且c是剩餘節點的祖先。六次比賽（分5組各自比賽，之後後每組的第一名比賽）之後，所有的節點已經連成了一個二叉堆，根節點是第一名。只需要讓左右子堆的頂點和它們的子節點一起再比一次，就能決出2，3名。

如圖所示，紅圈內是第七次比賽的參賽馬匹，綠色表示一個可能的結果和排名。

簡單說明7次的最優性，因為每次比賽引入4條有向邊，25個頂點要形成樹需要24條邊，就至少是6次比賽，但6次比賽甚至都不能確定第二名，因為假如根節點只有一個子節點，就說明根節點本身只參加了一組比賽，它的某個子節點參加了至少兩組比賽，這時候只要改變這個子節點除了和根節點的比賽外另一場比賽的結果，就能破壞樹的結構使之成為polytree，甚至連第一名都沒法決定了。

最後，如果要給25匹馬全部排名的話，就變成了BIBD（Balanced Incomplete Block Design）問題。