引言

    貓捉耗子是一個有名的游戲，一只貓讓N個老鼠圍成一圈報數，每次吃掉報單數的老鼠，有一只老鼠總不被吃掉，問這個老鼠站在哪個位置？數學中稱這類問題為貓捉耗子問題。對這類問題通常的做法是從特殊情況出發(fā)，逐步發(fā)現規(guī)律，然后給出求解公式。老師在課堂上介紹了公式以及推導過程，但我認為推導過程較為復雜，不好理解。根據反復試驗和觀察，本文給出了一種容易理解的求解這類問題的方法。

方法和例子

    這里列舉這類問題的兩種情形。對于每種情形都首先考慮特殊情況，然后從中發(fā)現規(guī)律。這兩種情形都是基于如下前提：從1到N編號的N個老鼠順時針圍成一圈，從1開始報數。并規(guī)定游戲一開始的第一個生存者是1號老鼠。設老鼠的總個數為N，最后幸存的老鼠編號為X。

情形1：

    1號老鼠生存下來，2號老鼠被貓吃掉；3號老鼠生存下來，4號老鼠被貓吃掉.....就這樣，這只貓每隔一只老鼠，就吃掉另一只老鼠，那么最后唯一幸存的那只老鼠是幾號呢？

    先考慮簡單的情況。當有兩只老鼠圍成一圈時，貓吃掉了2號，1號為最后的幸存者；當有三只老鼠圍成一圈時，貓先吃掉了2號，然后是1號，最后的幸存者是3號.....，依次類推，可發(fā)現如下規(guī)律：

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號.....，依次類推，可發(fā)現如下規(guī)律：

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。

結論

    通過對上述兩種情形的運算結果的觀察，發(fā)現N的所有可能的取值按照一定的順序排列后，構成了一個等差數列A。該數列的首項a1＝m，公差d＝n（m和n都是正整數）。

    而與N對應的X的取值則構成了若干個等差數列B1，B2，...，Bk。這些等差數列的公差都為m，首項都為1。還發(fā)現，構成的這些等差數列有這樣一個規(guī)律：每逢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、學而思奧數網寒假精英班課堂筆記－從特殊性到一般性的研究方法

指導教師：周脧  

學而思教育版權所有，未經許可，請勿轉載。