再次请教,离散数学
发布网友
发布时间：2024-01-21 17:51
共1个回答
热心网友
时间：2024-03-09 13:40
“若否命题成立，则不同的题目去掉后，满足条件的两人也必不同。这样就需要20人才能满足”,20人才能满足,这个结论有问题!
设10道题分别用1,2,…,10表示，故10道题构成的集合为S={1,2,…,10}，如果是11个人，11个人分别做对的题目构成的集合为
{1，2，3，…,10}(全对)，{2，3，4,…,10}(除1外)，{1，3，4，…,10}(除2外)，…,{1，2，3，…,9}(除10外)，
此时去掉任意一道题之后，必有两个人做对的题目完全相同。不需要20人,只需11人就能确保去掉任意一道题之后，必有两个人做对的题目完全相同。
下面给出一个证明供你参考:
证明 设10道题分别用t1,t2,…,t10表示，故10道题构成的集合为
S={t1,t2,…,t10}，
10个人分别做对的题目构成的集合为S1，S2,…,S10,显然S1，S2,…,S10,均是S的子集，且由题意可知S1，S2,…,S10两两不同。
下面用反证法证明该题的结论，如果不存在一道题去掉它之后，仍然没有两个人做对的题目完全相同。即去掉任意题之后，必有两个人做对的题目完全相同，如去掉t1之后，必存在不同的i,j,有Si-t1=Sj-t1,由题意Si与Sj不同，故t1必属于且仅属于Si和Sj之一，不妨设t1属于Sj，但不属于Si，故Si必是Sj的真子集（Si中的元素个数比Sj仅少一个，缺少一个t1），换言之，S1，S2,…,S10中至少有一个集合不含有t1，并且另有一个集合包含它，比它仅多一个元素t1，这两个集合形成一对,同理，S1，S2,…,S10至少有一个集合不含有t2，t3,…,t10，并且该集合与另外一个集合形成一个对子，该集合是它配对集合的真子集，前者元素个数比后者仅少一个，象上面Si，Sj一样，不妨就用S1，S2,…,S10分别表示不含有t1,t2,…,t10的集合,下面证明这些集合两两不相同，如果S1与S2是同一个集合，则与它配对的集合Sk，必含有t1,t2，此时集合Sk比S1或S2多两个元素，这是不可能的，故S1，S2,…,S10两两不相同，此时与S1，S2,…,S10分别形成对子的集合必在S1，S2,…,S10这些集合之中，设Sk是S1，S2,…,S10中含有元素最多的一个集合，与Sk配对的集合也必在S1，S2,…,S10这些集合之中，但与Sk配对的集合的元素较Sk的元素多，这也是不可能的，完成了反证法的证明。来自：求助得到的回答
