国家集训队2006论文集 高逸涵

《国家集训队2006论文集 高逸涵》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、对于一道题目的深入分析对猴子分桃问题的延伸当我们写论文时，往往需要对一类题目进行较深入地分析。本文就猴子分桃问题，举例说明对于一道问题的分析方法。引言有N只猴子分M个桃子，却怎么也不能分匀，于是约定第二天再分。当天晚上，一只猴子来到桃子堆前，把桃子均匀分成N堆，发现多了一个，于是他把这个桃子吃掉，并取走自己的一堆，其余的并到一起，然后离开。几分钟后，另一只猴子来到桃子堆前，把桃子均匀分成N堆，发现又多了一个，于是他把这个桃子吃掉，并取走自己的一堆，其余的并到一起，然后离开。然后，又一只猴子来到桃子堆前……每个猴子都进行了相同的运动。已知N,求M的最小值。问题1对于这

2、道问题，我们发现直接做很困难，但是记得曾经有一道很简单但与此题很相似的问题，所以我们要将问题化为我们所熟悉的问题。分析有N只猴子分M个桃子，约定第二天分。当天晚上，一只猴子来到桃子堆前，并把桃子均匀分成N堆，取走自己的一堆，其余的并到一起，然后离开。几分钟后，另一只猴子来到桃子堆前，并把剩下的桃子均匀分成N堆，取走自己的一堆，其余的并到一起，然后离开。然后，又一只猴子来到桃子堆前……每个猴子都进行了相同的运动。已知N,求M的最小值。问题2设第一个猴子离开后还剩A1个桃子，第二个猴子离开后还剩A2个桃子……第N个猴子离开后还剩AN个桃子，则有：这道题的解法很简单，下面

3、给出做法：A1=M/N*(N-1)A2=A1/N*(N-1)A3=A2/N*(N-1)……Ai=Ai-1/N*(N-1)……AN=AN-1/N*(N-1)将上式合并:AN=((N-1)/N)N*M由于N-1与N互质，且AN为正整数，所以M为NN的倍数，M的最小值为NN。下面回到问题1，我们试图将问题已化为和问题2相同的形式。下面给出初步分析：回到题目1设第一个猴子离开后还剩A1个桃子，第二个猴子离开后还剩A2个桃子……第N个猴子离开后还剩AN个桃子，则有：A1=(M-1)/N*(N-1)A2=(A1-1)/N*(N-1)A3=(A2-1)/N*(N-1)……Ai=(

4、Ai-1-1)/N*(N-1)……AN=(AN-1-1)/N*(N-1)为了使上式与问题2的格式相符，将每个等式的左右两边分别加上N-1。A1+N-1=(M+N-1)/N*(N-1)A2+N-1=(A1+N-1)/N*(N-1)A3+N-1=(A2+N-1)/N*(N-1)……Ai+N-1=(Ai-1+N-1)/N*(N-1)……AN+N-1=(AN-1+N-1)/N*(N-1)对于上式,设Bi=Ai+N-1。B1=(M+N-1)/N*(N-1)B2=B1/N*(N-1)B3=B2/N*(N-1)……Bi=Bi-1/N*(N-1)……BN=BN-1/N*(N-1)这

5、就回到了我们所熟悉的形式，由问题2的结论，M+N-1的最小值为NN，于是推得M的最小值为NN–N+1问题3让我们看一道更一般的题目：有N只猴子分M个桃子，却怎么也不能分匀，于是约定第二天再分。当天晚上，一只猴子来到桃子堆前，把桃子均匀分成N堆，发现多了K个，于是他把这个桃子吃掉，并取走自己的一堆，其余的并到一起，然后离开。几分钟后，另一只猴子来到桃子堆前，把桃子均匀分成N堆，发现又多了K个，于是他把这个桃子吃掉，并取走自己的一堆，其余的并到一起，然后离开。然后，又一只猴子来到桃子堆前……每个猴子都进行了相同的运动。已知N,求M的最小值。同问题2，有下列等式：A1=(

6、M-K)/N*(N-1)A2=(A1-K)/N*(N-1)A3=(A2-K)/N*(N-1)……Ai=(Ai-1-K)/N*(N-1)……AN=(AN-1-K)/N*(N-1)我们希望上式也能变形成同样的格式：Ai+kk=(Ai-1+kk)/N*(N-1)由Ai=(Ai-1-K)/N*(N-1)解得kk=(N-1)*K由问题2，M的最小值为NN–kk=NN–(N-1)*K问题3看起来好像是猴子分桃子类问题发展的极限了，但是事实真的是这样吗?请看下面一道题。问题4：有N只猴子分M个桃子，却怎么也不能分匀，于是约定第二天再分。当天晚上，一只猴子来到桃子堆前，把桃子均匀分

7、成N堆，发现多了1个，于是他把这个桃子吃掉，并取走自己的一堆，其余的并到一起，然后离开。几分钟后，另一只猴子来到桃子堆前，把桃子均匀分成N堆，发现又多了2个，于是他把这个桃子吃掉，并取走自己的一堆，其余的并到一起，然后离开。然后，又一只猴子来到桃子堆前……每个猴子都进行了相同的运动。已知N,求M的最小值。由上文，所有的等式可表示为：Ai=(Ai-1-i)/N*(N-1)可是，由于每一项的常数项中都与I有关。所以，简单的把左右的常数项配成一致，是不能解决问题的。我们考虑把每一等式配成如下格式：Ai+k*(i+1)+kk=(Ai-1+k*i+kk)/N*(N-1)由