第22章　趣味杂题：比赛、钟表、统筹与称重

1. 淘汰赛与循环赛

单败淘汰赛有 $N$ 支队伍，决出冠军总需 $N-1$ 场比赛，因为每场淘汰一队。轮空只是免赛进入下一轮，不改变总场次。至少轮数为 $\lceil {\log }_{2}N\rceil$，但冠军个人比赛场次受签位影响。

单循环赛 $N$ 队，每队对其他队一次，总场次 $C_N^2=N(N-1)/2$。每队已赛场数可用总度数求和；每场使两支队伍各增加一场。

2. 钟表与快慢表

两表每天分别快 $a$ 分、慢 $b$ 分，相对误差每天增加 $a+b$ 分。要重新显示同一时刻，需累计相对误差达到 12 小时或 24 小时，视题目“显示标准时间”的定义而定。先确定表盘周期，再除以相对误差。

走时快 $r$ 分/小时的表，实际经过 $t$ 小时，表上经过 $t(1+r/60)$ 小时。不要把“快 3 分钟”理解成每小时只显示 60 分钟。

3. 统筹排程

多个任务可并行、部分任务需先后时，画依赖图或甘特图。等待结果期间可做其他任务；在不受额外资源冲突影响时，依赖关系中耗时最长的连续任务链叫关键路径，它决定最早完工时间。可合并的收费、取药等活动只计一次。双机器调度常采用“短任务优先”减少总等待时间，但若目标是最短完工时间，还要均衡两台机器负荷。

资源分配、车间配比题先列整数变量和资源约束，再列成本/天数目标。问“至少多少天”是最小化时间；问“总费用最低”要把工期限制也写进去。

4. 天平称重

每次称重三种结果：左重、右重、平衡，可区分最多 $3^k$ 种状态。若已知假币偏轻，可设计分组称量；若不知道偏轻还是偏重，每枚假币对应两种假设，信息量要求更高。每次称量后都要保证各分支可区分剩余对象。例如已知一枚假币偏轻，58 枚中每次尽量分成三组等量，称两组：若平衡，假币在未称的一组；若不平衡，假币在较轻的一组。每次最多把候选数缩到约三分之一，因为 $3^3=27<58\le 81=3^4$，至少需要 4 次称量。

---