我被这个背包吓死，真的会有人喜欢这样设计的包包吗？（有图慎点）

有25匹马，任意两匹马的速度都不同。一次比赛可有不多于5匹马参加。
问：最少需要几次比赛参能选出最快的五匹马？

下面是一个最多使用8次比赛的方法。
第一步：
把25匹马分成5组，每一组有5匹马。每一组赛一次。
不失一般性，假设结果如下。
1A < 1B < 1C < 1D < 1E
2A < 2B < 2C < 2D < 2E
3A < 3B < 3C < 3D < 3E
4A < 4B < 4C < 4D < 4E
5A < 5B < 5C < 5D < 5E

第二步：各组的第二名在一起比赛。不失一般性，假设结果如下
1B < 2B < 3B < 4B < 5B

现在我们可以知道
(1) 1A一定入选
(2) 2D, 2E; 3B, 3C, 3D, 3E; 4B, 4C, 4D, 4E; 5B, 5C, 5D, 5E被淘汰

第三步：1D, 2B, 3A, 4A, 5A比赛。
我们分几种情况考虑。
(a) 1D < 2B < {...}
答案是1A, 1B, 1C, 1D加上min{1E, 2A}
(b) 1D < iA < {...}, i=3, 4, 5
答案是1A, 1B, 1C, 1D加上min{1E, 2A, iA}
(c) 2B < 1D < {...}
答案是1A, 1B, 2A, 2B加上min{1C, 2C}
(d) 2B < iA < {...}, i=3, 4, 5
答案是1A, 1B, 2A, 2B加上min{1C, iA}
(e) iA < jA < kA < {...}, 3 <= i, j, k <= 5
答案是1A, iA 加上 {1B, 1C, 2A, jA, kA}里的前三。

也许有笔误。但是道理应该是对的。

25匹马任意两匹马的速度都不同这个假设太强了
【 在 huaqizhiqing (花旗知青) 的大作中提到: 】
: 有25匹马，任意两匹马的速度都不同。一次比赛可有不多于5匹马参加。
: 问：最少需要几次比赛参能选出最快的五匹马？
: 下面是一个最多使用8次比赛的方法。
: 第一步：
: 把25匹马分成5组，每一组有5匹马。每一组赛一次。
: 不失一般性，假设结果如下。
: 1A < 1B < 1C < 1D < 1E
: 2A < 2B < 2C < 2D < 2E
: 3A < 3B < 3C < 3D < 3E
: 4A < 4B < 4C < 4D < 4E
: ...................

前五名也要排序呢？

最极端情况是第一轮，速度最快5匹马，都在一个组里。

能处理这个情况，就是需要的最小次数。

所以第一轮之后，肯定是从下往上赛的，才能处理

你符号是不是颠倒了

【 在 huaqizhiqing (花旗知青) 的大作中提到: 】
: 有25匹马，任意两匹马的速度都不同。一次比赛可有不多于5匹马参加。
: 问：最少需要几次比赛参能选出最快的五匹马？
: 下面是一个最多使用8次比赛的方法。
: 第一步：
: 把25匹马分成5组，每一组有5匹马。每一组赛一次。
: 不失一般性，假设结果如下。
: 1A < 1B < 1C < 1D < 1E
: 2A < 2B < 2C < 2D < 2E
: 3A < 3B < 3C < 3D < 3E
: 4A < 4B < 4C < 4D < 4E
: ...................

小于啥意思，用的时间，小就是快？
第二步比第二名，看不出哪个第一名能在top 5吧。

不好意思。做排序做惯了。A < B 的意思是A排在B前面。

【 在 cdz (哥哥我不是一般人) 的大作中提到: 】
: 你符号是不是颠倒了

这个假设是我加上的。为了严格起见。
允许同样快应该没有问题吧。但是我没有考虑。

【 在 keystone0504 (金牛) 的大作中提到: 】
: 25匹马任意两匹马的速度都不同这个假设太强了

用第三名比也可以，一次性可以排除一半的点，关键是第三步的讨论，要十分仔细，不能遗漏任何情形。
【 在 huaqizhiqing (花旗知青) 的大作中提到: 】
: 有25匹马，任意两匹马的速度都不同。一次比赛可有不多于5匹马参加。
: 问：最少需要几次比赛参能选出最快的五匹马？
: 下面是一个最多使用8次比赛的方法。
: 第一步：
: 把25匹马分成5组，每一组有5匹马。每一组赛一次。
: 不失一般性，假设结果如下。
: 1A < 1B < 1C < 1D < 1E
: 2A < 2B < 2C < 2D < 2E
: 3A < 3B < 3C < 3D < 3E
: 4A < 4B < 4C < 4D < 4E
: ...................

呵呵。没有太多的空余时间继续做。
这都是免费的啊。呵呵。

【 在 BCQ (不差钱) 的大作中提到: 】
: 前五名也要排序呢？

排序通常符号。越小越好。

假设第六次比赛，1B最快。
1A一定在前五了。

因为1A比5个组的第二名都快。最差也是第5名。

【 在 skyeer (看到你的眼) 的大作中提到: 】
: 小于啥意思，用的时间，小就是快？
: 第二步比第二名，看不出哪个第一名能在top 5吧。

嗯，这个思路是get top5但不排序。

