寻找四人全组合双打乒乓球赛必存全胜或全负选手的简洁证明
寻找四人全组合双打乒乓球赛必存全胜或全负选手的简洁证明
先把问题明确下:四位选手打乒乓球双打,要打完所有可能的2v2组合(总共3场),每场定胜负无平局。我们要证明:要么有一位选手赢下了自己参与的所有3场比赛,要么有一位选手输掉了自己参与的所有3场比赛。
我先说说自己最初想到的偏繁琐的反证思路,再给个更简洁的版本:
原思路(拆解比赛细节版)
假设不存在全胜(3胜)或全负(0胜)的选手,那每个选手的胜场数只能是1或2。每场比赛有2位胜者,3场下来总胜场数是6,所以4位选手的胜场分布只能是 (2,2,1,1)。
设胜2场的是A、B,胜1场的是C、D。首先,A和B组队对阵C、D的这场,他们肯定赢了——不然的话,A、B各自都会输掉这场,那他俩最多只能在剩下的两场里各赢1场,总胜场最多1,和设定矛盾。
接下来看剩下两场:AC vs BD、AD vs BC。如果AC赢了BD,那A拿到第2胜,C拿到唯一胜场;但B在这场输了,他要凑够2胜就必须赢下AD vs BC这场,可这场B和C组队赢的话,C就又多了1胜,变成2胜,和C原本1胜的设定冲突。反过来,如果AC输了BD,那B拿到第2胜,D拿到胜场;A要凑2胜就必须赢AD vs BC,那D又多了1胜,变成2胜,同样矛盾。所以最初的假设不成立,必然存在全胜或全负的选手。
更简洁的计数逻辑版
其实不用拆这么细,用计数+矛盾推导就能搞定:
- 每个选手都会参与3场比赛(和另外3人各搭档一次,对应3场不同的双打组合),所以每个人的胜场数只能是0、1、2、3。
- 假设没有全胜和全负的选手,那所有人胜场都是1或2,设2胜的有x人,1胜的有y人,可得方程组:
- (x + y = 4)(总人数)
- (2x + y = 6)(总胜场数)
解出来是x=2,y=2,也就是胜场分布确实是(2,2,1,1)。
- 现在看两个2胜选手A、B:他俩必定组队赢过C、D(理由和原思路一样,输了的话他俩胜场最多1,矛盾),所以C、D在这场各输1场,而他俩总负场数是2(因为胜1场=负2场),所以还各要输1场。
- 剩下两场里,C要赢1场输1场,D同理。假设C赢了AC vs BD,那D在这场输了,他就必须赢AD vs BC,可这场B会输,导致B的负场数变成2,胜场数只能是1,和B是2胜选手矛盾;反过来也一样,怎么推都会出现矛盾。
所以最初的假设不成立,结论得证。
备注:内容来源于stack exchange,提问作者Alex




