引言

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

方法和例子

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

情形1：

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

    先考慮簡(jiǎn)單的情況。當(dāng)有兩只老鼠圍成一圈時(shí)，貓吃掉了2號(hào)，1號(hào)為最后的幸存者；當(dāng)有三只老鼠圍成一圈時(shí)，貓先吃掉了2號(hào)，然后是1號(hào)，最后的幸存者是3號(hào).....，依次類推，可發(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	...

 

 

 

 

    對(duì)于這種情況，每次貓都是從兩只老鼠中吃掉一只老鼠，可認(rèn)為2只為一個(gè)周期，用m＝2表示；用n表示每個(gè)周期內(nèi)吃掉的老鼠數(shù)目，這里是n=1。

情形2：

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

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

 

 

 

 

    對(duì)于這種情況，每次貓都是從三只老鼠中吃掉兩只，可認(rèn)為3只為一個(gè)周期，即m＝3；每3只中吃掉兩只，因此，n=2。

結(jié)論

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

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

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

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

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

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

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

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

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

參考文獻(xiàn)

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

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

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

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

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