题目
一架天平放在科学老师McGregor女士的桌上。天平上有若干砝码,目前天平向右倾。在每个砝码上至少刻有一个学生的名字。每位学生进入教室时,会把所有带有自己名字的砝码移到天平的另一侧。问:是否一定存在一组允许进入的学生,使天平被掀向左侧?
分析
直观分析
把所有可能的学生组合都列出来(包括谁都不放和全部放)。看任意一块砝码,从它上面挑出刻名的一个学生(至少有一个)。在所有学生组合中,恰好一半包含该学生、一半不包含;当包含时这块砝码在一边,不包含时在另一边。因此这块砝码在所有组合里恰好一半时间在左、一半时间在右。对每块砝码都这样算,得到:所有组合的平均结果是天平平衡(左右总重相等)。
现在空集合(谁都不放)使天平向右倾,于是平均为平衡必然意味着存在至少一个组合使天平向左倾。也就是说,确实存在一组学生进来后能把天平掀向左。
(直观要点:对每块砝码用“挑一个名字,把所有组合按是否包含该名字配对”的方法,保证该砝码在所有组合中左右出现次数相等,从而总体平均平衡。)
严格证明
-
记砝码按索引为\(i\),质量为\(w_i\)。初始时每个砝码在左或右一侧;令右侧计为正、左侧计为负,初始符号为\(s_i\)(\(s_i=+1\)表示在右,\(s_i=-1\)表示在左)。初始总差定义为
\[ T(\varnothing)=\sum_i s_i w_i\]
题中给出 \(T(\varnothing)>0\)(初始向右)。
-
每位学生对应一组要翻转的砝码(把这些砝码移到另一侧)。对任意允许进入的学生子集\(X\),记最终的右减左总重为\(T(X)\)。翻转一块砝码相当于把它的符号乘以\(-1\),因此\(T(X)\)可以看成某些砝码符号被翻转后的带符号加权和。
-
为了求所有可能\(X\)的平均值,固定某个砝码\(i\),并从刻名学生中任选一位\(p_i\)。把所有学生子集两两配对:每对为\((Y,\;Y\cup\{p_i\})\)(或等价地,以是否包含\(p_i\)为准配对)。在配对的两个子集中,除\(p_i\)外其它学生选择相同,因此砝码\(i\)在这两个子集中恰好一次在左一次在右,对这两个子集的贡献之和为\(0\)。
解释:固定砝码\(i\),从其刻名中选一个学生\(p_i\)。把所有学生集合分成两类:不包含\(p_i\)的集合\(Y\)和包含\(p_i\)的集合\(Y\cup\{p_i\}\)。每个不包含\(p_i\)的集合\(Y\)都与\(Y\cup\{p_i\}\)配成一对(没有遗漏也没有重复)。在一对中,除了是否放\(p_i\)外其他选择完全相同,因此砝码\(i\)在这两个集合中的位置互为相反——在一个集合中在右,在另一个集合中在左。于是这两个集合里砝码\(i\)对“右减左”的贡献互为相反数(例如\(+w_i\)和\(-w_i\)),和为\(0\)。把所有这样的对加起来,砝码\(i\)在所有集合中的总贡献就是这些对的和,因而为\(0\)。
-
对每一个砝码都按上法配对,得到在所有子集中该砝码总贡献为\(0\)。对所有砝码求和得出:所有学生子集\(X\)的平均\(T(X)\)为\(0\)。
-
但已知\(T(\varnothing)>0\)。如果对所有\(X\)都有\(T(X)\ge0\),则平均值也应为正数,这与第4步平均为\(0\)矛盾。因此存在某个\(X\)使得\(T(X)<0\),即某个允许进入的学生集合会使天平向左倾。
结论:必然存在一组学生,McGregor女士允许他们进来后天平会被掀向左。