杯子里的互质数

2008-09-27 09:18赵国瑞
关键词:互质约数正整数

赵国瑞

匈牙利著名数学家保罗·埃杜斯教授,听说有一个叫路易·波沙的少年,聪明过人,擅长解数学题.埃杜斯教授心想,这是一个难得的人才,我要亲自考验考验他.

埃杜斯教授到了波沙的家中,见到了12岁的波沙.教授给他提了个问题:“从1,2,3直到100中任意取出51个数,那么至少有两个数是互质的.你能说出其中的道理吗?”(两个正整数互质,指的是它们没有大于1的公约数,比如4和9)

波沙稍微想了一下,把父母和教授面前的杯子都移到自己的面前.他指着这些杯子说:“这几只杯子就算50个吧.我把1和2这两个数放进第1个杯子,把3和4两个数放进第2个杯子……这样两个两个地往杯子里放,最后把99和100两个数放进第50个杯子里.我这样放可以吧?”

教授点点头说:“可以,当然可以这样放了.”

波沙又说:“因为我要从1到100中挑出51个数,所以至少有一只杯子里的两个数会全部被我挑走,对吧?而这同一只杯子里的两个数是紧挨着的、连续的,两个连续的正整数必然互质.”

埃杜斯教授笑着说:“你的杯子能喝酒、喝咖啡,还能做题,你这可是多用杯呀!”教授几句幽默话,把大家都逗笑了.

埃杜斯教授追问:“为什么相邻的正整数一定互质呢?”

波沙说:“假设a、b为两个相邻的正整数而又不互质(且b>a),那么a和b必存在着大于1的公约数c.于是a=mc,b=nc,m≠n,从而b-a=(n-m)c.所以c一定是b-a的约数.因为b-a=1,故b-a存在大于1的约数是不可能的!因此,两个相邻的正整数必然互质.”

埃杜斯教授夸奖小波沙:“答得很好!”

……

小波沙在解答埃杜斯教授的问题时,使用了两个数学原理:抽屉原理和反证法.

什么是“抽屉原理”呢?

如果将n+1件物体放进n个抽屉里,那么至少有一个抽屉里放着2件或2件以上的物体.

这就是抽屉原理.这个抽屉原理是显而易见的,也几乎是不言自明的.

抽屉原理也叫做“鸽笼原理”或“鞋盒原理”,是数学中经常使用的原理.请看下面的问题:

在一所有400名学生的小学里,会有两个小学生的生日相同吗?

1月1日到12月31日可以看做365(或366)个抽屉,而要把400个人的生日往这365(或366)个抽屉里“放”,那么至少有两个人的生日是在同一个抽屉里,也就是说至少有两个人的生日相同.

当然,这个问题比较简单,直接一说就明白了.如果问题稍微复杂一点,在使用抽屉原理时,就要讲究一些方法了.请看下面的问题:

现有9个人,每个人都有一支红蓝双色圆珠笔.每个人用双色圆珠笔写下“爱科学”三个字,每个字必须用同一种颜色写,各个字的颜色是随意的.试说明其中至少有两个人写字颜色是完全相同的(即所写的每个字的颜色都一样).

如果用0代表红色字,用1代表蓝色字,那么用红蓝两种颜色写“爱科学”三个字,会出现如下8种可能情况:

0,0,0,即红,红,红;1,1,0,即蓝,蓝,红;

1,0,0,即蓝,红,红;1,0,1,即蓝,红,蓝;

0,1,0,即红,蓝,红;0,1,1,即红,蓝,蓝;

0,0,1,即红,红,蓝;1,1,1,即蓝,蓝,蓝.

这8种可能可以看做是8个抽屉.现在有9个人写字,可以看成是要在8个抽屉中装进9件物体.由抽屉原理可知,至少有两个人所写的字的颜色完全相同.

猜你喜欢
互质约数正整数
基于互质阵列的信号波达方向估计算法
关于包含Euler函数φ(n)的一个方程的正整数解
约数词语,不简单
被k(2≤k≤16)整除的正整数的特征
最强大脑
方程xy=yx+1的全部正整数解
Short-range Radar Detection with(M,N)-Coprime Array Configurations
一类一次不定方程的正整数解的新解法
不定方程x2+y2+z2=2(xy+yz+xz)的解及其性质
约数问题(一)