小学二年级的数学题

isee

题：9 辆赛车的速度各不相同，它们要比快慢，但没有计时工具，只能在赛道上比谁先谁后，而每次最多有 3 辆赛车比赛，那么，最少比______次，能保证选出跑得最快的 2 辆赛车.

战巡

应该5次可以了

先分$a,b,c$这3组，各自比，得到的结果，假设为
\[a_1>a_2>a_3\]
\[b_1>b_2>b_3\]
\[c_1>c_2>c_3\]
这里用“$>$”表示更快

第四场由$a_1,b_1,c_1$比，最快的肯定为全部9辆中最快的，而次快的，作为第二名的候选，第三的直接淘汰
比如这里假设结果为$a_1>b_1>c_1$，那么$a_1$肯定为最快的，$b_1$将作为第二名的候选，$c_1$直接淘汰

注意第二名的候选，此时还有各组的第二名，但前面已经比过知道会有$b_1>b_2$，因此$b_2$是肯定要淘汰的，而且由于$c_1$已经淘汰，作为比$c_1$更慢的$c_2$更加没戏，最后一场，只需要$b_1,a_2$去比即可，赢家即为全场第二名

isee

战巡 发表于 2022-6-14 19:37
应该5次可以了

先分$a,b,c$这3组，各自比，得到的结果，假设为

小学二年级的题写这里就打住了.

不过，（由于我看了李永乐的视频），我知道李永乐说卡的地方是说：还需要证明 4 次不一定可以.
从而最少是 5 次.

Czhang271828

下面证明不存在确保四次可以的策略.

下面文字之所以很长, 是因为我尽量在用自然语言讲解一个思路, 相信这个思路是很简单的.

Step I. 把 $9$ 辆赛车看成 $9$ 个点 $\{v_i\}_{i=1}^9$, 定义一张有向的完全图 $\Gamma$, 规则如是: $v_i$ 到 $v_j$ 有边相连当且仅当 $i\neq j$, 边定向为 $i\to j$ 当且仅当 $v_i$ 比 $v_j$ 快. 初始情况是这个有向完全图 $K_9$ 的各边定向均未知, 目标是找到最长 path 上的第二个点. (估计读者可以领会以上未加具体阐释的名词.)

Step II. 三辆车比完一次赛相当于提取三个点 $\{v_i,v_j,v_k\}$ 诱导的子图 (三角形) 中三条边的定向. 我们发现这里最慢的点是没用的, 因此和最慢点相连的边是无效信息, 有效信息就是较快两点间的边的定向.

Step III. 比完四场赛后, 我们相当于在 $\Gamma$ 中删去了 $\{v_{\sigma(l)}\}_{l=1}^4$, $\sigma$ 是某一置换. 同时 $\{v_{\sigma(l)}\}_{l=5}^9$ 诱导的子图 $K_5$ 中至多有四条边的定向被提取出来.

Step IV. 实际上, 我们永远无法确保留在 $K_5$ 中的有效信息是 $4$ 条. 因为 $K_5$ 中的某些点至少会参加两次比赛, 从而总可能出现 "某次比赛决出的较快点在下一次比赛中被删除" 之可能性, 其中蕴含 "包含有效信息的边被删除". 因此, 没有策略可以确保留在 $K_5$ 中的有效信息一定是 $4$ 条!

关于 Step IV. 的补充: 如果上述解释不够显然, 那么我们穷举.

Case I. 若第一次比较 $\{v_1,v_2,v_3\}$, 第二次比较包含 $\{v_1,v_2,v_3\}$ 中的较快点 $v_k$, 则可能出现 $v_k$ 在第二次被淘汰之可能性.

Case II. 若第一次比较 $\{v_1,v_2,v_3\}$, 第二次比较 $\{v_4,v_5,v_6\}$, 第三次比较包含前两次决出的四个较快点的其中一者 $v_s$, 则可能出现 $v_s$ 在第三次被淘汰之可能性.

Case III. 若第一次比较 $\{v_1,v_2,v_3\}$, 第二次比较 $\{v_4,v_5,v_6\}$, 第三次比较 $\{v_7,v_8,v_9\}$, 则三条有效信息无法被 $K_5$ 包含 (涉及六个点), 从而至少一条有效信息被淘汰.

Step V. 但凡告诉你上述 $K_5$ 中的 $3$ 条边的指向, 你永远找不到第二快的点. 这是显然的: 因为 $5$ 个点被 $3$ 条边相连总是有多余一个连通分支, 从而无法全局比较!