初中数学竞赛专题辅导讲容斥原理

南京师范大学附中江宁分校黄志军初中数学竞赛专题辅导讲容斥原理IABABC1.在1到40这40个自然数中选一些数组成数集，使其中任何一个数不是另一个数的2倍，则这个数集最多有多少个数。2.一个体育代表团共有1001名运动员，他们所穿的运动服上的号码两两不同，但都小于2000，证明：至少有一名运动员的号码恰好等于另外两名运动员的号码之和。3.将与105互质的所有正整数从小到大排成一列数，求这个数列的第1000项。4.50名学生面向老师站成一行，老师先让大家从左到右按1，2，3，…依次报数，再让报数是4的倍数的同学向后转，接着又让报数是6的倍数同学向后转，问此时还有多少同学面向老师？引申：若将同学数50改成n，问此时还有多少同学面向老师？可以得出一个一般的结论：①n名学生面向老师站成一行，老师先让大家从左到右按1，2，3，…依次报数，再让报数是4的倍数的同学向后转，接着又让报数是6的倍数同学向后转，(1)问此时还有多少同学面向老师？(2)其中面向老师的第2002个（自左至右）同学报数是多少？②240名学生面向老师站成一行，老师先让大家从左到右按1，2，3，…依次报数，再让报数是3的倍数的同学向后转，接着又让报数是5的倍数同学向后转，再让报数是7的倍数同学向后转，(1)问此时还有多少同学面向老师？(2)其中面向老师的第66个（自左至右）同学报数是多少？5.从自然数序列：1，2，3，4，…中依次划去3的倍数和4的倍数，但其中5的倍数均保留。划完后剩下的数依次组成一个新的序列：1，2，5，7，10，…求该序列中第2002个数。2005是这个序列中的第几个数？划去的数从小到大排列，2008排在第几个数？第2008个数又是多少？6.设S=.求满足下面条件的最小自然数n,使得S的每一个n元子集都含有五个两两互素的数｛1，2，3，…，280｝7.平面上有n个点，n〉3，任意三点不共线，又设自然数k＜n,（2）如果k≤n，则可以让每个点都至少与其他k个点用线段连接，但任意三条线段都不能围成一个三角形。（1）如果k＞n，并且每个点都至少与其他k个点用线段连接，则必定有某三条线段围成一个三角形。12128、平面上有40个点，其中任意三点不共线，如果其中每个点都至少和其余27个点之间有线段连接.求证：必可找到4个点A，B，C，D，它们之中任何两点间都有线段相连接.9.某中学初一（1）班48位同学来自全省各地，原来并不全部认识。开学一个月后，每位同学认识班上其他同学都不超过36人，是否一定存在5个人，他们之间两两都相识？请说明理由！若每位同学认识班上其他同学的人数都超过36人，问是否一定存在5个人，他们之间两两都相识？请说明理由！10.空间中有2m个点，m≥2，其中任意四点不共面．证明：如果这2m个点之间至少连有m2+1条线段，则所连的线段中至少有三条，它们围成一个三角形．证明:在数学归纳法的基础上，应用容斥原理给出证明．当m=2时，m2+1=5，即四个点之间有五条线段相联易知其中必有一个三角形假设命题对m=k成立，即对空间中的2k个点，其中任意四点不共面，它们之间有k2+1条线段相联，则至少有某三条线段围成一个三角形．当m=k+1时，设由2m=2(k+1)个点组成的点集X满足条件:X中的任意四点不共面，X中至少有(k+1)2+l条线段相联下面证明必有三条线段围成一个三角形设a1，a2∈X，a1与a2之间有线段相联．除a2外，与a1有线段相联的点集记为A1；除a1外，与a2有线段相联的点集记为A2．分两种情形讨论情形1：X-{a1，a2｝中至少有k2+1条线段．此时，则因︱X-{a1，a2｝︱=2k，由归纳假设，在X-{a1，a2｝中存在一个三角形．情形2：X-{a1，a2｝中至多有k2条线段．由容斥原理︱A1∩A2︱=︱A1︱+︱A2︱-︱A1∪A2︱．以及︱A1︱+︱A2︱≥2k+1,︱A1∪A2︱≤2(k+1)-2=2k，即得︱A1∩A2︱≥(2k+1)-2k=1．．则以a1,a2，a3为顶点形成一个三角形．任取a3∈A1∩A2，这表明︱A1∩A2︱≠φ11.在面积为1的平面图形内任意放入9个面积为的小正方形，试说明：其中必有两个小正方形，它们重叠部分的面积不小于4515112.对于任何的集合S，设n(S)为集合S的子集个数．如果A、B、C是三个集合，满足下列条件：(1)n(A)+n(B)+n(C)=n(A∪B∪C)，(2)︱A︱=︱B︱=100，求︱A∩B∩C︱的最小值．13.一个民意调查组织对某一个地区n个居民作调查，这些居民获取新闻主要靠电视、收音机和报纸三种传播新闻的工具。调查报告表明：50人只用电视或用电视再辅之以其它工具获取新闻，61人不用收音机获取新闻，13人不用报纸获取新闻，74人至少用两种工具获取新闻。根据这些信息，求n最小值.CBAhgfedcba50611374adegacehabdhdefgabcdefghn