国际数学奥林匹克试题分类解析—A数论_A5整数综合问题.doc

A5 整数综合问题
A5－002 在n×n(n为奇数)的方格表里的每一个方格中，任意填上一个＋1或－1，在每一列的下面写上该列所有数的乘积；在每行的右边写上该行所有数的乘积，证明：这2n个乘积的和不等于0．
【题说】1962年全俄数学奥林匹克八、九年级题5．
【证】设p1，p2，…，pn是各行数字乘积，q1，q2，…，qn是各列数字乘积，它们都是＋1或－1，而应有p1p2…pn＝q1q2…qn，所以p1、p2、…、pn、q1、q2…、qn中应有偶数个－1．设为2k个，则其中＋1的个数为2(n－k)．由于n为奇数，k≠n－k，所以
p1＋p2＋…＋pn＋q1＋q2＋…＋qn≠0
A5－003 已知任意n个整数a1，a2，…，an，由此得到一列新的数．

由这n个数依同样法则又得到一列新数，并如此做下去．假如所有这些新数都是整数，证明原来所给各数ai(i＝1，2，…，n)都相等．
【题说】1964年全俄数学奥林匹克八年级题4．n为偶数时有一种例外情况使结论不成立．
【证】对于任给的n个数xi(1≤i≤n)，如果它们不全相等，那么施行如上运算若干次后得的新数中，最大值要变小，最小值要变大，因此，如若不能得出一组n个相同的数的话，其中最大数不能永远是整数．
假设从一组n个数z1，z2，…，zn得到n个相同的数

那么，当n是奇数时，易知z1＝z2＝…＝zn；当n是偶数时，z1，…，zn中奇数项相等，偶数项相等．
若zi(1≤i≤n)由yi(1≤i≤n)经运算得出，且设

则有 2(y1＋y2＋…＋yn)＝2na
及 2(y2＋y3＋…＋yn＋y1)＝2nb
从而 2na＝2nb，a＝b
由此得出z1＝z2＝…＝zn＝a
因此，我们的命题成立．
仅当n为偶数时，有一种例外情况：n个整数a，b，a，b，…，a，b，(a与b的奇偶性相同，a≠b)满足题中条件，但结论不成立．
A5－004 某整数集合A既含有正整数，也含有负整数，而且如果a和b是它的元素，那么2a和a＋b也是它的元素，证明：集合A包含它的任意两个元素之差．
【题说】1967年匈牙利数学奥林匹克题1．
【证】不难证明：如果整数c是集合A的元素，而n是自然数，那么nc也属于集合A．
因为集合A既含有正整数，也含有负整数，根据最小数原理，集合A存在最小的正整数a和绝对值最小的负整数b．这两个数的和a＋b也应该属于集合A，而且满足不等式．
b＜a＋b＜a
但是集合A不含有小于a的正数和大于b的负数，所以a＋b只能等于0．因此，数0属于集合A，且b＝－a．根据前面所证，集合A包含数a的所有整数倍．
设x∈A，则由带余数除法，存在整数q、r，使x＝qa＋r(0≤r＜a)．于是r＝x＋(－qa)∈A．由于0≤r＜a，必有r＝0．即A中的数均为a的整数倍．
既然集合A的元素都是a的整数倍，因此集合A的任意两个元素之差也是元素a的整数倍，因而属于集合A．
A5－005 证明：任何不大于n！的自然数，都能表示成不多于n个数的和，在这些加数中，没有两个是相同的，而且任何一个都是n！的因数．
【题说】第二届(1968年)全苏数学奥林匹克九年级题5．
【证】对n用数学归纳法，
n＝1时，显然．
设n时结论真．
对a≤(n＋1)！，将a除以n＋1得a＝d(n＋1)＋r，这里d≤n！，0≤r＜n＋1．
由归纳假设，d＝d1＋d2＋…＋dl，l≤n．且所有di是n！的不同因数(i＝1，2，…，l)．
于是 a＝d1(n＋1)＋…＋dl(n＋1)＋r
这个和中的加数不多于n＋1个，其中每一个都是(n＋1)！的因数，且全不相等．

