大学数学本科毕业论文--抽屉原理(3)

易知存在整数l,m使得dk?ck?1?c1?(al?a1)?(am?a1)?al?am.

所以，D中的元素不属于P1，也不属于P2，只能属于P4 ，P5. 3 ，P?16?1??1?6??3?根据鸽巢原理（推论1），设至少存在?个元素属于P3.设为

f1?f2?f3?f4?f5?f6?326.令F?{f1,f2,f3,f4,f5,f6}.

则根据假设，在F中不存在一个元素是某两个元素之差， 令g1?f2?f1,g2?f3?f1,?,g5?f6?f1.令G??g1,g2,g3,g4,g5?,显然G中的元素不属于P3.且对于gi存在p,q,l,m使得

gi?fi?1?f1?(cp?c1)?(cq?c1)?cp?cq?(al?a1)?(am?a1)?al?am.

故G中的元素也不属于P1和P2，则G中的元素属于P4 ，P5.

?5?1??1?3??2?对于G中的5个元素，根据鸽巢原理，设至少存在?个属于P4 .设为

h1?h2?h3?326.令H?{h1,h2,h3}.令t1?h2?h1,t2?h3?h1,T?{t1,t2}.

显然，T中的元素不属于P故T的元素属于P5.但根据假1，P2 ，P4 ，3 ，P26且u不属于P5 .同样，定t1?t2?t1，令u?t2?t1，则1?u?3u也不属于P1，P2 ，P3 ，P4 ，即存在一个整数1?u?326，不属于P1，P2 ，P4 ，P3 ，P5 .这与将1至326之间的整数任意分为5部分的假定相矛盾.

因此，其中有一部分至少有一个数是某两个数之和.得证.

3.3 高等代数中的应用

例6.已知齐次线性方程组

?a11x1?a12x2??ax?ax??211222 ????an1x1?an2x2?其中aij???1,0??,i1??a12nx2n?0?a22nx2n?0?an2nx2n?0

1,n2,j?,,n1?,,2证,明,存2在不全为零的整数

x1,x2,?,x2n适合

7

证明

xi?2n?j?1,2,?,2n?

?0??x1??0??x????2?O?X?A?a 令?ij?n?2n，??，???

???????0???x2n??则该齐次线性方程组可写成AX?0

?x1??x???设集合S={X??2?:xj?n,j?1,2,?2n}

?????x2n???2n?ax??1jj?j?1?2?n???a2jxj?? D={AX???:X?S} j?1????2n???anjxj????j?1?2n映射f:X?AX是一个满射.显然S=?2n?1?,因为a1j?{-1，0，1}，所以对

S?D每个X?S，它的2n个分量适合

?aj?12nijxj?ax?1i1ax?2i2?a2in2n x ?x1?x2??xn2

≤2n2（i=1,2,?,n） 因此D??4n2?1?又

n (2n?1)2n??4n2?4n?1???4n2?1?

nn根据抽屉原理.

