数学奥林匹克题解E组合数学 E1存在性问题081-090.pdf

E1-081能否将1990×1990方格表的每个小方格涂成黑色或

白色，使得关于表的中心对称的方格涂有不同的颜色，并且表的任

意一行及任意一列中黑格和白格都各占一半？

【题说】第二十四届（1990年）全苏数学奥林匹克十年级

题1．

【解】假设能按要求涂色．将黑格记为+1，白格记为-1．将

方格表分成四个995×995的正方形（如图）．因每个正方形含奇

数个方格，故任一正方形各格上的数相加，和不为零．又因关于中

心对称的方格涂有不同颜色．故正方形A与A，A与A各格的数相

1423

加的和均为零．因此，A与A，A与A中各有一个，其中各数之和

1423

为正，不妨设A、A中各数的和为正．这时A∪A中各数之和为正，

1212

但由已知，每行中黑格与白格各占一半．所以前995行各数之和为

零，即A与A中各数之和为零．矛盾！所以，满足要求的涂色法

12

不存在．

E1-082设项链A有珠14颗，B有珠19颗．对奇数n≥1，用

n，n+1，n+2，…，n+32给这33颗珠编号，使每个整数恰用一次，

且相邻之珠编号互素，试证最少有6种可行方法．

【题说】第三届（1993年）澳门数学奥林匹克第二轮题5．

【证】A的珠顺次编为n+k，n+k+1，…，n+k+13．

B的珠顺次编为n+k+14，n+k+15，…，n+32，n，n+1，…，n+k-1，

1≤k≤18．当且仅当

（n+k，n+k+13）=（n+32，n）

=（n+k-1，n+k+14）=1

即（n+k，13）=（n，32）=（n+k-1，15）

=1（*）

时，编号合乎要求．

因为n为奇数，（n，32）=1，显然成立．18个连续值中至少

2个k能使13|n+k，恰有6个能使3|n+k-1，至多4个能使5|十

k-1，故使（*）不成立的至多2+6+4=12个值，即至多有6个值能

使（*）成立．

注：因为连续15个数中有8个数与15互素，连续3个数中必

有一个与15互素（3的倍数与5的倍数至多各1个）．故k的18

个连续值中至少有9个使n+k-1与15互素，故最小有7种可行的

编号法，7是最佳值．令n=99，则恰好只有m=3，6，8，9，11，

14，15这7个数能使（*）成立．

E1-083设N={1，2，3，…}．论证是否存在一个函数f：N

→N使得

f（1）=2

f（f（n））=f（n）+n（对一切n∈N成立）

f（n）＜f（n+1）（对一切n∈N成立）

【题说】第三十四届（1993年）国际数学奥林匹克题5．

n∈N．我们证明f（n）合乎条件．显然f：N→N并且

最后f（f（n））=[α[αn+β]+β]=[αn+β]+[β[α

n+β]+β]

=f（n）+[β[αn+β]+β]

显然αn十β不是整数，于是有

β［αan+β]+β＜β（αn+β）+β十=n+β（β+1）=n+1

β[αn+β]+β＞β（αn+β-1）十β=n+β2