n名乒乓球选手单打比赛若干场后,任意两个选手已赛过的对手恰好都不完全相同,试证明：总可以从中去掉一名选手,而使在余下的选手中,任意两个选手以赛过的对手仍然都不完全相同.

Question

n名乒乓球选手单打比赛若干场后,任意两个选手已赛过的对手恰好都不完全相同,试证明：总可以从中去掉一名选手,而使在余下的选手中,任意两个选手以赛过的对手仍然都不完全相同.

Answer 1

若上述结论不成立,即所有选手都不能去掉.比如若去掉A,则选手B与C对手完全相同,也就是说,选手B与C除A外,赛过的对手一样.于是可从极端情况加以分析.
证明:设选手A是所有参赛选手中比赛场数最多的选手.若不存在可去选手,则A不可去,即若去掉A,则余下必有两名选手对手相同,不妨设为B、C.也就是说,B与C除A外对手完全相同,不妨设B与A赛过而C与A没赛.又因为C也是不可去选手,同理,即若去掉选手C则会有两名选手对手完全相同,不妨设为D和E,其中D与C赛过而E与C没赛过.下面我们来分析选手A与E.
因为选手B与C除对手A外,赛过的对手完全相同,既然选手C与D赛过,那么B与D也赛过,选手D与E除C外对手完全相同,故选手E与B赛过.再看选手A与E,均为与B赛过而与C没赛过的选手.又因为选手B与C的唯一区别就是有且只有一个选手A与B赛过与C没赛过,所以A与E为同一个人,于是与假定中的一条相矛盾,在有有限个选手的比赛中,总可以找到一个选手,其比赛场数大于或等于其他选手.故只能是假定没有可去选手是错误的.即原命题成立