探讨猫捉耗子问题

引言

    猫捉耗子是一个有名的游戏，一只猫让N个老鼠围成一圈报数，每次吃掉报单数的老鼠，有一只老鼠总不被吃掉，问这个老鼠站在哪个位置？数学中称这类问题为猫捉耗子问题。对这类问题通常的做法是从特殊情况出发，逐步发现规律，然后给出求解公式。老师在课堂上介绍了公式以及推导过程，但我认为推导过程较为复杂，不好理解。根据反复试验和观察，本文给出了一种容易理解的求解这类问题的方法。

方法和例子

    这里列举这类问题的两种情形。对于每种情形都首先考虑特殊情况，然后从中发现规律。这两种情形都是基于如下前提：从1到N编号的N个老鼠顺时针围成一圈，从1开始报数。并规定游戏一开始的第一个生存者是1号老鼠。设老鼠的总个数为N，最后幸存的老鼠编号为X。

情形1：

    1号老鼠生存下来，2号老鼠被猫吃掉；3号老鼠生存下来，4号老鼠被猫吃掉.....就这样，这只猫每隔一只老鼠，就吃掉另一只老鼠，那么最后唯一幸存的那只老鼠是几号呢？

    先考虑简单的情况。当有两只老鼠围成一圈时，猫吃掉了2号，1号为最后的幸存者；当有三只老鼠围成一圈时，猫先吃掉了2号，然后是1号，最后的幸存者是3号.....，依次类推，可发现如下规律：

N

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

...

X

1

3

1

3

5

7

1

3

5

7

9

11

13

15

1

3

5

7

9

...

 

 

 

 

    对于这种情况，每次猫都是从两只老鼠中吃掉一只老鼠，可认为2只为一个周期，用m＝2表示；用n表示每个周期内吃掉的老鼠数目，这里是n=1。

情形2：

    1号老鼠生存下来，2号、3号老鼠被猫吃掉；4号老鼠生存下来，5号、6号老鼠被猫吃掉.....就这样，这只猫每隔一只老鼠，就吃掉另两只老鼠，依次下去，最后唯一幸存的那只老鼠是几号呢？

    先考虑简单的情况。当有三只老鼠围成一圈时，猫吃掉了2号和3号，1号为最后的幸存者；当五只老鼠围成一圈时，猫先吃掉了2号和3号，然后是5号和1号，最后的幸存者是4号.....，依次类推，可发现如下规律：

N

3

5

7

9

11

13

15

17

19

21

23

25

27

29

31

33

...

81

83

...

X

1

4

7

1

4

7

10

13

16

19

22

25

1

4

7

10

...

1

4

...

 

 

 

 

    对于这种情况，每次猫都是从三只老鼠中吃掉两只，可认为3只为一个周期，即m＝3；每3只中吃掉两只，因此，n=2。

结论

    通过对上述两种情形的运算结果的观察，发现N的所有可能的取值按照一定的顺序排列后，构成了一个等差数列A。该数列的首项a1＝m，公差d＝n（m和n都是正整数）。

    而与N对应的X的取值则构成了若干个等差数列B1，B2，...，Bk。这些等差数列的公差都为m，首项都为1。还发现，构成的这些等差数列有这样一个规律：每逢N的值为mk时（m和k都是正整数），对应X的取值就是1。也就是说，当N的取值范围从mk到mk+1－n 之间时，对应的X的取值就构成了一个d=m，a1=1的等差数列，项数就是从N=mk到N=mk+1－n之间数的个数（包括mk和mk+1－n这两个数）。

    那么现在来看看一般情形：如果猫要从m个老鼠中吃掉n个老鼠，那么最后幸存的老鼠是几号呢？由上面的结论，可以得出这样的求解步骤：

    1、 首先找到小于N的一个最大的数mk（k是正整数，并假设N≠mk）； 

    2、 这样就构成一个首项a1＝mk，末项an＝N，公差d＝n的等差数列A，利用公式求出项数b; （即，b = 1 ＋ (N- mk)/n ）

    3、 因为X的每个取值也构成了一个与A对应的等差数列Bk，其中，公差为 m，首项为1，项数为b。利用等差数列求末项公式，求出末项an；

（即，an = 1 + (b-1)*m）

    4、 an就是与N对应的X的值，也就是最后唯一幸存老鼠的编号。

    本文提出的求解方法，通过带入老师所给出的公式验证后，证明此方法是正确的。

参考文献

1、学而思奥数网寒假精英班讲义

2、等差数列的相关知识

3、学而思奥数网寒假精英班课堂笔记－从特殊性到一般性的研究方法

指导教师：周睃  

学而思教育版权所有，未经许可，请勿转载。