赛马问题
问题:共计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场;