一场跑马比赛至多只能有 $8$ 匹马参赛，假设同一匹马参加每一场比赛速度都是一样的．问：$64$ 匹马能否通过不超过 $50$ 场的比赛分出任意两匹马之间的优劣．
【难度】
【出处】
2009年清华大学自主招生试题
【标注】
【答案】
可以
【解析】
首先证明：两个 $8k$ 元有序数组可以通过 $4k-1$ 场比赛将其合并为一个 $16k$ 元有序数组．
我们取出两个数组中各自最快的4元有序组进行比赛，那么至少可以将4个元素定序，然后在两个数组中剩下的元素中继续挑选各自最快的 $4$ 元有序组进行比赛，$\cdots$．于是对于两个小组共 $16k$ 个元素，需要 $4k-1$ 次排序（最后一次8元排序可以将 $8$ 个元素定序）．
于是可以有以下方案：
第一步 将 $64$ 匹马分为 $8$ 组，每组 $8$ 匹，用 $8$ 场比赛分别排序，得到 $8$ 个 $8$ 元有序数组；
第二步 由于用 $3$ 场比赛就可以将2个8元有序数组合并为一个 $16$ 元有序数组，所以可以用 $12$ 场比赛可以得到 $4$ 个 $16$ 元有序数组；
第三步 与第二步类似，可以用 $14$ 场比赛得到 $2$ 个 $32$ 元有序数组；
第四步 与第二步类似，可以用 $15$ 场比赛得到 $1$ 个 $64$ 元有序数组，为所求比赛结果．
这种方案一共需要比赛场数为\[8+12+14+15=49,\]因此 $64$ 匹马可以通过不超过 $50$ 场的比赛分出任意两匹马之间的优劣．
我们取出两个数组中各自最快的4元有序组进行比赛，那么至少可以将4个元素定序，然后在两个数组中剩下的元素中继续挑选各自最快的 $4$ 元有序组进行比赛，$\cdots$．于是对于两个小组共 $16k$ 个元素，需要 $4k-1$ 次排序（最后一次8元排序可以将 $8$ 个元素定序）．
于是可以有以下方案：
这种方案一共需要比赛场数为\[8+12+14+15=49,\]因此 $64$ 匹马可以通过不超过 $50$ 场的比赛分出任意两匹马之间的优劣．
答案
解析
备注