(映射形式设A和B是两个有限集，如果A>B那么对从A到B的任何满映射f，至少存在a1,a2,使f(a1)=f(a2).）

8

S中至少存在两个不同的元

?xj1??xi1??x??x??i2??j2?X?,X? i???j???

???????xi2n???xj2n??使

f?xi??f?xj?,即AXi?AXj,A?Xi?Xj??0.

??1?????2???即是我们所要求的，?1,?2,??2n是??????2n????1??xi1?xj1?????x?x??2??i2j2?????，则令??????????2n????xi2n?xj2n??不全为零的整数，且满足

?k?xik?xjk?xik?xjk?2n?k?1,2,?,2n?.

例7. 设A为n阶方阵，证明存在1?i?n，使秩(Ai)=秩(Ai?1)=秩(Ai?2)?? 证明

　,　2,　?　,n这n+1个数之一. 因为n阶方阵的秩只能是0,1由抽屉原理可知，存在k,l满E?A0,A,A2,?,An,An?1,E的个数多于秩的个数，足1?k

秩(Ak)= 秩(Al),

但

秩(Ak)?秩(Ak?1)???秩(Al),

所以

秩(Ak)=秩(Ak?1),

利用此式与秩的性质得

秩(ABC)?秩(AB)+秩(BC)-秩(B),

这里的A,B,C是任意三个可乘矩阵，用数学归纳法可证

秩(Ak?m)=秩(Ak?m?1).

其中m为非负整数，故命题的结论成立. 秩(Ai)=秩(Ai?1)=秩(Ai?2)??.

3.4 抽象代数中的应用

例8.证明:有限群中的每个元素的阶均有限． ．

9

证明

设G为n阶有限群，任取a∈G，则由抽屉原理可知a,a2,a3,st相等的．不妨设a?a,1?t?s?n?1于是有a,an,an?1中必有

s?t?e，从而a的阶有限．

例9.证明只含有限个理想的非零整环R必是域. 证明

根据魏得邦定理，只需证明R是除环即可.

(设R是环且R?1，则R是除环当且仅当对R中任意元素a?0,b，方程ax=b或ya=b在R中有解) 在R中任取元素a?0,b.

考虑N1?yaty?R?Rat,i?1,2,? 易知，Ra,Ra,Ra,?都是R的理想. 但由于整环R只有有限个理想，根据抽屉原理. 必存在正整数s与t满足s

t?s?1st?c)?b. 从而存在c∈R,使ba?ca或a(a??23 即方程ax=b在R中有解x?a 根据定理,R是除环. 由魏得邦定理，原命题得证.

t?s?1?c.

4.抽屉原理在实际生活中的应用

抽屉原理不仅在高等数学中具有广泛应用，在我们的实际生活中，也能处处发现抽屉原理的影子.如招生录取、赛程安排、资源分配、职称评定等等，都不难看到抽屉原理的作用.

其实早在中国古代的春秋战国时期就有了运用抽屉原理的例子，那就是《晏子春秋》中的“二桃杀三士”的典故，将两个桃子赏赐给三名勇士，在这里可以将桃子看作抽屉，三个人作为元素放进抽屉，则根据抽屉原理，一定有一个抽屉要放入两个或两个以上的元素，回到问题情境中就是一定要有两个人吃一个桃子，导致这三名勇士最后自相残杀而亡，这就是著名的“二桃杀三士”.

10

后来宋朝时期费衮在他的《梁谿漫志》中就曾运用抽屉原理来驳斥但是流行的“算命”一说，费衮指出算命是把一个人出生的年、月、日、时作为依据，把这些作为“抽屉”，则不同的抽屉有12×360×60＝259200个.把所有的人作为“物品”，则进入同一抽屉的人有成千上万个，因此“生时同者必不为少矣”.既然“八字”相同，“又何贵贱贫富之不同也？这是大基数的社会现象，常给人感觉世事很奇巧，碰到同生日、同名的人，这也是抽屉原理在生活中的应用.而生活中也有常见的抽屉原理的应用之处，如“抢凳子”游戏，一群人抢凳子，凳子数比人少，必然淘汰一些人,又或者是13个人中总有2人是同一个月份出生，52张扑克牌中取出5张总有2张花色相同，在100米长的小路上种101棵小树，不管怎么种，至少有两棵树苗之间的距离不超过1米等等. 下面我们再来看几个例子.

例10.有11名学生到老师家借书，老师是书房中有A、B、C、D四类书，每名学生最多可借两本不同类的书，最少借一本.试证明必有两个学生所借的书的类型相同. 证明

若学生只借一本书，则不同的类型有A、B、C、D四种；若学生借两本不同类型的书，则不同的类型有C3?2=6种，即AB、AC、AD、BC、BD、CD.共有10种类型.

把这10种类型看作10个“抽屉”，把11个学生看作11个“物品”.那个学生借了哪种类型的书，就将其放入对应的那个抽屉里.

?11? 根据抽屉原理，???1?2. 所以，至少有两个学生所借的书类型相同.

?10?2例11.体育用品仓库里有许多足球、排球和篮球，某班50名同学来仓库拿球，规定每个人至少拿1个球，至多拿2个球，问至少有几名同学所拿的球种类是一致的？ 解

首先来看具体的拿球的配组方式，有以下9种：

｛足｝，｛排｝，｛篮｝，｛足，足｝，｛排，排｝，｛篮，篮｝，｛足，排｝，｛足，篮｝，｛排，篮｝.

11

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库大学数学本科毕业论文--抽屉原理(3)在线全文阅读。