猴子分苹果问题
兰亭序歌词-
已经知道了整系数方程
ax
< br>by
c
(
a
,
b
互质
)
的一个解
x
0
p
,
y
q
,
那么我
0
们就能知道它的全部整数解。
事实
上，如果
x
,
y
是已知方程的另一解，则由
ax
by
c<
/p>
,
ap
bq
c
,
得
a
(
x
p
)
b
(
y
< br>q
)
。
由于
a
,
b
互质，从而必有整数
k
使
x
p
bk
,
此时
y
q
ak
于是，我们得到
:
x
p
bk
,
(
k
=0,
1
,
2
,
)
y
q
ak
,
以上表明，
如果我们能够看出二元一次不定方程的
某个特殊解，
那么要写出其全
部整数解，几乎不会有什么困难。
1979
年春，
美籍华裔物理学家、
诺贝尔物理学奖获得者李政道博士，
在
访问
中国科技大学时，向科大少年班学生提出过以下有趣的问题：
“
海滩上有一堆栗子，这是
5
只猴的财产，它们要平均分配。第一只猴子来
了，它左等右等，见别
的猴子还没来，便自作主张把栗子分成相等的
5
堆。分完
后还剩一个，
它便把剩下的那个顺手扔到海里，
自己拿走
5
堆中的一堆走了。
第
二只猴子来了，
它不知道刚才发生的事，
也
把栗子分成相等的
5
堆，
还是多一个。
它也扔掉一个，
自己拿走一堆走了。
以
后每只猴子来时也都遇到类似情形，
也全
都照此办理。问：原来
至少有多少个栗子？最后至少有多少个栗子？
”
这道题可以这样解答：设原来有
x
个栗子，最后剩下
y
个栗子。依题意得：
4
4
4
4
< br>4
(
(
(
(
(
x
1
)
1
)
1
)
1
)
1
)
1
< br>y
,
5
5
5
5
5
整
理得
1024
x
-3125
y
=8404
。
要解上述不定方程似乎不太容易。
但如果注意到
系数
3125-1024=2101
，
恰为
1
8404
的
，
4
也就知道
< br>x
-4
，
y
-4
是方程的一个特解。根据
前面我们讲到的公式，上述不
定方程的所有整数解可以写成：
k
,
x
4
3125
(
k
=0,
1
,
2
,
)
y
< br>4
1024
k
,
上式当
k
-1
时，得到最小的正数
x
3121
及最小的正数
y
1020
。这就是