|
问题： 1——50个自然数顺次排成一个圆圈，每隔一个数取掉一个数，最后剩下42，问应从哪个数取起？ 探求； 这是个环链数列确位问题，要探求它的确位规律，还是先从直链数列确位方法来热热身吧。 一、直链数列确位方法 1、2、3……M个自然数，顺次排成一条直链，从1开始，每隔一个数取掉一个数，一轮过后再从头开始，反复几轮，最后剩下一个数，这个数是几？ 分两种情况进行探讨： （一）取偶留奇的规律 首先看取偶留奇（留1取2，留3取4……）的情况。 这种情况下无论数列有多少个数，最终剩下的一定是排在数列首位的那个数1。 归纳一：1、2、3……M个自然数，顺次排成一条直链，从1开始，每隔一个数取掉一个数（留1取2，留3取4……），一轮过后再从头开始，反复几轮，最后剩下一个数一定是排在数列首位的那个数1。
（二）取奇留偶的规律 再看取奇留偶（取1留2，取3留4……）的情况： 这种取数法，第一轮取去所有奇数（1、3、5……），剩下 2的倍数（2、4、6……）； 第二轮取去2的奇数倍数（2、6、10……），剩下4的倍数（4、8、12……）； 第三轮取去4的奇数倍数（4、12、20……），剩下8的倍数（8、16、24……）； …… 更进一步探求可归纳出一个规律：每取掉一轮后，剩下的数都是2＾n数的倍数,最后剩下的数必定是2＾n数，且是2＾n的最大值。即满足条件 2＾n≤M＜2＾（n+1） 归纳二：1、2、3……M个自然数，顺次排成一条直链，从1开始，每隔一个数取掉一个数（取1留2，取3留4……），一轮过后再从头开始，直到剩下一个数。最后剩下的数必定是2＾n数，且是2＾n的最大值。即满足条件2＾n≤M＜2＾（n+1）。
（三）应用 现在用上面归纳出的方法来解一道古趣题： 100个和尚分吃1个饼。方丈说：“这1个饼仅够一人吃，我看大家站成一条队从1起顺次报数，每次报到单数的人出列，报完一轮再从头报起，反复几轮，直至最后剩下一人，这个饼就给这最后剩下的人吃。问吃到这饼的和尚起先该站在第几？ 这道直链确位题要求取奇留偶，根据上面归纳二得的方法，设最后吃到饼的和尚起先站在第2＾n位上。 由 2＾n≤100＜2＾(n+1) 推得 2＾6＜100＜2＾（6+1） 即64＜100＜128 所以，最后吃到饼的和尚起先是站在第64位上。 二、环链数列确位方法 热身完成，回头再来探求环链数列的确位规律。 1、2、3、……M个自然数顺次排成一个圆圈，从1开始，每隔一个数取去一个数，最后剩下一个数，这个数是几？ 分两种情况探讨： （一）取奇留偶的规律 先看取奇留偶（取1留2、取3留4……）的情况。 当数序数M为2时，取去1，最后留下排在数列末位的2； 当数序数M为4时，顺次取去1、3、2，最后留下排在数列末位的4； 当数序数为8时，顺次取去1、3、5、7、2、6、4，最后剩下排在数列末位的8； …… 进一步探求归纳得，当数序数M为2＾n时,最后剩下的数必定是排在数列末位的那个数2＾n。 若数序数M≠2＾n时，又怎么处理呢？ 可定M=2＾n+K，先从这M个数中取去K个数，使原数列变换成一个数序数为2＾n的新数列，这个数列与原数列同解。这时，排在数列末位上的那个数就是要求的解。 为了便于直观感知，还可以把环链数列看成是从1起每取掉一个数就把它后面的那个数排到数列最后面去的直链数列（通过这样的变换，数序不会发生变化）。 举例1： 1、2、3、……14、15个自然数顺次排成一个圆圈，从1起每隔一个数取掉一个数（取1留2……），最后剩下的一个数是几？ ∵15=2＾3+7 ∴先从15个数中顺次取掉7个数1、3、5、7、9、11、13，把13后面的14排到数列的末位，剩下的8个数组成一外新的数列是15、2、4、6、8、10、12、14。 这个数列的数序数8=2＾3，所以，最后剩下的是排在数列末位的数14。 举例2: 100个和尚分吃1个饼。方丈说：“这1个饼仅够一人吃，我看大家站成一个圆圈,从我开始，按1、2、3……顺次报数，每次报到单数的人出列，直至最后剩下一人，这个饼就给这最后剩下的人吃。问吃到这饼的和尚第一次报的数是几？ 把100个和尚从方丈起按排队的顺序编为1——100号。 设100=2＾n+K ，2＾n满足条件
2＾n≤100＜2＾（n+1） ∵2＾6＜100＜2＾（6+1） 即64＜100＜128 ∴K=100-2＾n=100-2＾6 =100-64=36 先从100人中出列36人，这出列的第36人编号是 36×2-1=71（奇数），把71号后面的72号排到队列的末位。这时剩下的64人排成的新队列顺序号是73、74……99、100、2、4……70、72。此时排在队列末位的72就是最后剩下的人。 所以，吃到饼的和尚第一次报的数是72。 进一步探求得：1、2、3……M个自然数顺次排成一个圆圈，从1起每隔一个数取掉一个数（取1留2……），最后剩下一个数P。 设M=2＾n+K，得K=M-2＾n 2＾n满足条件2＾n≤M＜2＾(n+1) 先从M个数中取掉K个数，取掉的第K个数是 2K-1（奇数），紧挨它后面的数是2K，把2K调换到数列的最后（末位）排成一个同解新数列，最后剩下的数P就是排在数列末位的2K。 归纳三：1、2、3……M个自然数顺次排成一个圆圈，从1起每隔一个数取掉一个数（取1留2……），最后剩下一个数P。 P=2（M-2＾n） ［2＾n满足条件2＾n≤M＜2＾(n+1)］ 应用举例:1、2、3……999、1000个自然数顺次排成一个圆圈，从1起每隔一个数划掉一个数（1划2不划……），最后剩下的一个数是几？ （依归纳三计算） ∵2＾9=512，
2＾10=1024 512＜1000＜1024 ∴2×（1000-512）=976 最后剩下的数是976。 （二）取偶留奇的规律 取奇留偶的规律是：当数序数M为2、4、8、……2＾n时,最后剩下的数一定是排在数列末位上的那个数。 取偶留奇的规律与之稍有不同的是：当数序数M为2、4、8……2＾n时，最后剩下的数必定是排在数列首位上的那个数。 若数序数M≠2＾n时，可设M=2＾n+K。先从M个数中去掉K个数，使数列变成2＾n个数(这样变化后的数列与原数列同解)，这时,排在数列首位上的那个数就是要求的数。 举例1： 1、2、3、……14、15个自然数顺次排成一个圆圈，从1起每隔一个数取掉一个数（留1取2……），最后剩下的一个数是几？ ∵15=2＾3+7 先从15个数中顺次取去7个数是2、4、6、8、10、12、14，剩下的8个数排成的新数列是15、1、3……11、13。最后剩下的数就是排在首位上的数15。
举例2: 100个和尚分吃1个饼。方丈说：“这1个饼仅够一人吃，我看大家站成一个圆圈,从我开始，按1、2、3……顺次报数，每次报到双数的人出列，直至最后剩下一人，这个饼就给这最后剩下的人吃。问吃到这饼的和尚第一次报的数是几？ 先把和尚从方丈起顺次编号为1、2、3……99、100号。 设100=2＾n+K，2＾n≤M＜2（n+1） ∵2＾6＜100＜2＾7，即64＜100＜128 ∴K=100-64=36 先从100人中出列36人，出列的第36人编号是 36×2=72（偶数），剩下的64人排成的新队列顺序是73、74、75……99、100、1、3……69、71，这时，排在队列首位上的那个人73号就是最后剩下 的人。 吃到饼的和尚第一次报的数是73。 更深层的探索归纳得出规律:1、2、3……M个自然数顺次排成一个圆圈，从1起每隔一个数取去一个数（留1取2……），最后剩下一个数P。 设M=2^n+K，得K=M-2^n。 ［2^n≤M＜2^(n+1)］ 先从M个数中取去K个数，取去的第K个数是2K（偶数），紧挨其后的数2K+1就成了新的数列的首位数。新数列有2^n个数，所以，此时排在数列首位上的那个 数2K+1就是要求的数。 归纳四：1、2、3……M个自然数顺次排成一个圆圈，从1起每隔一个数取去一个数（留1取2……），最后剩下一个数P。 P=2（M-2^n）+1，且2＾n≤M＜2＾（n+1）。 应用举例: 1、2、3……2015、2016个自然数顺次排成一个圆圈，从1起每隔一个数取去一个数（留1取2……），最后剩下一个数是几？ （依归纳四计算） ∵2＾10=1024， 2＾11=2048 1024＜2016＜2048 ∴2×（2016-1024）+1=1985 最后剩下的数是1985。 弄懂了环链数列的确位规律，现在回头来解答本文开头提出的问题： 1——50个自然数顺次排成一个圆圈，每隔一个数取掉一个数，最后剩下42，问应从哪个数取起？ 由题意知本题要求留下偶数。可分两步来解答。 （1）
求出从1取起（取1留2……）时，最后剩几？ 依公式： P=2（M-2＾n），且2＾n≤M＜2＾(n+1)计算 ∵2＾5=32， 2＾6=64， 32＜50＜64 ∴2×（50-2＾n）=2×（50-32）=36 就是从1取起时最后剩下36。 （2）
求出从几取起时最后剩下42？ ∵42-36=6 （42是36后面第6个数） ∴1+6=7 就是说从1向后推6个数开始取数，最后就会剩下42。 所以要从7开始取数。 三、延伸发散 题型（一） 1，2，3，4，……M个自然数排成一个大圆圈。从1开始数，隔过1划掉2，3；隔过4划掉5，6；……。这样每隔一个数划掉两个数，转圈划下去。问：最后剩下的数P是几？ 解题公式： P = (3/2)(M – 3^n) + 1 且3＾n≤M＜3＾（n+1） 题型（二） 1，2，3，4，……M个自然数，依次排成一个大圆圈。从1开始数，每隔1个数，划去3个数。（1不划，2，3，4划去，5不划，6，7，8划去，……）。直到剩下一个数为止。问：最后剩下的数P是几？ 解题公式： P = (4/3)(M – 4^n) + 1 且4＾n≤M＜4＾(n+1) 综合题型：1、2、3……M个自然数顺次排成一个圆圈，从1开始，每隔一个数划去T个数，直到剩下一个数为止，最后剩下的数P是几？ 解题公式： P=［（T+1）/T］［M-（T+1）＾n］+1 且(T+1)＾n≤M＜(T+1)＾（n+1）
取数问题最能锻炼一个人的推理、归纳能力，研究起来有趣得很，让人上瘾：每隔两个数取一个数、每隔三个数取一个数、每隔两个数取两个数……每隔A个数取B个数，这些问题都怎么解？能归纳出一个涵盖这每一种题型的公式来吗？ 我期待志同者与我一起来玩玩这个脑子游戏。 |
|
|