A5－006 找出具有下列性质的所有正整数n：设集合{n，n＋1，n＋2，n＋3，n＋4，n＋5}可以划分成两个无公共元素的非空子集，使得一个子集中所有元素的乘积等于另一子集中所有元素的乘积．
【题说】第十二届(1970年)国际数学奥林匹克题4．本题由捷克斯洛伐克提供．
【解】假定n具有所述性质，那么六个数n，n＋1，n＋2，n＋3，n＋4，n＋5中任一个素因数p必定还整除另一个数(在另一个子集中)．因而p整除这两个数的差，所以p只能为2，3，5．
再考虑数n＋1，n＋2，n＋3，n＋4．它们的素因数不能为5(否则上面的六个数中只有一个被5整除)，因此只能为2与3．这四个数中有两个为连续奇数．它们必须是3的正整数幂(因为没有其它因数)，但这样两个幂的差被3整除，决不能等于2．矛盾！这就说明具有所述性质的n是不存在的．
A5－007 证明：任何一个正的既约真分数m／n可以表示成两两互异的自然数的倒数之和．
【题说】1972年～1973年波兰数学奥林匹克三试题5．
【证】对m用数学归纳法．
m＝1时，显然成立．假设对小于m的自然数命题成立，我们证明它对m＞1也成立．为此，设
n＝qm＋r(0≤r＜m) (1)
因为m／n是正的既约真分数，所以q＞0，r＞0．

又因0＜m－r＜m，所以由归纳假设，

其中t1＜t2＜…＜tk为自然数．
因为n＞m，所以由(3)知：t1＞q＋1，将(3)代入(2)得

所以，命题对任何自然数m都成立．
A5－008 8分和15分的邮票可以无限制地取用．某些邮资额数，例如7分、29分，不能够刚好凑成．求不能凑成的最大额数n，即大于n的额数都能够凑成，并证明你的答案．
【题说】第六届(1974年)加拿大数学奥林匹克题6．
【解】因为
98＝8·1＋15·6
99＝8·3＋15·5
100＝8·5＋15·4
101＝8·7＋15·3
102＝8·9＋15·2
103＝8·11＋15·1
104＝8·13＋15·0
105＝8·0＋15·7
比105大的数，可用以上8数加上8的适当倍数而得到．而97不能用8与15凑成．故所求的n值为97．
【注】一般地，当正整数p、q互质时，不能用p、q凑成的最大整数pq－p－q．
A5－009 若整数n可表示成
n＝a1＋a2＋…＋ak (1)
其中a1，a2，…，ak是满足

的正整数(不一定相异)，那么，我们称n是好数，已知整数33至73是好数，证明：每一个不小于33的整数都是好数．
【题说】第七届(1978年)英国数学奥林匹克题3．
【证】我们改证命题
pn：整数n，n＋1，…，2n＋7都是好数．
已知p33为真．
假设pn成立，那么n是好数，即存在正整数a1，a2，…，ak使(1)、

从而

这表明 2(a1＋a2＋…＋ak)＋4＋4＝2n＋8
2(a1＋a2＋…＋ak)＋3＋6＝2n＋9
也是好数，因此Pn成立．根据数学归纳法，对所有正整数n≥33，Pn成立，原命题因而得证．
A5－010 设f(x)＝x2－x＋1．证明：对任意的m个自然数(m＞1)，f(m)，f(f(m))，…两两互素．
【题说】第十二届(1978年)全苏数学奥林匹克十年级题1．
【证】因f(0)＝1，所以多项式

