Blog Post

36辆车和6个赛道,筛选出最快的3辆车

问题描述:有36辆赛车和6条跑道,没有计时器的前提下,最少用几次比赛可以筛选出最快的3辆赛车?

情况1:不能标记

将36辆车分成6组,每组6辆车,每组分别进行比赛,留下每组的前3名。还有18辆车(6次)

将18辆车分成3组,每组6辆车,每组分别进行比赛,留下每组的前3名。还有9辆车(3次)

从9辆车中选择6辆进行一次比赛,留下前3名。留下的3辆车和没有参加比赛的3辆车,还有6辆车(1次)

最后6辆车比赛选出前3名(1次)

总共6+3+1+1=11次

情况2:可以标记

方法1(8次)

将36辆车分成6组,每组6辆车,每组分别进行比赛,留下每组的前3名,标记。得到A1、A2、A3、...、F1、F2、F3共18辆车(6次)

选择上次比赛每组的第1名进行比赛,得到前3名。A1、B1、C1、D1、E1、F1 ---> D1、A1、E1(假设是这三个,不影响结果)(1次)

上次比赛的第1名D1就是最终的第1名,选择D2、D3、A1、A2、E1(第1名所在分组的2、3名;第2名所在分组的1、2名;第3名所在分组的第1名)共5辆车进行一次比赛,得到前2名,这两辆车和D1组成了最终的结果(1次)

总共6+1+1=8次

方法2(7-10次)

选择6辆车进行一次比赛,得到前3名标记为S1、S2、S3(1次)

剩余的30辆车分成6组,每组有5辆车。每组的5辆车和S3进行比赛。如果每一组中S3都是最快的,结束(6次)

否则,最坏情况下,从上次6组比赛前3名组成的A1、A2、A3、...、F1、F2、F3共18辆车中选择前3名(2次,同方法1)

上次比赛的前3名和S1、S2、S3进行比赛,得到最终的结果(1次)

总共1+6=7(最好)、1+6+2+1=10次(最坏)

方法3(10次)

将36辆车分成6组,每组6辆车,每组分别进行比赛,留下每组的前3名,标记A1、A2、A3、...、F1、F2、F3共18辆车(6次)

每组的第一名进行一次比赛A1、B1、C1、D1、E1、F1留下前3名B1、A1、F1(1次)

第一次比赛每组的第二名进行一次比赛A2、B2、C2、D2、E2、F2留下前2名A2、E2(1次)

第一次比赛每组的第三名进行一次比赛A3、B3、C3、D3、E3、F3留下第1名B3(1次)

B1、A1、F1、A2、E2、B3组成的6辆车,进行1次比赛,得到最终的结果(1次)

总共6+1+1+1+1=10次

所以最快的方法是7次,最稳定又快速的方法是8次。

变形1:有25匹马,5条跑道,选出最快的5匹马

有标记

将25匹马分成5组,每组5匹马,每组分别进行比赛,标记A1、A2、A3、A4、A5、...、E1、E2、E3、E4、E5(5次)

每组的第1名进行比赛A1、B1、C1、D1、E1得到的第1名为最终的第一名,假设为B1(1次,选出1匹)

每组当前的第1名进行比赛A1、B2、C1、D1、E1得到的第1名为最终的第二名(1次,选出2匹)

以此类推,每次比赛都可以选出一匹最快的马。

总共5+1+1+1+1+1=10次

变形2:有38头牛,6条赛道,选出跑的最快的3头牛。

无标记

方法1(13次)

将其中的36头牛分成6组,分别进行比赛,留下前3名,共18头牛,与没有参与比赛的牛总共20头(6次)

将20头牛分成4组,每组5头牛,比赛留下前3名,共12头牛(4次)

将12头牛分成2组,每组6头牛,比赛留下前3名,共6头牛(2次)

剩下的6头牛比赛,得到最终的结果(1次)

总共6+4+2+1=13次

方法2(11次)

从38头牛中随机挑出2头牛,不参与比赛(0次)

从剩下的36头牛中选择跑的最快的3头牛(11次,同情况1)

挑出的2头牛和选出的3头牛比赛,得到最终的结果(1次)

总共11+1=12次

有标记

从38头牛中随机挑出2头牛,不参与比赛(0次)

从剩下的36头牛中选择跑的最快的3头牛(8次,同情况2的方法1)

最终比赛一次,得到结果(1次)

总共8+1=9次