组合数论问题

组合数论问题

组合数论作为数论的一个（小）分支，是研究整数集合的组合性质。与代数数论、解析数论等分支相对应，组合数论的证明与结论更多地带有“离散的、组合的”味道。

例1. （组合数论经典定理）证明：任意2n+1个整数中一定可以找到n个，

其和为n的倍数。

[证：]先证命题的（完全）积性，即

引理：若对于正整数m, n 原命题都成立，则命题对于mn亦成立。 由引理，只需对n=p为素数的情形证明即可。

反证法，设存在2p+1个正整数x1,x2,?,x2p?1使得其中任意p个之和 考察 C2pp?1??(xi?xi???xi)p?1(mopd)

12p

例2．(IMO预选题2008N4).对于整数k?2,证明C22k?1－C22k被2整除但不被23k+1整除.

(2n)!2n(2n?1)!!22n((2n?1)!!)2[证：]利用C===,

n!(n!)2(2n)!n2nkk?13k

C22k?1k－C22kk?122(2?1)!!2((2?1)!!)2(2k?1)!!2kk=－=(－(2?2i?1)(2?(2i?1))). ??kkk(2)!(2)!(2)!i?1i?12k?1i?12k?22k?1i?12kk?12kk22kk?1k?1?(2k?2i?1)－?(2k?(2i?1))=?2(2r?1)k?1S2k?1?(2r?1)≡2

i?1r?12k?1k+1

(2k－1)!!?1(mod 23k+1). 2i?111=?2i?12i?12k?12111k-1

=2. (?)??kk2?(2i?1)i?12i?1i?1(2i?1)(2?(2i?1))2k?1k?1A={1,3,…, 2k－1}是(mod 2k)的缩系,故r -2(r∈A)是r2(r∈A)的置换,因此

211k-1k2≡－≡－=－≡2(mod 2). r(4i(i?1)?1)????k2r(2?r)rr?Ar?Ar?Ai?1k?12k?1k2k?12k由于α2((2)!)==2－1,故α2(C2k?1－C2k)=2k－(2k－1)+k+1+2(k－1)=3k.

2?1k

例3.（2008莫斯科数学奥林匹克） 每个正整数染n色之一,每色都有无穷多个数.已知,任意两个同奇偶的不同数的算术平均值的颜色只由该两数的颜色确定(例如,红色数与蓝色数的平均值总是黄色).

(1).求证,任意两个同奇偶的同色数的平均值必与该两数同色; (2).对哪些n存在这样的染色法?

[证：](1).考虑任一色例如红色.设每两个同奇偶的不同红色数的平均值为X1

色(记作(红,红)→X1),再设(红,X1)→X2,(红,X2)→X3.由于红色数有无穷多个,必有两个a,b(mod 8)同余.可以依次标出下列各数的颜色:

a 红

7a?b 83a?b 45a?3b8

X3 X2 X3

a?b 2X1

3a?5b8

a?3b 4a?7b 8b 红

9b?a 8X3 X2 X3 X3

由此得到(X3,X3)→X1, (X3,X3)→红,故X1=红.

(2).当n为奇数时记n色为0～n―1,每个整数a染a(mod n)色即可. 若对偶数n有符合要求的染色法.设任一色的所有数依递增次序排列为a1,a2,....由于每两个相邻项之间没有该色的数以及每两个同奇偶的同色数的平均值与该两数同色,归纳可证这个数列是公差为奇数的等差数列.

现在设各色数列的公差为d1,…,dn,首项的最大者为a,D=lcm(d1,…,dn).则D个相

nnDD1继正整数a,a+1,…,a+D―1中第i色数的个数是.故有?=D,即?=1.

dii?1dii?1di但左边通分后分母为奇数,分子是偶数个奇数之和,为偶数,矛盾.

因此当且仅当n为奇数时存在这样的染色法.

例4．正n边形的顶点染若干色(每点染一色,至少有2色),已知,每种颜色的所

有点都构成一个正多边形.求证,这些同色多边形中必有2个全等.

[证：]以正n边形的中心作为复平面原点.则正n边形的顶点集为 M={uωt | t=0,1,2,…,n－1} ,其中ω=cos

2?2?+isin. nn反设所有同色多边形互不全等,则它们的边数互不相同,设是k1

Mj={ujωjt | t=0,1,2,…,kj－1} ,其中ωj=cos

2?2?+isin,1?j?r. kjkju和uj都是非零复数(它们的模都等于正n边形的外接圆半径).

k 记S=?z1,Sj=

z?Mz?Mj?zk1,应当有S=?Sj.但根据单位根的性质,

j?1r?(cost?0m?12?2??isin)kt当m?|k时等于0,而m|k时等于m.故S=S2=S3=…=Sr=0, mmkS1=k1u11≠0,得出矛盾.

[注：]此即数论中著名的三角和方法.本题表明,整数集Z划分为若干个互不相交的(双向无穷)等差数列只有这样的方式:Z先划分成d个公差为d的等差数列,然后其中若干个再分别划分成等公差的数列。

本题原为前苏联奥林匹克题，在网络中被评为最难的数学竞赛试题之一。

例5. (中国数学奥林匹克2008冬令营) A是N*的无限子集,给定整数n>1.已知对任意不整除n的素数p,集合A中均有无穷多个元素不被p整除.

[证明：]对任意整数m>1,(m,n)=1.集合A中均存在有限多个互不相同的元素,其和S满足S≡1(mod m)且S≡0(mod n).

证.设m的标准分解式是?pi?,对每个i,记ui=

iki?1m.则(pi?i,uin)=1. ?ipi由已知条件, A中有无穷多个元素不被p1整除.考虑它们的余数组

( r(mod p1?) ,s(mod u1n) ), (r,p1)=1.

1由于只有有限多种不同的余数组,必有无穷多个元素属于同一余数组(r,s).又因ru1n与p1?互素,故存在x∈N*满足同余式 ru1nx≡1(mod p1?).取u1nx个此类元素就

11得到A的u1nx元子集B1,其和S1≡1(mod p1?)且S1≡0(mod u1n).

1?对于A1=A\\B1(由于B1为有限集,A1仍满足题述条件)和p2,u2n同样操作得到

2?A1的有限子集B2,其和S2≡1(mod p2)且S2≡0(mod u2n).

2再令A2=A1\\B2,….依次得到A的k个互不相交的有限子集B1,…,Bk,其和分别满足 Si≡1(mod pi?)且Si≡0(mod uin) (1?i?k).

i最后取B=?Bi,它的和S=?Si.由于每个Si≡0(mod n),故S≡0(mod n).又由于

i?1i?1kk?Si≡δij(mod p?),其中δ=1(若i=j)或0(若i≠j).故对每个i, S≡1(mod piji).合模得到jji

S≡1(mod m).

例6．（2009USAMO）s1,s2,?,是一个无限长的有理数数列且不是每项相等.

t1,t2,?也是一个无限长的有理数数列且不是每项相等,满足对于任意整数i,j,有

(si-sj)(ti-tj)是整数.求证:存在有理数r,使得对于任意整数i,j,均有(si-sj)r为整数

且

(ti-tj)r为整数.

[证：] 对于固定的素数p,及有理数x，记vp(x)为x含p的方幂（可为负整数），及vp(0)???

引理一：vp(x)有如下基本性质：min{vp(x),vp(y)}?vp(x-y), 且若vp(x)?vp(y),则

min{vp(x),vp(y)}?vp(x-y)

引理二：mini,jvp(si?sj)???.

于是可记mini,jvp(si?sj)?s(p)???, mini,jvp(ti?tj)?t(p)???