Question

求解答： 高中数学竞赛的两道基础训练题。

圣诞节快乐！
1.求证：任意9个整数中，必有5个整数的和被5整除。
加强命题：设N为一质数，则在任意2N-1个数中，必存在N个数的和被N整除。
更一般地，设N为自然数，若在任意2N-1个数中，必存在N个数的和被N整除，则称N为奇异数。求证：所有自然数都是奇异数。

2.给定自然数N，已知自然数K有如下性质：若N阶简单图G中，任何K个点中都至少有一个点与该K点组中其他K-1个点都相连，则G中必有一个点与G中其他所有顶点相连。求K的所有可能值。

Answer 1

第一题太难了。是一个经典的定理。我说我怎么有点印象。
这个定理属于高维东。
我找到了，照抄给大家。
首先，证明对素数P成立。
若有反例a1 a2 ……an
任取p个，做和（x1+x2+……+xp）≠0（mop p）
则由费尔马小定理，（x1+x2+……+xp）^(p-1)=1（mop p）
跑遍求和，

∑（x1+x2+……+xp）^(p-1)=∑1（mop p）
右=C（2p-1,p）≡(2p-1)!/[(p!)（p-1）!]≡1（mod p）
(把p约掉，用Wilson定理)
左边等于什么呢？其中的某一项（以p=13为例）如
a1^2*a2^5*a3^4*a4（m个项，幂数分为k1,k2,……,km）
共展开于若干个(α)括号，每个括号提供若干(β)项，一共就是
αβ=C（2p-1-m,p-m）*β。那个C什么什么的一定能被P整除。不是吗？写写就知道了。
于是左边的∑是0（mod p）,和右边为1矛盾。
对P就证明完了。

假如A，B都被证明满足奇异条件。
对于2AB-1个数{x_n}，从中抽出A个，做和A1为A的倍数；再抽出A个，和也要求是A的倍数A2；一直可以得到2B-1组。（这样最后留下了孤零零的A-1个数）
看看A1,A2,……A_(2B-1)这2B-1个数，自然可以抽出B个，使其和为B的倍数。
这些数对应的x就是AB个数{x_l}，其和为A的倍数之后，还是B得倍数。
这样就证明了该命题。

2.我估计我能写出证明了。刨去K=2和K=N这两个平凡解。
两点间有连线，就连红线；无连线，就连蓝线。

对于某个(N,K)，这样考虑，假如有反例，就是K个点内的小组织很团结，但是N点不团结，我们就考察这个反例，刨去它。
求所有有反例的K即可。
对某个反例图G0，必然有，N个点每个点都有蓝线射出，但是任何一个K点小组织都很红很团结。
G0如果适当的删去一些蓝线换成红线，得到的G也必定是反例。
如何删得干净点呢？
点x1和x2有蓝线相连，把这两点记作一个整体B2。若其他点和B2无蓝线相连，就称B2为x1出发的扩张完毕。若有x3与B2有连蓝线，则x1 x2 x3就是B3；依此扩张至不能再扩张为止。这个B内包含m个点，m-1条蓝线。称这种图形叫“路”。路是不是很像烃？
然后再在剩下的点中选一个扩张中心，再次扩张，得到一个扩张完毕的路C。
D，E……
记得到蓝线系统被缩编为路A1,A2，……,As。（按成员多少从大到小排列）
我们要证明，这样的缩编，对某些K，总有“蓝倾”的不太红不太团结的K点小组。（就是说，反例是不成立的——很拗口很搞脑子= =！）
以上是准备工作。对N为奇数时，A1不小于3

若图G是反例G0（N,K）缩编的结果。
K是W=As+As-1+……+Ar——呔！不能再加了，加一个就超了（或到了）时

若K>W+1=W+w，则As+As-1+……+Ar再在A1中抽前w个点，这些点就是刚好K个，而且每个点在小组内都有蓝线射出。
若K=W+1,适当构造仍有反例。可以自己试试。如果你领会这个证明的精神。（若As=2……若否……）
说明对N位奇数，举不出反例。

思路相同，对于n为偶数,对反例，一样有A1,A2，……,As
如果大家都是2就有好戏看了，是不是？我们证明它。

1）若A1>=3则如奇数情形讨论，不存在这样的反例。
2）若A1=2
就是说，x1x2 x3x4 x5x6 ……抱对。
此时对K为偶数一样，“反例”可以轻易推翻。
对K位奇数，不难证明，此时恰好是成立的反例。

综上所述，对N为奇数，K可以取遍2到N；对N为偶数，K为2到N间的偶数。
应该不错。

Answer 2

不会，我才初二。