任选6人,证明其中必有3人,他们互相认识或都不认识

题目详情

▼优质解答

答案和解析

这是一道数学题.
结论：任意六个人中,必有三个人相互认识,或相互不认识.
证明：任选定一个人,比如A,由抽屉原理,其余五人B,C,D,E,F中,必至少有三个人与A认识或不认识.
不失一般性,不妨设B、C、D与A认识.
在B、C、D中,若有两个人认识,比如B、C认识,则A、B、C相互认识,结论得证；
若B、C、D互不认识,则结论也已证明.
因此,任意六个人中,必有三个人互相认识或互相不认识.
更一般地,如果任意m个人中,必有n个人相互认识或相互不认识,求m的最小值f(n).
这是图论中著名难题,已有少量结果.f(2)=3,f(3)=6,.

看了任选6人,证明其中必有3人,他...的网友还看了以下：

如图：AB、CD相交于点O,且∠A=∠B.证明它们是否是位似图形.是,就指出位似中心.不是,请说明　2020-05-13 …

多选：关于原始凭证,下列说法中不正确的是（）A.原始凭证金额有错的,应由出具单位更正,并加盖出具单　2020-05-21 …

关于原始凭证的填制,下列说法中正确的有（）多选题A.原始凭证上填制的经济业务内容和数字必须真实可靠　2020-05-21 …

在海上保险实务中,投保人或被保险人保证必须从事合法的运输业务,从保证形式看, 该保证属于:( )A、　2020-05-21 …

境内企业直接或者间接到境外发行证券或者将其证券在境外上市交易,必须经( )批准。 A.国家外汇管　2020-06-27 …

英语翻译语言是人类与生俱来的本能.所有语言来源人类,被人类所创,为人类所创.因此,语言必须很轻松地　2020-06-30 …

英语翻译1、请保持证件的整洁,妥善保管好自己的证件2、此证不得转让或给予他人使用3、持证人必须遵从　2020-07-23 …

f(x)为周期函数,是f(2x)为周期函数的（）条件?括号内填充分不必要、必要不充分、充要、既不充　2020-08-02 …

商务英语翻译（请勿用有道，google,谢谢！）Translatethefollowingsente 　2020-11-05 …

关于原始凭证的审核，下列表述正确的有（）A.外来原始凭证必须有填制单位公章和填制人员的签章B.自制原　2021-01-07 …

相关搜索：证明其中必有3人他们互相认识或都不认识任选6人