的常数项pn(0)＝1．
因而，对于任意的整数m，pn(m)除以m，余数等于1．
用m＇＝pk(m)代替m，就得到pn＋k(m)＝pn(m＇)与m＇＝pk(m)互素．
A5－011 自然数n的数字和用S(n)来表示．
(1)是否存在一个自然数n，使得n＋s(n)＝1980；
(2)证明：在任意两个连续的自然数之中，至少有一个能表示成n＋S(n)的形式，其中n为某个自然数．
【题说】第十四届(1980年)全苏数学奥林匹克八年级题6．
【解】(1)当n＝1962时，n＋S(n)＝1980．
(2)令Sn＝n＋S(n)，如果n的末位数字是9，则Sn＋1＜Sn；否则Sn＋1＝Sn＋2．对任意两个连续的自然数m(m≥2)，m＋1，在Sn＜m的n中，选择最大的，并用N表示．这时SN＋1≥m＞SN，所以N的末位数字不是9，从而SN＋1＝SN＋2．由m≤SN＋1＝SN＋2＜m＋2，即得SN＋1＝m或SN＋1＝m＋1．
A5－012 设n为≥2的自然数．证明方程xn＋1＝yn＋1在x与n＋1互质时无正整数解．
【题说】1980年芬兰等四国国际数学竞赛题3．本题由匈牙利提供．
【证】xn＝yn＋1－1＝(y－1)(yn＋yn－1＋…＋1)．如果质数p是y－1与yn＋yn－1＋…＋1的公因数，则p整除xn，从而p是x的因数．但y除以p余1，所以yn＋yn－1＋…＋1除以p与n＋1除以p的余数相同，即n＋1也被p整除，这与x、n＋1互质矛盾．因此y－1与yn＋yn－1＋…＋1互质，从而y－1＝sn，yn＋yn－1＋…＋1＝tn，其中s、t为自然数，st＝x．但yn＜yn＋yn－1＋…＋1＜(y＋1)n，所以yn＋yn－1＋…＋1≠tn，矛盾，原方程无解．
A5－013 设a、b、c是两两互素的正整数，证明：2abc－be－ac－ab是不能表示为xbc＋yac＋zab形式的最大整数(其中x、y、z是非负整数)．
【题说】第二十四届(1983年)国际数学奥林匹克题3．
【证】熟知在a、b互素时，对任意整数n有整数x、y，使ax＋by＝n．当n＞ab－a－b时，首先取0≤x＜b(若x＞b则用x－b、y＋a代替x、y)，我们有
by＝n－ax＞ab－a－b－ax≥ab－a－b－a(b－1)＝－b
所以y＞－1也是非负整数．即n＞ab－a－b时，有非负整数x、y使ax＋by＝n．
因为a、b、c两两互素，所以(bc，ac，ab)＝1．
令(bc，ac)＝d．则(ab，d)＝1，所以方程
abz＋dt＝n (1)
有整数解，并且0≤z＜d(若z＞d则用z－d、t＋ab代替z、t)．
设 bc＝da1，ac＝db1，那么(a1，b1)＝1．在n＞2abc－bc－ca－ab时，

即 t＞a1b1－a1－b1
从而方程 a1x＋b1y＝t (2)
有非负整数解(x，y)．
由(1)与(2)消去t可得
bcx＋acy＋abz＝n
有非负整数解．
另一方面，若有非负整数x、y、z使
2abc－bc－ac－ah＝xbc＋yac＋zab
则 bc(x＋1)＋ac(y＋1)＋ab(z＋1)＝2abc
于是应有，a整除bc(x＋1)，因(a，bc)＝1．所以，a整除x＋1，从而c≤x＋1．同理有，b≤y＋1，c≤z＋1．因此
3abc＝bca＋acb＋abc≤bc(x＋1)
＋ac(y＋1)＋ab(z＋1)＝2abc
由于a、b、c都是正整数，这是不可能的，故2abc－bc－ca－ab不能表成xbc＋yca＋zab(x、y、z为非负整数)的形式．
A5－014 能否选择1983个不同的正整数都不大于105，且其中没有三个正整数是算术级数中的连续项，并证明你的论断．
【题说】第二十四届(1983年)国际数学奥林匹克题5．本题由波兰提供．
【解】考虑三进制表示中，不含数字2并且位数≤11的数所成的集合M．
显然|M|＝211－1＞1983．M中最大的数为

