引言

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

方法和例子

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

情形1：

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

    先考慮簡單的情況。當有兩只老鼠圍成一圈時，貓吃掉了2號，1號為最后的幸存者；當有三只老鼠圍成一圈時，貓先吃掉了2號，然后是1號，最后的幸存者是3號.....，依次類推，可發(fā)現(xiàn)如下規(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èi)吃掉的老鼠數(shù)目，這里是n=1。

情形2：

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

    先考慮簡單的情況。當有三只老鼠圍成一圈時，貓吃掉了2號和3號，1號為最后的幸存者；當五只老鼠圍成一圈時，貓先吃掉了2號和3號，然后是5號和1號，最后的幸存者是4號.....，依次類推，可發(fā)現(xiàn)如下規(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。

結(jié)論

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

    而與N對應(yīng)的X的取值則構(gòu)成了若干個等差數(shù)列B1，B2，...，Bk。這些等差數(shù)列的公差都為m，首項都為1。還發(fā)現(xiàn)，構(gòu)成的這些等差數(shù)列有這樣一個規(guī)律：每逢N的值為mk時（m和k都是正整數(shù)），對應(yīng)X的取值就是1。也就是說，當N的取值范圍從mk到mk+1－n 之間時，對應(yīng)的X的取值就構(gòu)成了一個d=m，a1=1的等差數(shù)列，項數(shù)就是從N=mk到N=mk+1－n之間數(shù)的個數(shù)（包括mk和mk+1－n這兩個數(shù)）。

    那么現(xiàn)在來看看一般情形：如果貓要從m個老鼠中吃掉n個老鼠，那么最后幸存的老鼠是幾號呢？由上面的結(jié)論，可以得出這樣的求解步驟：

    1、 首先找到小于N的一個最大的數(shù)mk（k是正整數(shù)，并假設(shè)N≠mk）； 

    2、 這樣就構(gòu)成一個首項a1＝mk，末項an＝N，公差d＝n的等差數(shù)列A，利用公式求出項數(shù)b; （即，b = 1 ＋ (N- mk)/n ）

    3、 因為X的每個取值也構(gòu)成了一個與A對應(yīng)的等差數(shù)列Bk，其中，公差為 m，首項為1，項數(shù)為b。利用等差數(shù)列求末項公式，求出末項an；

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

    4、 an就是與N對應(yīng)的X的值，也就是最后唯一幸存老鼠的編號。

    本文提出的求解方法，通過帶入老師所給出的公式驗證后，證明此方法是正確的。

參考文獻

1、學(xué)而思奧數(shù)網(wǎng)寒假精英班講義

2、等差數(shù)列的相關(guān)知識

3、學(xué)而思奧數(shù)網(wǎng)寒假精英班課堂筆記－從特殊性到一般性的研究方法

指導(dǎo)教師：周脧  

學(xué)而思教育版權(quán)所有，未經(jīng)許可，請勿轉(zhuǎn)載。