奥数专题之递推.pdfVIP

奥数专题之递推 递推法专题 递推法是组合数学中的一个重要解题方法，许多问题通过递推法来解决就显得精巧简 捷．鉴于这一方法在学习中的应用越来越广泛，掌握和运用这种方法，就显得更加重要． 递推方法问题主要有两类：一是问题中有明显的递推关系，重点在于递推关系的应用； 二是问题中没有明显的递推关系，需要对已有条件进行变形或改变问题的有关形式而建立递 推关系，将问题转化为第一类问题。本文重点探索第二类问题。 通过建立、研究递推关系 Sk+1=f(Sk)，使问题得以解决的方法称为递推方法。 例 1 平面上有 n 条直线，它们中任意两条都不平行，且任意三条都不交于一点。这 n 条 直线可以把平面分割成多少个部分？ 请看一个引起普遍关注的关于世界末日的问题。 例 2 有这样一段关于“世界末日”的传说。在印度北部的一个佛教的圣庙里，桌上的黄铜 板上，放着三根宝石针，每根长约 0.5 米。据说印度教的主神梵天在创造世界时，在其中的 一根针上，自上而下由小到大放了六十四片金片。每天二十四小时内，都有僧侣值班，按照 以下的规律，不停地把这些金片在三根宝石针上移来移去：每次只准移动一片，且不论在那 根针上，较小的金片只能放在较大的金片上。当所有六十四片金片都从梵天创造世界时所放 的那根针上移到另一根针上时，世界的末日就要到来。这虽是一个传说，但却引起人们的重 视，大家都想知道僧侣移动完毕这六十四片金片需要多少时间。也就是说，人类在这个世界 上还可以生存多少时间。 例 3 有 10 级台阶，小王从下向上走，若每次只能跨一级或两级，他走上去共有多少种不同 的走法？ 追问：10 级的情况可以一一列出，台阶数比较多的情况，怎么办？ 提示：此即为斐波那契数列 { a }求通项的问题。 n 例 4 同室4 人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送出的贺年卡，则 4 张贺年卡不同的分配方式共有( ) （A）6 种 （B）9 种 （C）11 种 （D）23 种 这里，我们引进一个概念： 设 a ,a ,a ,…，a 是 1，2，3，…，n 的一个排列,如果 a  i,(i=1,2,…，n),则称这种 1 2 3 n i 排列为一个错位排列（也称为更列）。 1 更列问题也可以形象地理解为：将 1，2，3，…，n 看成已经排好对的 n 个人，重新站 队时，各人都不站在原来的位置上。 例 5 A、B 二人拿两颗骰子做抛掷游戏，规则如下：若掷出的点数之和为 3 的倍数时，原掷 骰子的人再继续掷；若掷出的点数不是 3 的倍数时就由对方接着掷，第一次由A 开始掷，求 第 5 次仍由 A 掷的概率。 例 6 将一个四棱锥的每个顶点染上一种颜色，并使每一条棱的两端异色。如果只有 5 种颜色 可供使用，那么不同的染色方法总数有多少种？ ax  by  3   2 2 ax  by  7  5 5 例 7 设实数 a,b,x,y 满足方程组 3 3 ，求ax  by 的值。 ax  by  16   4 4 ax  by  42  例 8 设a 为下列自然数 N 的个数：N 的各位数字之和为 n，且每位数字只能是 1，3 或 4. n 求证 a 是一个完全平方数