第四讲 递推方法

    在不少计数问题中，要很快求出结果是比较困难的，有时可先从简单情况入手，然后从某一种特殊情况逐渐推出与以后比较复杂情况之间的关系，找出规律逐步解决问题，这样的方法叫递推方法。

    一、准备题
    线段AB上共有10个点（包括两个端点），那么这条线段上一共有多少条不同的线段？
    分析与解答：从简单情况研究起：
                AB上共有2个点，有线段：1条
                AB上共有3个点，有线段：1＋2＝3（条）
                AB上共有4个点，有线段：1＋2＋3＝6（条）
                AB上共有5个点，有线段：1＋2＋3＋4＝10（条）
                ……
                AB上共有10个点，有线段：1＋2＋3＋4＋…＋9＝45（条）
     一般地，AB上共有n个点，有线段：
     1＋2＋3＋4＋…＋（n－1）＝n×（n－1）÷2
     即：线段数＝点数×（点数－1）÷2

     二、例题讲解：
     例1 的乘积中有多少个数字是奇数？

　
     如果我们通过计算找到答案比较麻烦，因此我们先从最简单的情况入手。
     9×9＝81，有1个奇数；
     99×99＝99×(100－1)＝9900－99＝9801，有2个奇数；
     999×999＝999×(1000－1)＝99900－999＝998001，有3个奇数；
     ……
     从而可知，999…999×999…999的乘积中共有10个奇数。

    例2 计算13＋23＋33＋43＋53＋63＋73＋83＋93＋103的值。

　
    这道题我们可以采用分别求出每个数的立方是多少，再求和的方法来解答。但是，这样计算的工作量比较大，我们可以从简单的情况开始研究。
     13＋23＝9＝32＝(1＋2)2
     13＋23＋33＝36＝62＝(1＋2＋3)2
     13＋23＋33＋43＝100＝102＝(1＋2＋3＋4)2
     ……
     这样我们可以得到：13＋23＋33＋43＋53＋63＋73＋83＋93＋103
                     ＝(1＋2＋3＋4＋5＋6＋7＋8＋9＋10)2
                     ＝552＝3025
     所以 13＋23＋33＋……＋ｎ3 ＝(1＋2＋3＋……＋ｎ)2

    例3 2000个学生排成一行，依次从左到右编上1～2000号，然后从左到右按一、二报数，报一的离开队伍，剩下的人继续按一、二报数，报一的离开队伍，……按这个规律如此下去，直至当队伍只剩下一人为止。问：这时一共报了多少次？最后留下的这个人原来的号码是多少？

　
    难的不会想简单的，数大的不会想数小的。我们先从这2000名同学中选出20人代替2000人进行分析，试着找出规律，然后再用这个规律来解题。
    这20人第一次报数后共留下10人，因为20÷2＝10 ，这10人开始时的编号依次是：2、4、6、8、10、12、14、16、18、20，都是2的倍数。
    第二次报数后共留下5人，因为10÷2＝5 ，这5人开始时的编号依次是： 4、8、12、16、20，都是4的倍数，也就是2×2的倍数。
    第三次报数后共留下2人，因为5÷2＝2 ……1 ，这2人开始时的编号依次是： 8、16，都是8的倍数，也就是2×2×2的倍数。
    第四次报数后共留下1人，因为2÷2＝1 ，这1人开始时的编号是：16，都是8的倍数，也就是2×2×2×2的倍数。
    由此可以发现，第n次报数后，留下的人的编号就是n个2的连乘积，这是一个规律。
    2000名同学，报几次数后才能只留下一个同学呢?
    第一次：2000÷2＝1000       第二次：1000÷2＝500
    第三次：500÷2＝250         第四次：250÷2＝125
    第五次：125÷2＝62 ……1    第六次：62÷2＝31
    第七次：31÷2＝15 ……1     第八次：15÷2＝7 ……1
    第九次：7÷2＝3 ……1       第十次：3÷2＝1 ……1
    所以共需报10次数。
    那么，最后留下的同学在一开始时的编号应是：
    2×2×2×…×2＝1024（号）

    例4 平面上有10个圆，最多能把平面分成几部分？

　
    直接画出10个圆不是好办法，先考虑一些简单情况。
    一个圆最多将平面分为2部分；
    二个圆最多将平面分为4部分；
    三个圆最多将平面分为8部分；（如右图）
    当第二个圆在第一个圆的基础上加上去时，第二个圆与第一个圆有2个交点，这两个交点将新加的圆弧分为2段，其中每一段圆弧都将所在平面的一分为二，所以所分平面部分的数在原有的2部分的基础上增添了2部分。因此，二个圆最多将平面分为2＋2＝4部分。
    同样道理，三个圆最多分平面的部分数是二个圆分平面为4部分的基础上增加4部分。因此，三个圆最多将平面分为2＋2＋4＝8部分。
    由此不难推出：画第10个圆时，与前9个圆最多有9×2＝18个交点，第10个圆的圆弧被分成18段，也就是增加了18个部分。因此，10个圆最多将平面分成的部分数为：
    2＋2＋4＋6＋…＋18
  ＝2＋2×（1＋2＋3＋…＋9）
  ＝2＋2×9×（9＋1）÷2
  ＝92
    类似的分析，我们可以得到，n个圆最多将平面分成的部分数为：
    2＋2＋4＋6＋…＋2（n－1）
  ＝2＋2×[1＋2＋3＋…＋（n－1）]
  ＝2＋n（n－1）
  ＝n2－n＋2

    例5 有8块相同的巧克力糖，从今天开始每天至少吃一块，最多吃两块，吃完为止，共有多少种不同的吃法？

　

    为叙述方便起见，设n块糖有an 种不同的吃法。
    如果n＝1，那么只有1种吃法，所以 a1＝1；
    如果n＝2，那么有2种吃法，每天吃1块和每天吃2块，所以 a2＝2；
    下面研究n≥3的情况，我们把吃糖的情况分为两种情况讨论：
    如果第一天吃1块，那么还有n－1块，有an－1种不同吃法。
    如果第一天吃2块，那么还有n－2块，有an－2种不同吃法。
    根据加法原理得：an＝an－1＋an－2 （n≥3），这样我们可以这个算出a3、a4、a5、…a8 现列表如下：

