关于Fibonacci数与Lucas数的两个猜想的证明

斐波那契数0，1，1，2，3，5，8，13，…可由下列违归关系生成：F0=0，F1=1，且几十l一只，十人一l（n＞l）．卢卡斯（Lucag）数2，l，3，4，7，11，18，29，…可由下列递归关系生成：人一2，L；一1，且人十l一人十L。；－l（n）l）．对这两类数，文［l］提出了如下有趣的猜想．猜想1除去F3·F3·F3—8—F6之外，其余任意三个大于1的斐波那契数之积都不是斐波那契数．猜想2？个不等于1的卢卡斯数之积不属于卢卡斯数．本文我们将证明这两个猜想都是成立的，为此，先给出几个引理．弓l理It‘。Fn＋。；一F。F，；＋；＋F。；P。31理2［…     

一对一错号排列的简明公式

对于一对一错号排列问题：有编号为1，2，…，n的n个球，将其装入编号为1，2，…，n的n个金中，每盒装1个球，且球与盒的编号不同，求不同的装球方法种数S。文［1］给出了如下一个递推公式：利用该公式计算S。时，需首先依次逐一求出SI，JZ，S3，…，S。－l的值，笔者认为，当n较大时，其计算相当复杂．下面利用集合思想方法和容斥原理来推导该问题的一个较为简明的计算公式．设n个球任意放入n个盘中，且每盒装1个球的所有不同放法组成全集I，其中第i个球恰放入第i盘中的放法组成集合A。（i—1，2，…，n），显然A。MI．又用符号IAI…     

一对一错号排列的一个公式

排列组合问题非常灵活多变，比较难以把握．例如，四人同室，他们各写一张贺年卡，先集中起来，然后每人从中拿一张别人送出的贺年卡，则四张贺年卡不同的分配方法有多少种？它的原型是下列“小球人盒”问题．将编号为1、2、3、4的4个小球装人编号为1、2、3、4的4个盒中，每盒装1个球，且球与盒的编号不同，问不同的装球方法有多少种．我们把这个问题叫做“一对一错号排列”问题．本问题，由于球与盒的个数不多，用常规法解，难度倒不是很大，但增加球与盒的个数后，情况就不一样了，仍用常规法解，难度将随之增大．因此，对于这类问题如果…     

错号排列的又一个公式

问题：有编号为1，2，...，n的n个小球，将其装人编号为1，2，...，n的n个盘中，每盒装1个球，且球与盒的编号不同，问不同的装球方法有多少种．邓廷元老师在文[1]中给出了这类"一对一错号排列"问题的公式解法该公式是用排除法得到的，并且文[1]中指出，n的值增大后，仍用常规法解，难度将随之增大，事实上，不论n的值多大，都可用常规法解，且难度并不大。设SR为一对一错号排列时K个小球装入K个盒子的不同装法种数．按题设要求把n个小球装入n个盒子可分两步完成：（Ⅰ）给编号为1的盒子装球，有种装法（Ⅱ）给其它n－1个盒子装球，若1号…     

对一道竞赛题“简证”的完善

《中学数学杂志》（曲阜）1996年第6期P40及本刊1997年第l期P34＋IJ登了董林同志关于’’’高中联赛最后一题的“简证”．我们在阅卷中见过学生的类似解法，主要有两个逻辑性的误点．为了阅读方便，我们先引述董文的解法，然后予以分析，最后给出一个细致的直接解法．题目有n（n＞6）个人聚会，已知（I）每个人至少同其中［U个人互相认识；（回）对于其中任「分」个人，或者其中有2人相识，或者余下的人中有2人认识．证明：这n个人中必有3人两两相识．证明对于n个人中的任意一个人A，把余下的人分成两类，与A认识的人作成集合P，与A不认…     

欧拉—费尔马定理及应用

欧拉一费尔马（小）定理为初等数论中极为重要定理之一．最早由费尔马1640年提出（未证明）．后经欧拉推广证明．它是解决二次同余式关键．有许多应用．在中学，被列入《高中数学竞赛大纲》（二试）．主要解数学竞赛中求余数、整除等有关问题．考虑不少师生对定理及应用均不熟悉，本文拟在这方面作一些介绍．1欧拉函数与欧拉—费尔马定理欧拉函数（n）表示不超过n且与n互质的正整数个数：＝1（2）＝1，（3）＝2，。4）一2，叭5）一4，叭6）一2，。7）一6，…我们先给出。n）的表达式：设n一户和·户和…··户承（户；为素数，i—1，2，…，…     

关于正方形的勾股剖分