【 在 huaqizhiqing (花旗知青) 的大作中提到: 】
: 排序通常符号。越小越好。
: 假设第六次比赛，1B最快。
: 1A一定在前五了。
: 因为1A比5个组的第二名都快。最差也是第5名。

但是看不出八次是不是最少的
【 在 skyeer (看到你的眼) 的大作中提到: 】
: 嗯，这个思路是get top5但不排序。

用下秒表，五次就行了。

赛6次就可以找到最快的五匹马

赛八次太多了

【 在 huaqizhiqing (花旗知青) 的大作中提到: 】
: 有25匹马，任意两匹马的速度都不同。一次比赛可有不多于5匹马参加。
: 问：最少需要几次比赛参能选出最快的五匹马？
: 下面是一个最多使用8次比赛的方法。
: 第一步：
: 把25匹马分成5组，每一组有5匹马。每一组赛一次。
: 不失一般性，假设结果如下。
: 1A < 1B < 1C < 1D < 1E
: 2A < 2B < 2C < 2D < 2E
: 3A < 3B < 3C < 3D < 3E
: 4A < 4B < 4C < 4D < 4E
: ...................

是的。非常容易证明至少需要7次。

但是要证明至少需要8次好像不是很容易。

【 在 keystone0504 (金牛) 的大作中提到: 】
: 但是看不出八次是不是最少的

其实就是处理最坏情况，最快5匹马第一次就分在一个组里面。

第一轮比完。就从最后5名开始比

最后5名比出第一，这个第一和非本组的第四名的4匹马一起比，本组第四名因为已经比过，不用重复。

就这么倒着来，能处理最快5匹马分在一个组的极端情况，最后需要的次数就是答案

计时就可以了吧。
每匹马跑一次就够了，既然一次只能跑五匹，那一共是五次。
如果同一匹马一会跑得快一会跑慢了，那永远都没结果哈。

类似运动会短跑，八条跑道，几十个人报名，怎么半。
这是个赛制安排的问题。
假设人人速度恒定，计时赛就可以。
实际上使用的是淘汰赛制。但是小组赛是第一名还是头两名还是前四名出线，或者是末位淘汰，是有赛制决定的，有一定的主观因素。
结果是第一名应该是错不了的，但是越往后约不确定，比如说决赛第八名，极大可能不是那
几十个选手中第八快的。

选举制度也是类似的。
这个就不发散了。

回到原题。
最少需要六次比赛，即可以确定跑得最快的五匹马。
办法如下：
任意挑一匹马，这匹马伴跑所有比赛，实际上起到一个参照系的作用，然而不能像时钟一样定量。
剩下24匹，四匹一组，共六组，每次一组加上伴跑马，跑六次。
最理想的情况下，累计有四匹马或者五匹跑得快于伴跑马，此时即可以确定跑得最快的五匹马。

没啥难证的，大不了穷举法。

【 在 huaqizhiqing (花旗知青) 的大作中提到: 】
: 是的。非常容易证明至少需要7次。
: 但是要证明至少需要8次好像不是很容易。

也是6次

【 在 BCQ (不差钱) 的大作中提到: 】
: 前五名也要排序呢？

就看到第二步，就看不下去了。

2D你是怎么排除的？

1A>1B>2B>2C>2D >3B/1C ...这个序列是怎么排除的？

【 在 huaqizhiqing (花旗知青) 的大作中提到: 】
: 有25匹马，任意两匹马的速度都不同。一次比赛可有不多于5匹马参加。
: 问：最少需要几次比赛参能选出最快的五匹马？
: 下面是一个最多使用8次比赛的方法。
: 第一步：
: 把25匹马分成5组，每一组有5匹马。每一组赛一次。
: 不失一般性，假设结果如下。
: 1A < 1B < 1C < 1D < 1E
: 2A < 2B < 2C < 2D < 2E
: 3A < 3B < 3C < 3D < 3E
: 4A < 4B < 4C < 4D < 4E
: ...................

1A < 1B < 2B < 2C < 2D
2A < 2B < 2C < 2D

所以有五匹马（1A, 1B, 2A, 2B, 2C）比2D快。

【 在 today222 (道.道.道) 的大作中提到: 】
: 就看到第二步，就看不下去了。
: 2D你是怎么排除的？
: 1A>1B>2B>2C>2D >3B/1C ...这个序列是怎么排除的？

细节有漏的，但lz似乎是对的，这里第一个我能看懂的8次
lz思路很清晰，都帮我理清思路了
【 在 today222 (道.道.道) 的大作中提到: 】
: 就看到第二步，就看不下去了。
: 2D你是怎么排除的？
: 1A>1B>2B>2C>2D >3B/1C ...这个序列是怎么排除的？

好像是错的。3B不能排除。所以第七次以后还有6个要比。应该是九次。

【 在 huaqizhiqing (花旗知青) 的大作中提到: 】
: 有25匹马，任意两匹马的速度都不同。一次比赛可有不多于5匹马参加。
: 问：最少需要几次比赛参能选出最快的五匹马？
: 下面是一个最多使用8次比赛的方法。
: 第一步：
: 把25匹马分成5组，每一组有5匹马。每一组赛一次。
: 不失一般性，假设结果如下。
: 1A < 1B < 1C < 1D < 1E
: 2A < 2B < 2C < 2D < 2E
: 3A < 3B < 3C < 3D < 3E
: 4A < 4B < 4C < 4D < 4E
: ...................