n 1 2 3 4 5 6 7 8
an 1 2 3 5 8 13 21 34

    所以，8块相同的巧克力糖有34种不同的吃法。

    例6 4个人进行篮球训练，互相传球接球，要求每个人接球后马上传给别人，开始由甲发球，并作为第一次传球，第五次传球后，球又回到甲手中，问有多少种传球方法？

　
    设第n次传球后，球又回到甲手中的传球方法有an种。可以想象前n-1次传球，如果每一次传球都任选其它三人中的一人进行传球，也就是每次传球都有3种可能，由乘法原理，共有传球方法。这些传球方式并不是都符合要求的，它们可以分为两类，一类是第n－1次恰好传到甲手中，这有an－1种传球方法，它们不符合要求，因为这样第n次无法再把球传给甲；另一类是第n－1次传球，球不在甲手中，第n次持球人再将球传给甲，有an种传球方法。根据加法原理， 有
     an－1＋an＝3×3×3×…×3＝3n－1
     因此有 an＝3n－1－an－1
     由于甲是发球者，一次传球后球又回到甲手中的传球方法是不存在的，所以a1＝0。
     利用递推关系可以得到：
     a2＝3－0＝3          a3＝3×3－3＝6
     a4＝3×3×3－6＝21   a5＝3×3×3×3－21＝60
     所以经过5次传球后，球仍回到甲手中的传球方法有60种。

　

练 习
　

    ⒈ 有500位学生编成一排，从左到右1、2、3报数，凡报到1和2的离队，报3的留下，象左看齐再重复同样的报数过程，如此进行若干此后，只剩下两位同学。问这两位同学在开始的队列中，从左到右数，分别在第几个？
    ⒉ 平面上有一条直线，把平面分成两部分，十条直线最多可把平面分成几部分？
　

    ⒈ 最后两人在最开始分别排在第243个和第486个。
    ⒉ 十条直线最多可把平面分成56部分。