高一数学题求解一次会议有500名代表参加,每名代表认识的人数>400.证明:一定能找到6名代表,每两名代表互相认识(本题的认识是互相的,即甲认识乙,乙认识甲)用容斥原理解答.如果可以,给我说
1人问答
问题描述：
高一数学题求解
一次会议有500名代表参加,每名代表认识的人数>400.证明:一定能找到6名代表,每两名代表互相认识(本题的认识是互相的,即甲认识乙,乙认识甲)
用容斥原理解答.如果可以,给我说下容斥原理的精髓(好的额外加分)
2L的没这个题解答啊
饶进军回答：
容斥原理的定义上面已经解释了,
这到题目用到抽屉原理的成分还多些
第一步：任意从500名代表中选取一人A，由于每个代表认识(互相认识)大于400人，即至少401人，故将这401人归为一组
那就把这500人分为了3部分：（和A不认识的98人）（A）（认识A的401人）
第二步：在这401人里任意找一个B，AB肯定互相认识，那在这401人里至少有多少人和B认识呢？由于B也至少认识401人，那么B在这400人里（不算B自己）至少认识401-99=302人（假设第一步筛选出去的98人他都认识，而且已知他认识A），将这302人归为一组
现在这500人就分成三部分（和A、B不一定认识的196人）（互相认识的A、B）（同时认识A、B的302人）
第三步：在这302人里任意找一个C，由于C也至少认识401人，那么C在这302人里至少认识401-198=203人（假设前面两步筛选出去的196人他都认识，而且已知他认识A、B），将这203人归为一组
现在这500人就分成三部分（和A、B、C不一定认识的297人）（互相认识的A、B、C）（同时认识A、B、C的203人）
第四步：在这203人里任意找一个D，由于D也至少认识401人，那么D在这203人里至少认识401-300=101人（假设前面三步筛选出去的297人他都认识，而且已知他认识A、B、C人），将这101人归为一组
现在这500人就分成三部分（和A、B、C、D不一定认识的396人）（互相认识的A、B、C、D）（同时认识A、B、C的101人）
第五步：在这101人里任意找一个E，由于E也至少认识401人，那么E在这101人里至少认识401-400=1人，假设这个人为F，这样E和F就和前面的（互相认识的A、B、C、D）组成了一个（互相认识的A、B、C、D、E、F）的圈子
所以得证
证明得很辛苦，请给分
数学推荐
数学推荐
最新更新
精品分类
优秀数学推荐
热门数学
邮箱： 