2008-09-07 3:29| 
11 Comments | 本文内容遵从n个人中每两个人之间都进行过一次比赛。假设比赛不可能出现平局。证明，一定能找出这样的一个人，对于其它任何一人p，他击败了p或者击败了某个打败了p的人。
一句话证明：赢的次数最多的那个人显然满足我们的条件。反证，假设被他打败的所有人的集合为P，万一有个人既没有输给他，也没有输给P里面的任何一人，那这个人至少赢了|P|+1次，成了获胜次数更多的人，矛盾。我故意在这里多写一句话，目的是想说明前面的空白有多短。在Ctrl+A之前，不妨试试看自己能否想到如此简单的证明。
来源：http://www.cut-the-knot.org/arithmetic/combinatorics/RoundRobinTournament.shtml
顺便说两件事情。
网友yuye_abc建议我搞一个wap浏览插件。其实没有必要，大家直接去wap.feedsky.com/matrix67就可以了。
网友hetong_007留言说NOI专刊引用了我两篇文章？求详情。依然欢迎大家在自己的文章里引用我Blog上的东西。
我在第一时间就想到了反证法.
妙。但为什么“赢的次数最多的那个人显然满足我们的条件”？
如何能证明这一点，就已经证明了原命题，再使用反证法就纯属多余了。
如果能证明这一点，就已经证明了原命题，再使用反证法就纯属多余了。
学东西
这个问题我们在杭州培训的时候也说过了……徐世英老师说的
还有一个问：不能有两个冠军
关于NOI专刊的介绍（其实我觉得M牛应该知道的）：http://www.lsjks.net/rdqy/ShowArticle.asp?ArticleID=227
这一期有两位OIBH上的牛分别写了两篇文章。
一篇是讲离散化的：http://www.matrix67.com/blog/archives/108
另外一篇是讲对称/回文的——07模拟赛的Problem 2: gift
送给MM的生日礼物
引用指的是两个OIBHer的文章分别包括了你的两道题和离散化那篇的原文解释。
原来你不知道的啊……Orz……
NOI专刊只是引用了两道题目……
orz
拜一下~
他打败了所有人不然就有一来一回，他打败了P也被某人打败。我的看法。
我想的是数学归纳法
对于1个人,显然成立
假设对于n个人成立，并且找到了那个人A
对于n+1人,新来的那人为B
若A胜B,则A满足条件
否则,B满足条件
所以对n+1人也成立
所以对一切n都成立