精选问答
高一数学题求解一次会议有500名代表参加,每名代表认识的人数>400.证明:一定能找到6名代表,每两名代表互相认识(本题的认识是互相的,即甲认识乙,乙认识甲)用容斥原理解答.如果可以,给我说下容斥原理的精髓(好的额外加分)2L的没这个题解答啊

2019-05-23

高一数学题求解
一次会议有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)的圈子
所以得证
证明得很辛苦,请给分
容斥原理的定义上面已经解释了,
这到题目用到抽屉原理的成分还多些
第一步:任意从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)的圈子
所以得证
证明得很辛苦,请给分
相关问答