赛马问题

  • Post author:
  • Post category:其他



问题:

共计64匹马,8个赛道,在不可计时情况下,选出最快4匹马,最少需要比赛几场?


结论:

若考虑最少场次数,则按照最好情况,需要9场比赛。

方案一:需要10-11场比赛,最好情况10场,最坏情况11场;

方案二:需要9-12场比赛,最好情况9场,最坏情况12场;


方案一

(1)将64匹马分为8组,进行8场小组赛:


排除:各小组内第5-8名

(2)选出各小组第1名进行比赛:

确定:全场第1名

排除:第5-8名整个小组

排除:G2、G3、G4(必定无法进入全场前4名)


保留:B2有可能成为第4名

排除:B3、B4(必定无法进入全场前4名)


保留:E2有可能成为第3-4名,E3有可能成为第4名。

排除:E4(必定无法进入全场前4名)

保留:C2有可能成为第2-4名,C3有可能成为第3-4名,C4有可能成为第4名。


(3)此时,剩余未确定、未排除共计9匹马,选择其中8匹马进行比赛,C4暂不参赛:

最好情况:C3未获得全场前3名位置,则C4必定不是全场前4名,则比赛结束,共计比赛10场;

最坏情况:C2全场第2名,C3全场第3名,则还需要C4与此时全场第4名进行一场比赛,确定最终的全场第4名,共计比赛11场。



方案二:

(1)随机选择8匹马,进行第1场比赛:


排除:第5-8名

(2)随机选择7匹马+上一场第1名,进行第2-9场比赛:

排除:

此时:

若第9场比赛是情况一(最好情况),则直接得出全场前4名,最终比赛9场;

若全程都是情况三(最坏情况),则需要增加3场比赛,得出第2-4名次,最终比赛12场;

加赛方案:

对于全程最坏情况,当第9场比赛结束后,相当于需要在9个已有序的小组内决出前3名,如图所示:

排除:全场第1名,每组后4名,剩余待比赛马匹情况如下,

即问题变为3*9组内有序,选出前3名的问题:

随机选择8组第1名,进行第10场比赛,得到比赛结果和排除情况如下:

此时,除去J3,剩余马匹进行第11场比赛:

若J2未获取第2名,则J3不可能进入前3名,则比赛结束,共计11场;

若J2未获取第2名,则需要J3与当前第3名进行第12场比赛,决出第3名(即全场第4名),共计12场;



版权声明:本文为cuixianlong原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。