将一个正方形剖分成n个勾股形（即三边长都是整数的直角三角形），n的最小值是多少？这是一个有趣的未解决的问题［fi．1968年，人们找到了将正方形剖分成5个勾股形的一个剖分图，如图1．那么n的最小值是否就是5呢？本文将回答这个问题．定理如果正方形可剖分成n个勾股形，那么n＞5．在证明定理之前，先介绍两个引理．引理1【'」三边长都是整数，底边上的高等于底边的整边三角形不存在．gi理2如图2，E、F分别在正方形儿汉D的边AD、CD上，则剖分三角形bABE、西汉F、凸n双、bEBI；'不可能都是勾股形．证明假设4个剖分三角形都是勾股形，…     

从一道分组计数题目谈起

我们在教学中发现,应用组合公式对一些分组问题进行计数时,学生易忽略一个问题,即若分组后某几个组的元素个数相同,则这几组应看成是无差别的组,在计数中应考虑这几个无差别组造成的重复计数情况.我们看个例子:例1有4个人,分成二组.⑴如果把他们分成一个组是3个人,另外一个人自成一组,问有多少种不同的分组方法?⑵如果把他们分成每组都是二个人,问有多少种不同的分组法?解题分析:对于问题⑴,我们可以如下考虑,先从4个人中任选1个人独立组成一组(这样的选择有C41=4种),余下3个人作为另一组.因此,不同的分组法有4种.对于问题⑵,如果我们沿用…     

一个组合问题

问题 一个售报亭有2n人排队买报．每份报1角钱．其中n个人持一角货币，n个人持二角货币．而报亭没有钱．问有多少种排队方式使报亭能顺利售报而不出现找不出钱的为难局面?(约定：持等值币的人无区别．)答案是1/n 1 C2n^n.若问题是4n人持1角货币n个人持5角货币．可行     

具有四个不同特征值的竞赛矩阵

设A是n阶竞赛矩阵，k是非负整数。文[3]刻划了恰好有三个不同特征值的n阶竞赛矩阵，文[4]刻划了恰好有四个不同特征值并且0作为一个一重特征值的n阶竞赛矩阵。在这篇文章中我们主要研究了两个问题：（1）讨论当k是A的特征值时A的性质。（2）刻划恰好有四个不同特征值并且k作为一个一重特征值的全部n阶竞赛矩阵。     

自然数幂个位数字变化规律的一个证明

本文用数学归纳法证明:任何一个自然数,当其幂指数以4为周期变化时,幂的个位数字保持不变.我们观察以下表格,会发现一个有趣的规律:从1到7这几个数,当它们的幂指数增加4时,个位数字保持不变.n1n2n3n4n5n6n7n811111111248163264128256392781243729218765614166425610244096163846553652512562531251562578125390625636216129677764665627993616796167493432401168071176498235435764801其实,任何自然数的幂均符合这一规律.也即:任何自然数当其幂指数以4为周期变化时,幂的个位数字保持不变.我们将其分为两个结论来证明.结论1:任何自然数的5次…     

平面图的绑定数

图G的绑定数b(G)是指边集合的最少边数,当这个边集合从G中去掉后所 得图的控制数大于G的控制数． Fischermann等人在[3]中给出了两个猜想: (1)如果 G是一个连通的平面图且围长g(G)≥4,则b(G)≤5;(2)如果G是一个连通的平面图且 围长g(G)≥5,则b(G)≤4．设n3表示度为3的顶点个数,r4和r5分别表示长为4和 5的圈的个数．本文,我们证明了如果r4<(5n3)/2 10,则猜想1成立;如果r5<12,则猜 想2成立．     

一个排列问题的商榷

文[1]讨论了如下的问题：把2n个同学分成两个组，第一组中的n个同学分别记为z1、z2、…、zn，第二组中的n个同学分别记为m，、m2、…、mn，并假设代号下标相同的两个同学是朋友，第一组中的同学去找第二组同学中的朋友．这2n个同学先任意排成一排（叫第一排），如果排在最左边和最右边的同学下标相同，则认为找到了朋友，他们不再参加后面的游戏；如果最左边和最右边的同学下标不同，则按照原来的左右顺序重新排成一排（叫第二排）。     

关于Erdos-Jacobson-Lehel 问题的门槛

