【做数学题时间到了】数学竞赛题：好学生

yogibear

理科实验班共30名学生，每一名学生在班内均有同样多的朋友（朋友是相互的）。在一次考试中，任意两名学生的成绩互不相同。如果一个学生的所有朋友中，有超过一半朋友的成绩低于该学生，则称该学生为“好学生”。

试问：“好学生”最多可能有多少个？证明你的结论。

flywater

好难……

spirithand

遐想结果为14个

spirithand

每个人都有29个朋友，30个人成绩都不相同，且任意两名学生的成绩也不相同，则排名前15的学生符合要求。

此结果为瞎想，没经过严格证明

imsea

是啊，如果每个人只有一个朋友，自己的成绩比朋友高，那么就有15个好学生，
再引用4楼的结论：每个人都有29个朋友，30个人成绩都不相同，且任意两名学生的成绩也不相同，则排名前15的学生符合要求
……………………

发现自己只能想到这里了，往后就没有具体的思路了

afire

有多少两道杠以上干部或者有多少一等奖学金获得者就有多少好孩子。

w0017

不是第一名，称什么好学生？

当然，理想的情况下，第一名也不是好学生，只要它的好友数等于0
所以成绩跟好学生是两码事，想当好学生，你就得先在班里混得开

[ Edited by  w0017 on 2007-12-9 15:48 ]

imsea

从数学变成政治了

yogibear

QUOTE:

Posted by imsea on 2007-12-9 15:51
从数学变成政治了

明白了。。。专门网的都是好学生。。。

尼伯龙根

熊熊是班主任

l_etoile

这题应该可以看成：取得朋友子集，因为每个子集的模相同，所以模必须为1，2，5，6，10，15，30。然后就简单了，如果每个子集的模为1，也就是没有朋友，与题不符，如果为2的话，一共有15个子集，好学生最多为15个，如果为3个话，每个人有2个朋友，只要比其中一个成绩好即为好学生，每人的所以每个子集可以有2个好学生，一共10个子集，也就是20个好学生，以此类推。。，最后应该答案应该是20的，其实可以用optimisation里的定理来证（大学里学过），不过还是解释比较简单

afire

楼上数学达人啊.

俺数学根本没学透。

很好，很强大！

设共有x个好学生，每个学生有k个朋友。班上最好的学生，在k个“朋友对”中都是成绩好的，而其余每个“好学生”则都至少在 个“朋友对”中是成绩好的，因此“好学生”们至少一共在 个“朋友对”中是成绩好的。这个数目不会超过这班内的“朋友对”总数，即 。由此可得x≤28×kk+1 +1       ①
  另一方面，班内比最差的“好学生”成绩还差的学生不多于 个，因此，又有                                       ②
①的右边是k的增函数，而②等价于                  ③
综合①，③可得x≤28×59–2x60–2x +1：，即            ④
满足④和条件 的最大整数为 ，所以好学生的个数不超过25。下证明可以取到25。
   将全班成绩由好到坏编号为 ，将这些号码列成一张 的数表（如图）
1        2        3        4        5
6        7        8        9        10
11        12        13        14        15
16        17        18        19        20
21        22        23        24        25
26        27        28        29        30
假定某两个学生是一对朋友，只要他们的号码在表中属于如下3种情况：（1）处于相邻的行，但位于不同列；
（2）处于同一列，其中一者位于最下端的行中；
（3）同在最上面一行中。
不难验证，上述情形均满足。故所求答案为25。

很好，很强大！

QUOTE:

Posted by l_etoile on 2007-12-9 19:13
这题应该可以看成：取得朋友子集，因为每个子集的模相同，所以模必须为1，2，5，6，10，15，30。然后就简单了，如果每个子集的模为1，也就是没有朋友，与题不符，如果为2的话，一共有15个子集，好学生最多为15个 ...

看起来还真像那么回事

croclly

原来应该会，现在嘛，还真不懂，没事不研究这个，费脑子

l_etoile

嗯，确实没有考虑周全，题目也没看清。。。（没说1个人只能在一个朋友子集里），那样的话1个人在1个朋友圈里不是好学生，但是在另外一个圈里可能是好学生，数学退化啊。。。不过我只算出了22个，ls的推论的2个constraint没看懂，汗一个。。。第一和第2个里面好像都少打了

deutsch-zh

如果每人有2个朋友:

将30 学生从好到坏排成环型
1,2,3,4,5,.....28,29,30
每个人都与相邻的人做朋友: 即
第1组 > 2 与 1, 3
第2组>3 与 2, 4
第3组>4 与 3, 5
...
...

第28组>29与 28, 30
第29组>30与 29, 1
第30组> 1与 30,2
可看到 1 至 28号同学可在1 至 28组中成为好学生. 共28位好学生

sokoo

*.*lll *.*lll 疯ing,忘到姥姥家乐

lotuis

25个

deutsch-zh

证明在哪里

能说明deutsch-zh 的28个的解哪里错了

RXJWAN

理科实验班里的都是好学生

8610

谁刨坟来着？肯定不是好学生。。。

dimsage

恩
我说说我的思路
找一个什么几何模型， 先把这个问题解决了：理科实验班共30名学生，每一名学生在班内均有同样多的朋友（朋友是相互的）。

dimsage

我觉得用简单多面体的欧拉定理能够解决
思想不够成熟，楼下继续

[ Edited by  dimsage on 2008-2-21 22:34 ]