数学竞赛中的代数问题3.doc

816449362516941看过之后记住2-3 数学竞赛中的代数问题（再续）五递推数列1基本内容（2个定义、两条定理）（1）递推数列定义1 对于正整数由递推关系所确定的数列称为递推数列（2）递归数列、特征方程 定义2 若数列从第项以后任一项都是其前项的线性组合， ， 其中为正整数，为常数，则称为阶线性递归数列，称为的递归方程，与递归方程相对应的代数方程 称为阶线性递归数列的特征方程 例1 等差数列 ：，是2阶线性递归数列； 等比数列：，是1阶线性递归数列.调和数列：，不是线性递归数列，但是递推数列.（3）递归方程的求解（定理35，定理36）定理1 若特征方程有个相异根，则对应递归方程所确定的数列的通项公式为 .其中是下列方程组的唯一解： 定理2 若特征方程有重根，则对应递归方所确定的数列的通项公式为： 其中是下列方程组的唯一解： 2数学竞赛中递推数列的主要类型（1）求数值（2）求通项（3）论证数列的性质（4）数列应用题（如 p133,2-55）例2 （2-55, p133）运动会连续开了天（），一共发了枚奖章第一天发1枚以及剩下（）枚的，第二天发2枚以及发后剩下的 ，以后每天均按此规律发奖章在最后一天即第天发了剩下的枚奖章，问运动会开了多少天，一共发了多少枚奖章？ 讲解 “运动会连续开了天（），一共发了枚奖章”是题目为了叙述方便给我们设出的未知数，现在的问题是要解出在两个未知数所以要去找联系两个未知数的等量关系题目给出的、反映，之间联系的最本质关系是发奖方式：第天发枚以及发后剩下的（昨天剩下、及发枚后剩下），这又涉及今天与昨天奖章的关系，所以，我们还要设一个体现前后关系的未知数：运动会开了天后还剩下枚奖章，它与中小学时设的常量未知数的不同之处在于，是一个变量（关于的函数），因此，题目最本质的等量关系是反映的等量关系（递推方程）首先有 又，第天发了枚奖章，还剩下 ，得等量关系 下面是解这个递推方程，基本思路是化归为等比数列来处理先视为常量，找它的迭代不动点 ，（）得 ，把化为了 但为变量，且左、右两边要保持下标一致才能成为等比数列，所以继续将 ， 这又变成的形式，再求迭代不动点 于是，或说可变为 这表明，是一个等比数列，有 ，由等比数列的通项公式得 得 这就是，所满足的等量关系或方程（不定方程），因为，为整数，所以为整数，但，只有整除，由于 ，（）得=0，代入得 说明1：可以算出每天发的奖章第1天：第2天：第3天：第4天：第5天：第6天：其实是每天6枚.说明2 古典名题背景：例1-2 一位老人把积蓄的m枚金币分给n个儿女（m,n是大于1的正整数），首先，给老大1枚金币和剩下；然后，从余下枚的金币中给老二分2枚金币和剩下；依此类推，第个孩子就分枚金币和剩下的,直到最小的孩子分到最后剩下的枚金币问老人分给每个孩子的金币是否一样多？说明3 既有运算又有推理，是运算与论证的综合，还与数论交叉.例3 （斐波那契兔子问题）兔子出生以后两个月就能生小兔子，每次不多不少恰好生一对（一雌一雄）假如养了初生的小兔一对，试问：一年以后共可有多少对兔子（如果生下的小兔都不死的话）解 更一般地，设第个月有对兔子，因为第1个月只有原有的1对小兔子，故；到第2个月小兔子长大但还不会生育，仍是一对兔子，故对，易知第个月的兔子数可由两部分兔子组成，一部分是上一个月转来的兔子数，另一部分是当月新出生的小兔子，它的数量是前一个月（上2个月）的兔子数，故有 （） 其中，这个式子叫做斐波那契递推方程它反映了一个状态与前面两个状态，的联系由此可以求得：，即年后有兔子144对通过递推关系可以解出由有 （递推方程）即 变形并递推（也可以直接用等比数列的通项公式） 同理 消去得 另解 ，.说明 2009年全国高考数学陕西卷（理科）22题（12分）： 已知数列满足，猜想数列的单调性，并证明你的结论；()证明：裴波那契递推方程 ，决定了数列：1，2，3，5，8，13，21，34，55，89，144，233，现作变形，并令则有，这就是本题的数列： 其不动点为方程 的正根，正是著名的黄金分割，也是极限可见，本题有裴波那契数列和黄金分割的背景由于裴波那契数列有很多很好的性质，所以本题亦有很多很好的性质可供探讨例4设为试证数列的各项均为整数证明 由 知，数列单调递增又由已知有 平方得这表明是二次方程 两个根，由韦达定理得 又，可由数学归纳法推得数列的各项均为整数 例5 （例2-78）已知数列满足，且，（），求数列得通项 解 由已知有，且相减后移项 ，两边减去，变形 取得2-4 数学竞赛中的数论问题一. 数学竞赛中数论问题的基本内容1.数论是研究自然数的一个数学分支.2.主要有8个定义、15条定理.定义1 （带余除法）给定整数如果有整数满足 ，则和分别称为除以的商和余数。特别的，时，则称被整除，记作，或者说是的倍数，而是的约数。定义2 （最小公倍数）非零整数的最小公倍数是能被其中每一个所整除的最小正整数，记作定义3 （最大公约数）设整数中至少有一个不等于零，这个数的最大公约数是能整除其中每一个整数的最大正整数，记作定理1 对任意的正整数，有 定义4 如果整数 满足则称与是互素的（以前也称为互质）。定义5 大于1且除1及其自身外没有别的正整数因子的正整数，称为素数（以前也称为质数）。其余大于1的正整数称为合数；数1既不是素数也不是合数。定理2 素数有无穷多个，2是唯一的偶素数。定义6 对于整数，且若，则称关于模同余，记作；若，则称关于模不同余，记作。定理3 （整除的性质）设整数为非零整数，（1） 若，则；（2） 若，则；（3） 若，则对任意整数，有；（4） 若，且，则；（5） 若，且，则（6） 若为素数，且，则或。定理4 （同余的性质）设为整数，（1） 若且，则；（2） 若且，则且。（3） 若，则对任意的正整数有，且；（4） 若，且对非零整数有，则。定理5 设为整数，为正整数，（1） 若，则；（2） 若，则；（3） 若，则。定义7 设为正整数，为大于2的正整数, 是小于的非负整数，且。若 ，则称数为的进制表示。定理6 给定整数，对任意的正整数，都有唯一的进制表示。定理7 任意一个正整数与它的十进制表示中的所有数字之和关于模9同余。定理8 （分解唯一性）每个大于1的正整数都可分解为素数的乘积，而且不计因数的顺序时，这种表示是唯一的 定理9 若正整数的素数分解式为 则的约数的个数为，的一切约数之和等于 。定义8 对任意实数，是不超过的最大整数。亦称为的整数部分，。定理10 在正整数的素因子分解式中，素数作为因子出现的次数是 定理11 如果素数不能整除整数，则。定理12 设为素数，对任意的整数，有。定理13 设正整数，则不大于且与互素的正整数个数为 。定理14 整系数二元一次方程存在整数解的充分必要条件是。定理15 若是整系数二元一次方程的一个整数解，则方程的一切整数解可以表示为 3.主要出现8类重点问题.（1）奇数与偶数（奇偶分析法、01法）；（2）约数与倍数、素数与合数；（3）平方数；（4）整除；（5）同余；（6）不定方程；（7）数论函数、高斯函数、欧拉函数；（8）进位制（十进制、二进制）.二. 例题选讲 例1 有100盏电灯，排成一横行，从左到右，我们给电灯编上号码1，2，99，100.每盏灯由一个拉线开关控制着.最初，电灯全是关着的.另外有100个学生，第一个学生走过来，把凡是号码为1的倍数的电灯的开关拉了一下；接着第2个学生走过来，把凡是号码为2的倍数的电灯的开关拉了一下；第3个学生走过来，把凡是号码为3的倍数的电灯的开关拉了一下，如此等等，最后那个学生走过来，把编号能被100整除的电灯的开关拉了一下，这样过去之后，问哪些灯是亮的？（1）直接计算100次记录，会眼花缭乱.（2）拉电灯的开关有什么规律：编号包含正约数被拉，有几个正约数就被拉几次.（3）灯被拉的次数与亮不亮（开、关）有什么关系：0123456789关开关开关开关开关开 灯被拉奇数次的亮！（4）哪些数有奇数个约数：平方数（5）1100中有哪些平方数：共10个1，4，9，16，25，36，49，64，81，100816449362516941看过之后记住例2 用表示不大于的最大整数，求 原式 2004年12个月366天内层2004个高斯记号，外层1个高斯记号.例3 证明对任意正整数，分数不可约.证明1 （反证法）假若可约，则存在， （1）使 从而存在，使消去，得 （4）的 （5）由（1）、（5）矛盾，得.解题分析：1.去掉反证法的假设与矛盾就是一个正面证法2.式（4）是实质性的进展，表明 可见 .例4 （1906，匈牙利）假设是的某种排列，证明：如果是奇数，则乘积 是偶数.解法1 （反证法）假设为奇数，则均为奇数，奇数个奇数的和还是奇数奇数=与奇数偶数矛盾. 是偶数. 解法2 （反证法）假设为奇数，则均为奇数，与的奇偶性相反，中奇数与偶数一样多，为偶数但为奇数，矛盾. 是偶数. 解法3 中有个奇数，放到个括号，必有两个奇数在同一个括号，这两个奇数的差为偶数，得是偶数. 例4-1（1986，英国）设是整数，是它们的一个排列，则是偶数. 例4-2 的前24位数字为，记为该24个数字的任一排列，求证比为偶数.例5 设与为正整数，满足 求证可被1979整除（1979） 有1979整除，从而1979整除，但1979为素数，得可被1979整除例6 （1956，中国北京）证明对任何正整数都是整数，并且用3除时余2. 例7 设是异于2，5，13的任一整数.求证在集合中可以找到两个不同元素，使得不是完全平方数.证明 不是完全平方数只能是.若结论不成立，则存在正整数，使同时成立，由（1）知是奇数，设代入（1）得 为奇数，代入（2）、（3）知均为偶数.设，代入（2）、（3）后相减，有 .由于为偶数，故同奇偶，可被4整除，得为偶数.这与上证为奇数矛盾.所以，在集合中可以找到两个不同元素，使得不是完全平方数.