某班有30个学生，每个学生在班内都有相同个数的朋友。朋友是相互的。班里进行了一次测验，结果大家的成绩均不相同。一个学生被称为“好学生”，当且仅当他的朋友中有超过一半(不包括正好一半)的朋友成绩低于他。试问：班里最多有多少“好学生”?
拿到这个问题，我首先想哪些因素能确定好学生数。恩，两个因素：
1.每个学生的朋友数
2.每个人都有哪些朋友
注意到，必须先确定1才能继续分析2。那么，朋友数是多少的时候好学生数可以达到最多呢？这个关系很难看出来。首先，如果这30个学生的集合能够用朋友关系分类，那就好做了。可惜朋友关系不具有传递性，它不是一个等价关系，所以不能分类。
但并不是所有情况都不能分类。当朋友数是1的时候就可以。因为朋友是相互的，这样就两两成了一组，一共15组，此时不论朋友怎么结对都是15个好学生。
这是一种极端的情况。于是我很自然的想到另外一种极端的情况：每个学生的朋友数为29，即整个班的同学彼此之间都是朋友。此时好学生数也是确定的——15个。
两端的情况结果相等，我想会不会是朋友数为15个的时候好学生数会最多。这时，我想先确定朋友数是15个试试看。如何表现出同学之间的朋友关系呢？此时我想到了一种数学工具——图。
用图论的语言重述一下原问题：一个图有30个顶点，分别有权值1,2,3…,30(用权值表示相应学生考试的名次)，每个顶点的度数相同。一个顶点为”好点”当且仅当与它相邻的顶点中有超过一半的顶点权值小于它的权值。问”好点”数最多是多少？
这时，我就可以通过在顶点间连线来确定它们之间的关系了。假设每个顶点的度数为15，我连线…-_-‘无奈这30个学生实在是太多了，要连30*15/2=225条线。想到这里我就崩溃了。况且，即使找到了一种连线方法也不能确定它就是最优的，因为假设朋友数为15本身就站不住脚。
朋友数和好学生数之间到底有着怎样的关系呢？
我在这里被困了很长时间。后来发现自己的思路被局限在对整体的考虑上。当我从个体来考虑问题时，豁然开朗，发现了重要的突破点。
用x表示班里的好学生数，m表示每个人的朋友数。
当m为偶数时，一个好学生要有至少m/2 + 1 个朋友成绩比他差。注意到，好学生所组成的集合是有界的，并且也存在序关系(排名)。所以好学生集合里一定存在一个排名最靠后(成绩最差)的好学生。那么他的朋友中比他成绩差的朋友肯定是”坏学生”(这里我把非好学生简称坏学生)。这样就得到了关系

当m为奇数时，同理可以得到

此外，朋友对的总数为30m/2=15m对。把朋友对中成绩相对较好的学生叫G，相对较差的学生叫B。当m为偶数时，在一个好学生的m个朋友对中，他至少在m/2 + 1 个朋友对中是G，所有的朋友对中 好学生是G的 朋友对的个数应该大于等于(m/2 + 1)x，它应该小于朋友对的总数：

当m为奇数时，同理可以得到

综合奇偶数情况下的条件，我们知道下面两式是肯定成立的

解得

即在下图中，好学生数x一定在两条曲线的下方

可以看出，好学生数一定小于26，而且只有当m=7时才可能取得26。于是我就开始画7个朋友数的情况，但是怎么也画不出只有4个坏学生的情况，甚至5个坏学生的情况都画不出。这时我发觉自己定的界还是不够紧，这个条件还可以再缩紧一些。因为1号(用号表示其排名)的所有朋友对中他都是G，2号至少在m-1个朋友对中是G。当然还可以继续下去，3号至少在m-2个朋友对中是G，不过这时就要保证朋友数m要大于等于2了。而我现在还无法严密的说明朋友数是2的情况好朋友数不能达到最多。于是我就不能进行到3号。这样条件变为解得,。这时第一条线变成了下图中的红线：

看来刚才是白尝试了，好学生数最多就25个，且只能在m=7或m=8或m=9时取得。在m=9的情况下，25个好学生是可以达到的(下图只是一种情况，并不是唯一能够达到25的情况)：

这样，我们证明了25是上界，又证明了25是可以达到的，所以25是上确界。问题也就解决了。
大家可能会好奇上图中为什么我有的线用红色画。仔细观察，我的连线方式是有规律的。每个好学生都与他相邻的8个学生连线(左边4条，右边4条)，再有一条线(红线)连到坏学生那里。当然这样的连法有很多种，我只是找了一种对称的。
一般的来说，已知了朋友数m，我的连线方法如下：
1. 把学生按名次排列围成一圈
2. 确定坏学生数为并令坏学生为排名最后的那几位
3. 每个好学生与其相邻的个学生连线，左边条，右边条。然后剩余的base条线连到坏学生那里
4. 如果第3步进行不下去(每个坏学生的朋友数都已达到m但还不能容纳每个好学生过来的base条线)，那么坏学生数加一，回到第3步。
如果第3步能够进行下去，那么此时的好学生数为最多。若此时坏学生的线数还不够，则在他们之间连线使得每个坏学生的朋友数均为m。
为什么这种连线方法能使好学生数达到最多？直观上看，如果我们想要使好学生数达到最多，每个好学生应该“刚好”成为好学生才行(排名前几的除外)。而上面这种算法达到了这一要求。我一直想严格证明这种算法肯定能使好学生数达到最多，但这几天都没有做出来。希望阅读这篇博客的朋友们能留言给我一些思路。
为什么我把坏学生默认定为排名最后的那几位？
可以证明，只要有坏学生不是排在最后几名的情况，我都可以在不改变其他条件的前提下把它转化为坏学生就是最后几名的情况。也就是说，好学生数能够达到最多的所有情况中，一定存在一种情况使得所有坏学生都排在最后。
假设A与B的排名相邻，A比B成绩好，而A为坏学生，B为好学生。可以证明在不改变其他条件的前提下，把上述情况转化为A为好学生，B为坏学生。
证明：
1. 假设A和B是朋友，如图所示。

A的朋友中，比A排名靠前的有m1个，靠后的有m2 + 1个。B的朋友中比B靠前的有m3 + 1 个，比B靠后的有m4个。假设朋友数为m，此时有m1+m2+1=m3+m4+1=m，m1>m2+1,m3+1<m4。
此时交换A与B的其他的好友(A和B之间仍是好友)，如图所示

交换后，A的好朋友中比A排名靠前的有m3个，靠后的有m4+1个。由于m3+1<m4，所以m3<m4 - 1<m4 + 1，因此A为好学生。同理，B的好朋友中比B排名靠前的有m1+1个，靠后的有m2个。由于m1>m2+1，所以m1+1>m2+2>m2，因此B为坏学生。
2. 假设A与B不是朋友。
此时直接交换A,B的朋友即可，证法与1类似。
有了上面的结论，我们就可以通过下图所示的方式把坏学生都逐次移动到最后。

按照刚才提到的算法，可以求出任意朋友数m所对应的最多好学生数x。程序(ActionScirpt2)如下：

用直方图和杆图表示结果：

另附上m=8,10,11时的连线：

朋友数m=8，好学生数为22。

 
朋友数m=10，好学生数为23。
 

朋友数m=11,好学生数为24。(25不是好学生)

相关日志:

• 有重复组合数
• 零点定理的又一应用
• “不可能”的证明(一)
• 构造一个有趣的函数
• 鸽笼原理的几个应用
• 用另一种函数列构造方法证明Levi定理
• 5人1猴分西瓜
• “不可能”的证明(二)
• 一道趣题
• 17 on 1