若x、y、z∈M并且x＋z＝2y，则由于2y的各位数字为0或2，所以x＋z的各位数字也为0或2．从而x、z在同一位上的数字同为0或同为2，即x＝z．因此M中任三个互不相同的数不成等差数列．
于是回答是肯定的，M即是一例．
A5－015 将19分成若干个正整数之和，使其积为最大．
【题说】1984年上海市赛一试题2(9)．
【解】由于分法只有有限种，其中必有一种分法，分成的各数的积最大．我们证明这时必有：
(1)分成的正整数只能是2和3．
因为4＝2＋2，且4＝2×2，若分出的数中有4，拆成两个2其积不变；若分出的数中有数a≥5．则只要把a拆成2与a－2，由2(a－2)＞a知道积将增大．
(2)分成的正整数中，2最多两个．
若2至少有3个，则由3＋3＝2＋2＋2及3×3＞2×2×2可知，将3个2换成2个3，积将增大．
所以，将19分成5个3与2个2的和，这些数的积35×22＝972是最大的．
A5－016 设a、b、c、d是奇整数，0＜a＜b＜c＜d，且ad＝bc．证明：如果对某整数k和m有a＋d＝2k和b＋c＝2m，那末a＝1．
【题说】第二十五届(1984年)国际数学奥林匹克题6．
【证】因为a[(a＋d)－(b＋c)]
＝a2＋ad－ab－ac＝a2＋bc－ab－ac＝(a－b)(a－c)＞0
所以a＋d＞b＋c，即2k＞2m，k＞m．
又由ad＝bc，有 a(2k－a)＝b(2m－b)
2m(b－2k－ma)＝b2－a2＝(b＋a)(b－a)
可知2m整除(b＋a)(b－a)．但b＋a和b－a不能都被4整除(因为它们的和是2b，而b是奇数)，所以2m－1必整除b＋a或b－a之一．
因为b＋a＜b＋c＝2m，所以b＋a＝2m－1或b－a＝2m－1．
因为a、b是奇数，它们的公因数也是奇数，且是b＋a和b－a的因数，从而是2m－1的奇因数，即1．所以a与b互质，同理a与c也互质．但由ad＝bc，知a能整除bc，故a＝1．
A5－017 对正整数n≥1的一个划分π，是指将n分成一个或若干个正整数之和，且按非减顺序排列(如n＝4，划分π有1＋1＋1＋1，1＋1＋2，1＋3，2＋2及4共5种)．对任一划分π，定义A(π)为划分π中数1出现的个数；B(π)为π中出现不同的数的个数(如对n＝13的一个划分π：1＋1＋2＋2＋2＋5而言，A(π)＝2，B(π)＝3)．求证：对任意正整数n，其所有划分π的A(π)之和等于B(π)之和．
【题说】第十五届(1986年)美国数学奥林匹克题5．
【证】设p(n)表示n划分的个数．那么第一个位置是1的划分有p(n－1)个，第二个位置上是1的(当然它第一个位置上也是1)的划分有p(n－2)个．等等．第n－1个位置上是1的划分有P(1)＝1个，第n个位置上是1的只有1种．若令P(0)＝1．则所有划分中含1的数A(π)之和等于P(n－1)＋P(n－2)＋…＋P(1)＋P(0)．
另一方面，从含有1的每个划分中拿去一个1，都成为一个(n－1)的划分，共拿去P(n－1)个1．再从含有2的每个划分中拿去一个2，都成为n－2的划分，共拿去P(n－2)个2．…从含有(n－1)的划分(只有一个：1＋(n－1)，拿去(n－1)，即拿去了P(1)＝1个1．再加上含有n的一个划分，n为P(0)＝1个，故B(π)总和也等于P(n－1)＋P(n－2)＋…＋P(1)＋P(0)．
因此，A(π)＝B(π)．
A5－018 在直角坐标系xoy中，点A(x1，y1)和点B(x2，y2)的坐标均为一位正整数．OA与x轴正方向的夹角大于45°，OB与x轴正方向的夹角小于45°，B在x轴上的射影为B＇，A在y轴上的射影为A＇，△OB＇B的面积比△OA＇A的面积大33.5．由x1、

求出所有这样的四位数，并写出求解过程．
【题说】1985年全国联赛二试题1．

＞67．又由于x2、y2均为一位正整数，所以x2y2＝72或x2y2＝81．因为∠BCB＇＜45°，所以x2＞y2．故由x2y2＝72可知x2＝9，y2＝8．此时x1y1＝5．同样可求得x1＝1，y1＝5．
综上可知，1985为符合条件的唯一的四位数．
A5－019 设n、k为互素自然数，0＜k＜n，在集合M＝{1，2，…，n－1｝(n≥3)中的各数，要么着蓝色，要么着白色，已知
(1)对于各i∈M，i和n－i同色；
(2)对于各i∈M，i≠k， i和|i－k|同色．
证明：在M中的所有数均同色．
【题说】第二十六届(1985年)国际数学奥林匹克题2．本题由澳大利亚提供．
【证】设lk＝nql＋rl(l＝1，2，…，n－1；1≤rl≤n－1)．若rl＝rl＇，则(l－l＇)k被n整除，但n、k互素，所以n|(l－l＇)这表明在l＝1，2…，n－1时，r1，r2，…，rn－1互不相同，所以M＝｛r1，r2，…，rn－1｝．
若rl＜n－k，即rl＋k＜n，则rl＋1＝rl＋k，由条件(2)，rl＋1与rl＋1－k＝rl同色．
若rl≥n－k，即rl＋k≥n，则rl＋1＝rl＋k－n，于是rl＋1与k－rl＋1＝n－rl同色．再由条件(1)n－rl与rl同色．
综上所述，ri＋1与rl同色(l＝1，2，…，n－2)，因此M中所有数同色．
A5－020 如n是不小于3的自然数，以f(n)表示不是n的因数的最小自然数(例如f(12)＝5)．如果f(n)≥3，又可作f(f(n))．类似地，如果f(f(n))≥3，又可作f(f(f(n)))

果用Ln表示n的长度，试对任意的自然数n(n≥3)，求Ln并证明你的结论．
【题说】第三届(1988年)全国冬令营赛题6．
【解】很明显，若奇数n≥3，那么f(n)＝2，因此只须讨论n为偶数的情况，我们首先证明，对任何n≥3，f(n)＝ps，这里P是素数，s为正整数．假若不然，若f(n)有两个不同的素因子，这时总可以将f(n)表为f(n)＝ab，其中a、b是大于1的互素的正整数．由f的定义知，a与b都应能整除n，因(a，b)＝1，故ab也应整除n，这与f(n)＝ab矛盾．所以f(n)＝ps．
由此可以得出以下结论：
(1)当n为大于1的奇数时，f(n)＝2，故Ln＝1；
(2)设n为大于2的偶数，如果f(n)＝奇数，那么f(f(n))＝2，这时Ln＝2；如果f(n)＝2s，其中自然数s≥2，那么f(f(n))＝f(2s)＝3，从而f(f(f(n)))＝f(3)＝2，这时Ln＝3．
A5－021 一个正整数，若它的每个质因数都至少是两重的(即在这数的分解式中每个质因数的幂指数都不小于2)，则称该正整数为“漂亮数”．相邻两个正整数皆为“漂亮数”，就称它们是一对“孪生漂亮数”，例如8与9就是一对“孪生漂亮数”．请你再找出两对“孪生漂亮数”来．
【题说】1989年北京市赛高一题5．
【解】设(n，n＋1)是一对“孪生漂亮数”，则4n(n＋1)是漂亮数，并且
4n(n＋1)＋1＝4n2＋4n＋1＝(2n＋1)2
是平方数，而平方数必为漂亮数．
所以，(4n(n＋1)、4n(n＋1)＋1)也是一对“孪生漂亮数”．
于是，取n＝8，得一对“孪生漂亮数”(288，289)．
再取n＝288，得另一对“孪生漂亮数”(332928，332929)．
两个自然数的平方差，则称这个自然数为“智慧数”比如16＝52－32，16就是一个“智慧数”．在自然数列中从1开始数起，试问第1990个“智慧数”是哪个数？并请你说明理由．
【题说】1990年北京市赛高一复赛题4．
【解】显然1不是“智慧数”，而大于1的奇数2k＋1＝(k＋1)2－k2，都是“智慧数”．
4k＝(k＋1)2－(k－1)2
可见大于4且能被4整除的数都是“智慧数”而4不是“智慧数”，由于x2－y2＝(x＋y)(x－y)(其中x、y∈N)，当x，y奇偶性相同时，(x＋y)(x－y)被4整除．当x，y奇偶性相异时，(x＋y)(x－y)为奇数，所以形如4k＋2的数不是“智慧数”
在自然数列中前四个自然数中只有3是“智慧数”．此后每连续四个数中有三个“智慧数”．
由于1989＝3×663，所以2656＝4×664是第1990个“智慧数”．
A5－023 有n(≥2)名选手参加一项为期k天的比赛，每天比赛中，选手的可能得分数为1，2，3，…，n，且没有两人的得分数相同，当k天比赛结束时，发现每名选手的总分都是26分．试确定数对(n，k)的所有可能情况．
【题说】第二十二届(1990年)加拿大数学奥林匹克题1．
【解】所有选手得分总和为
kn(n＋1)/2＝26n，即k(n＋1)＝52
(n，k)取值可以是(3，13)，(12，4)，(25，2)及(51，1)，但最后一种选择不满足要求．
当(n，k)＝(3，13)时，3名选手13天得分配置为(1，2，3)＋2(2，3，1)＋2(3，1，2)＋3(1，3，2)＋2(3，2，1)＋3(2，1，3)＝(26，26，26)．
当(n，k)＝(12，4)时，12名选手4天得分配置为2(1，2，…，11，12)＋2(12，11，…，2，1)＝(26，26，…，26)．
当(n，k)＝(25，2)时，25名选手两天得分配置为(1，2，…，24，25)＋(25，24，…，2，1)＝(26，26，…，26)．
A5－024 设x是一个自然数．若一串自然数x0＝1，x1，x2，…，xt－1，xt＝x，满足xi－1＜xi，xi－1|xi，i＝1，2，…，t．则称{x0，x1，x2，…xt}为x的一条因子链，t为该因子链的长度．T(x)与R(x)分别表示x的最长因子链的长度和最长因子链的条数．
对于x＝5k×31m×1990n(k，m，n是自然数)试求T(x)与R(x)．
【题说】第五届(1990年)全国冬令营赛题2．
【解】设x的质因数分解式为

其中p1、p2、…、pn为互不相同的质数，α1、α2、…、αn为正整数．
由于因子链上，每一项至少比前一项多一个质因数，所以T(x)≤α1＋α2＋…＋αn．
将α1＋α2＋…＋αn个质因数(其中α1个p1，α2个p2，…，αn个pn)依任意顺序排列，每个排列产生一个长为α1＋α2＋…＋αn的因子链(x1为排列的第一项，x2为x1乘排列的第二项，x3为x2乘第三项，…)，因此T(x)＝α1＋α2＋…＋αn，R(x)即排列

对于x＝5k×31m×1990n＝2n×5k＋n×31m×199n，
T(x)＝3n＋k＋m

A5－025 证明：若

则

为整数．
【题说】1990年匈牙利阿拉尼·丹尼尔数学竞赛低年级普通水平题1．
【证】若x＋y＋z＋t＝0，则由题设条件可得

于是此时(1)式的值等于－4．
若x＋y＋z＋t≠0，则

由此可得x＝y＝z＝t．于是(1)式的值等于4．

A5－026 课间休息时，n个学生围着老师坐成一圈做游戏，老师按顺时针方向并按下列规则给学生们发糖：他选择一个学生并给一块糖，隔一个学生给下一个学生一块，再隔2个学生给下一个学生一块，再隔3个学生给下一个学生一块…．试确定n的值，使最后(也许绕许多圈)所有学生每人至少有一块糖．
【题说】1991年亚太地区数学奥林匹克题4．
【解】问题等价于确定正整数n，使同余式
1＋2＋3＋…＋x＝a(modn) (1)
对任意正整数a都有解．
我们证明当且仅当n是2的方幂时，(1)式总有解．
若n不是2的方幂，则n有奇素因数p．
由于1，1＋2，1＋2＋3，…，1＋2＋…＋(p－1)，1＋2＋…＋p至多表示mod p的p－1个剩余类(最后两个数在同一个剩余类中)，所以1＋2＋…＋x也至多表示mod p的p－1个剩余类，从而总有a使1＋2＋…＋x≡a(mod p)无解，这时(1)也无解．
若n＝2k(k≥1)，考察下列各数：
0×1，1×2，2×3，…，(2k－1)2k (2)
设x(x＋1)≡y(y＋1)、(mod 2k＋1)，其中0≤x，y≤2k－1，则
x2－y2＋x－y≡(x－y)(x＋y＋1)≡0(mod 2k＋1)
因为x－y，x＋y＋1中，一个是奇数，一个是偶数，所以x－y≡0(mod2k＋1)或x＋y＋1≡0(mod 2k＋1)
由后者得：
2k＋1≤x＋y＋1≤2k－1＋2k－1＋1＝2k＋1－1
矛盾．故 x≡y(mod 2k＋1)，即x＝y．
因此(2)中的2k个偶数mod 2k＋1互不同余，从而对任意整数a，方程x(x＋1)≡2a(mod 2n)有解，即(1)有解．
A5－027 设S＝{1，2，3，…，280}．求最小的自然数n使得S的每个有n个元素的子集都含有5个两两互素的数．
【题说】第三十二届(1991年)国际数学奥林匹克题3．本题由中国提供．
【解】令Ai＝｛S中一切可被i整除的自然数｝，i＝2，3，5，7．记A＝A2∪A3∪A5∪A7，利用容斥原理，容易算出A中元素的个数是216．由于在A中任取5个数必有两个数在同一个Ai之中，从而他们不互素．于是n≥217．
另一方面，令
B1＝(1和S中的一切素数｝
B2＝(22，32，52，72，112，132｝
B3＝｛2×131，3×89，5×53，7×37，11×23，13×19｝
B4＝｛2×127，3×83，5×47，7×31，11×19，13×17｝
B5＝{2×113，3×79，5×43，7×29，11×17}
B6＝{2×109，3×73，5×41，7×23，11×13}
易知B1中元素的个数为60．令B＝B1∪B2∪B3∪B4∪B5∪B6，则B中元素的个数为88，S－B中元素的个数为192．在S中任取217个数，由于217－192＝25＞4×6，于是存在i(1≤i≤6)，使得这217个数中有5个数在Bi中．显然这5个数是两两互素的，所以n≤217．
于是n＝217．

A5－028 对于每个正整数n，以s(n)表示满足如下条件的最大正整数：对于每个正整数k≤s(n)，n2都可以表示成k个正整数的平方之和．
1．证明：对于每个正整数n≥4，都有s(n)≤n2－14；
2．试找出一个正整数n，使得s(n)＝n2－14；
3．证明：存在无限多个正整数n，使得s(n)＝n2－14．
【题说】第三十三届(1992年)国际数学奥林匹克题6．本题由英国提供．
【解】用反证法证明如下：
假设对某个n≥4，有s(n)≥n2－14，则存在k＝n2－13个正整数a1，a2，…，ak，使得

于是就有

从而

3b＋8c＝13
这表明c＝0或1；但相应的b不为整数，矛盾．
2．每个大于13的正整数m可以表为3b＋8c，其中b、c为非负整数．事实上，若m＝3s＋1，则s≥5，m＝3(s－5)＋2×8．若m＝3s＋2，则s≥4，m＝3(s－2)＋8．

由

即知n2可表为n2－m个平方和，从而n2可表为n2－14，n2－15，…，

对于n＝13，有
n2＝122＋52＝122＋42＋32＝82＋82＋52＋42
由于82可表为4个42的和，42可表为4个22的和，22可表为4个12的和，所以132＝82＋82＋52＋42可表为4，7，10，…，43个平方的和，又由于52＝42＋32，132可表为5，8，11，…，44个平方的和．
由于122可表为4个62的和，62可表为4个32的和，所以132＝122＋42＋32可表为3，6，9，…，33个平方的和．

为18＋2×9＝36，18＋2×12＝42个平方的和．再由42为4个22的和，132也可表为39个平方的和．
综上所述，132可表为1，2，…，44个平方的和．

3．令n＝2k×13．
因为132可表为1，2，…，155个平方的和，22可表为4个平方的和，所以132×22可表为1，2，…，155×4个平方的和，132×24可表为1，2，…，155×42个平方的和，…，n2＝132×22k可表为1，2，…，155×4k个平方的和．

s(n)＝n2－14
A5－029 每个正整数都可以表示成一个或者多个连续正整数的和．试对每个正整数n，求n有多少种不同的方法表示成这样的和．
【题说】第一届(1992年)中国台北数学奥林匹克题2．
【解】设m为n的正的奇因数，m＝nd，则

若(1)的每一项都是正的，则它就是n的一种表示(表成连续正整数的和)．
若(1)式右边有负数与0，则这些负数与它们的相反数抵消(因

以略去，这样剩下的项是连续的正整数，仍然得到n的一种表示，其项数为偶数(例如7＝(－2)＋(－1)＋0＋1＋2＋3＋4＝3＋4)
于是n的每一个正奇因数产生一个表示．
反过来，若n有一个表示，项数为奇数m，则它就是(1)的形式，而m是n的奇因数，若n有一个表示，项数为偶数，最小一项为k＋1，则可将这表示向负的方向“延长”，增加2k＋1项，这些项中有0及±1，±2，…，±k．这样仍成为(1)的形式，项数是n的奇因数．
因此，n的表示法正好是n的正奇因数的个数，如果n的标准分解

A5－030 x、y为正整数，x4＋y4除以x＋y的商是97，求余数．
【题说】1992年日本数学奥林匹克预选赛题7．
【解】由题知x4＋y4＜98(x＋y)，不妨设x≥y，则x4＜98×2x，所以x≤5．
注意到14＝1，24＝16，34＝81，44＝256，54＝625．对x，y∈{1，2，3，4，5}，x4＋y4＞97(x＋y)的仅有54＋44＝881＝(5＋4)×97＋8，所以所求的余数为8．
A5－031 设p＝(a1，a2，…，a17)是1，2，…，17的任一排列，令kp是满足不等式
a1＋a2＋…＋ak＜ak＋1＋…＋a17
的最大下标k，求kp的最大值和最小值，并求所有不同的排列p相应的kp的和．
【题说】1992年捷克和斯洛伐克数学奥林匹克(最后一轮)题1．
【解】若kp≥12，则

这与kp的定义相矛盾，所以kp≤11．
又当p＝(1，2，…，17)时，1＋2＋…＋11＝66＜87＝12＋13＋…＋17，故此时kp＝11．
所以，kp的最大值为11，并且kp的最小值为5，此时p＝(17，16，…，2，1)．
设p＝(a1，a2，…，a17)是1，2，…，17的任一排列，由kp的定义，知

且

但(2)的等号不可能成立，否则

矛盾．所以

由(1)和(3)可知，对排列p＝(a1，a2，…，a17)的反向排列p＇＝(a17，a16，…，a1)，
kp＇＝17－(kp＋2)＋1＝16－kp
所以kp＋kp＇＝16．
于是可把1，2，…，17的17！个不同排列与它的反向排列一一配对．所求之和为

A5－032 确定所有正整数n，使方程
xn＋(2＋x)n＋(2－x)n＝0
有整数解．
【题说】1993年亚太地区数学奥林匹克题4．
【解】显然，n只能为奇数．
当n＝1时，x＝－4．
当n为不小于3的奇数时，方程左边是首项系数为1的非负整系数多项式，常数项是2n＋1，所以它的整数解只能具有－2t的形式，其中t为非负整数．若t＝0，则x＝－1，它不是方程的解；若t＝1，则x＝－2，也不是方程的解；当t≥2时，方程左边＝2n[－2n(t－1)＋(1－2t－1)n＋(1＋2t－1)n]，而－2n(t－1)＋(1－2t－1)n＋(1＋2t－1)n≡2(mod 4)，从而方程左边不等于零．
综上所述，当且仅当n＝1时，原方程有一个整数解x＝－4．
A5－033 每一个大于2的自然数n都可以表示为若干个两两不等的正整数之和．记这些相加数个数的最大值为A(n)，求A(n)．
【题说】1993年德国数学奥林匹克(第一轮)题1．
【解】对任意自然数n(n≥3)，存在自然数m，使

－1)之和，所以A(n)＝m．

A5－034 完全平方数对(a，b)满足：
(1)a和b的十进制表示位数相同；
(2)将b的十进制表示续写在a的十进制表示之后，恰好构成一个新的完全平方数的十进制表示，例如a＝16，b＝81，1681＝412．求证：这样的数对(a，b)有无穷多对．
【题说】1993年德国数学奥林匹克(第一轮)题3．
【证】取a1＝42，a2＝492，…，an＝(5×10n－1－1)2，…；b1＝92，b2＝992，…，bn＝(10n－1)2，…．其中n为正整数．
显然，an，bn均为2n位数，且

＝25×104n－2－103n＋2×102n－2×102n＋1
＝(5×102n－1－10n＋1)2
即对任意正整数n，(an，bn)均满足条件．
A5－035 证明：对于任意整数x，

是一个整数．
【题说】1994年澳大利亚数学奥林匹克一试题2．

由于连续n个整数中必有一个是n的倍数，所以上式为整数．

A5－037 设n＝231·319．n2有多少个小于n，但不能整除n的正整数因子？
【题说】第十三届(1995年)美国数学邀请赛题6．
【解】n2的因子必为2α·3β形，其中0≤α≤62，0≤β≤38．
于是(α，β)是属于图中矩形的格点，显然对I、IV中的格点(α，β)，2α．3β不满足要求(2α·3β|n或2α·3β≥n)，II中任一格点(约定β＝19或α＝31的点属于I或IV，不属于II或III)(α，β)，若2α·3β≥n，则对III中格点(62－α，31－β)，有262－α·331－β＜n．反之，对III中格点(α，β)，若2α·3β≥n，则对II中格点(62－α，31－β)，有262－α·331－β＜n．因此II、III中恰有一半的格点(α，β)，使2α·3β满足要求．即所求的正整数因子个数为
19×31＝589

A5－038 在满足y＜x≤100的有序正整数对(x，y)中，有

【题说】第十三届(1995年)美国数学邀请赛题8．

＝49＋16＋8＋4＋3＋2＋1＋1＋1＝85
A5－039 对于每个正整数n，将n表示成2的非负整数次方的和，令f(n)为正整数n的不同表示法的个数．
如果两个表示法的差别仅在于它们中各个数相加的次序不同，这两个表示法就被视为是相同的．例如，f(4)＝4，因为4恰有下列四种表示法：4；2＋2；2＋1＋1；1＋1＋1＋1．

【题说】第三十八届(1997年)国际数学奥林匹克题6．本题由立陶宛提供．
【证】对于任意一个大于1的奇数n＝2k＋1，n的任一表示中必含一个1．去掉这个1就得到2k的一个表示．反之，给2k的任一表示加上一个1就得到2k＋1的一个表示．这显然是2k＋1和2k的表示之间的一个一一对应．从而有如下递归式：
f(2k＋1)＝f(2k) (1)
对于任意正偶数n＝2k，其表示可以分为两类：含有1的与不含1的．对于前者，去掉一个1就得到2k－1的一个表示；对于后者，将每一项除以2，就得到k的一个表示．这两种变换都是可逆的，从而都是一一对应．于是得到第二个递归式：
f(2k)＝f(2k－1)＋f(k) (2)
(1)、(2)式对于任意k≥1都成立．显然f(1)＝1．定义f(0)＝1，则(1)式对于k＝0也成立．根据(1)、(2)式，函数f是不减的．
由(1)式，可以将(2)式中的f(2