高逸涵 对于一道题目的深入分析 猴子分桃问题的延伸.pptVIP

对于一道题目的深入分析 对猴子分桃问题的延伸 * * 当我们写论文时，往往需要对一类题目进行较深入地分析。本文就猴子分桃问题，举例说明对于一道问题的分析方法。 引言 有N只猴子分M个桃子，却怎么也不能分匀，于是约定第二天再分。当天晚上，一只猴子来到桃子堆前，把桃子均匀分成N堆，发现多了一个，于是他把这个桃子吃掉，并取走自己的一堆，其余的并到一起，然后离开。几分钟后，另一只猴子来到桃子堆前，把桃子均匀分成N堆，发现又多了一个，于是他把这个桃子吃掉，并取走自己的一堆，其余的并到一起，然后离开。然后，又一只猴子来到桃子堆前……每个猴子都进行了相同的运动。 已知N,求M的最小值。 问题1 对于这道问题，我们发现直接做很困难，但是记得曾经有一道很简单但与此题很相似的问题，所以我们要将问题化为我们所熟悉的问题。 分析 有N只猴子分M个桃子，约定第二天分。当天晚上，一只猴子来到桃子堆前，并把桃子均匀分成N堆，取走自己的一堆，其余的并到一起，然后离开。几分钟后，另一只猴子来到桃子堆前，并把剩下的桃子均匀分成N堆，取走自己的一堆，其余的并到一起，然后离开。然后，又一只猴子来到桃子堆前……每个猴子都进行了相同的运动。 已知N,求M的最小值。 问题2 设第一个猴子离开后还剩A1个桃子，第二个猴子离开后还剩A2个桃子……第N个猴子离开后还剩AN个桃子，则有： 这道题的解法很简单，下面给出做法： 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=(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) 这就回到了我们所熟悉的形式，由问题2的结论，M+N-1的最小值为NN，于是推得M的最小值为NN –N+1 问题3 让我们看一道更一般的题目： 有N只猴子分M个桃子，却怎么也不能分匀，于是约定第二天再分。当天晚上，一只猴子来到桃子堆前，把桃子均匀分成N堆，发现多了K个，于是他把这个桃子吃掉，并取走自己的一堆，其余的并到一起，然后离开。几分钟后，另一只猴子来到桃子堆前，把桃子均匀分成N堆，发现又多了K个，于是他把这个桃子吃掉，并取走自己的一堆，其余的并到一起，然后离开。然后，又一只猴子来到桃子堆前……每个猴子都进行了相同的运动。 已知N,求M的最小值。 同问题2，有下列等式： A1=(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看起来好像是猴子分桃子类问题发展的极限了，但是事实真的是这样吗?请看下面一道题。 *