设σ(k,n）表示最小的正整数m，使得对于每个n项正可图序列，当其项和至少为m时，有一个实现含k 1个顶点的团作为其子图。Erdos等人猜想：σ(k,n）＝（k-1)(2n-k) 2.Li等人证明了这个猜想对于k≥5，n≥（^k2））＋3是对的，并且提出如下问题：确定最小的整数N（k），使得这个猜想对于n≥N(k）成立。他们同时指出：当k≥5时，[5k-1/2]≤N(k）≤（^k2) 3.Mubayi猜想：当k≥5时，N(k）＝[5k-1/2]。在本文中，我们证明了N（8）＝20，即Mubayi猜想对于k=8是成立的。     

正则组合包含连续自然数的个数

一、问题的提出 (一) 第二十届国际中学生数学竞赛题第6题是:一个国际社团的成员来自六个国家,共有成员1978人,用1,2,3,……,1977,1978编号。请证明,该社团至少有一个成员的编号数,与他两个同胞的编号数之和相等,或是一个同胞编号数的二倍。 1978年9月16日北京科技报发表了证明方法、人数减至1957人,此法仍有效,但这不等于说1957是最少人数。 (二) 可以从相反方面提出问题,不出现原题指出的现象,可以有多少人参加n~(?)个国家组成的国际社团? 若一个自然数集合中任二数之正差△_A不属于这个集合,则称此集合为正则集合,或说它是正则的,用这定义,可以把上面的问题抽象为如下的数学问題: n个正则集合,能包含多少个(从1开始的)连续自然数? 本文给出一个数学命题和一个猜想。     

一道国外竞赛题的推广和引申

第40届美国中学数学竞赛最后一道题：假设7个男孩与13个女孩排队站成一行，以S记为这一行申一个男孩与一个女孩相邻站着的位置的个数．例如，对于S=12（B代表男孩、G代表女孩），S的平均值（这20个人的一切可能的排列都考虑到）最接近于（）．（A）9（B）10（C）11（D）12（E）13此题难应当年所有参加竞赛的同学，使得没有一人获得满分（试卷30道题，每题5分，满分为150分）．将此题推广如下：假设”个男孩和m个文孩排成一行，以S记这f亏中一个男孩自一个文孩相邻的童的位置的个数，那么这m＋n个人的所＃n［列中，S的平均值是多少？很…     

Whc 168初探

本刊最近收到多篇来稿 .对本刊 2 0 0 0年第 1期文章‘关于Whc 168的一个注记’提出质疑 ,并举例说明该文所提下界 n3 -n6在n =5时已不可达 .实际上 ,这个问题产生于对原问题的理解上 .数学化表述该问题可以这样提出 ,“对每个自然数n ,有一个整数 f(n) ,使当f(n)本书放入n个抽屉时可使任二个抽屉里的书的数目不同 .问minf(n) =?”我们求解这个问题时可以这样做 :先求使 f(n)≥k(n)对所有自然数n成立的k(n) .这是一种对‘至少几本书”的理解 .本刊 2 0 0 0年第 1期文‘关于Whc168的一个注记’中给出k(n)= n3 -n6.全文中有一句话不妥 ,即“…已给出 n3 -n6是可以达到的 .”‘质疑’中提出的问题正是指明了这一点 ,即k(n) =n3 -n6只是一个下界 ,而非精确下界 .这个问题还有待进一步研究 ,还应进一步提高 ,使之精确化 .我们感谢所有来稿的同志对我刊的爱护 ,以便推动对问题的进一步研究     

(二)所有人的身高一样

命题:所有人的身高一样。用数学归纳法证明如下。 n=1时,命题显然成立. 设n=k时命题真,即对任何k个人,其身高一样。那么n=k+1时,即有k+1个人时,先将这k十1个人编号,记为A_1 A_2…,A_3,A_k+1,由归纳假设可知,A_1,A_2,…A_k-1,A_k+1这k个人身高相等,记作m,又A_2,A_3,…,A_k,A_(k+1)这k个人的身高也相等,记作m_1,显然m=m_1,即这k+1个人的身高都相等。综上所述,所有人的身高都相等。     

解决排列问题9要诀

1.注意合理选取主元先看下面两个问题; 问题1 公共汽车上有3个空位,现在上来5名乘客,每个座位坐一人,问有几种不同的坐法? 问题2公共汽车上有5个空位,现在上来3名乘客,每人坐一个座位,问有几种不同的坐法?     

三维空间的分划问题

华罗庚教授在文[1]中提出如下分划问题：空间有n个平面，其中没有两个平面平行，没有三个平面相交于同一条直线，也没有四个平面过同一个点．求证：它们分．我们发现，正三棱柱的三个侧面所在平面完全满足上述条件，按上述公式计算应有V3=1个交点，E3=6段交线，S3=12片面，把空间完成F3=8分．可是实际上，这三个平面却没有交点，只有三条交线，9片面，把空间分成7块（如图）．因此这个分划问题有误．很自然地，我们会想到：问题1要得到华教授所述结论，n个平面应满足怎样的条件？问题2若依华教授所列条件，正确的点、线、面、块数该是多少…