Question

高分求解一道数学题：

几月前网上有如下一道题：10个人做10道题，已知：没有两个人做对的题目完全相同。
求证：存在一道题，去掉之后，仍然没有两个人做对的题目完全相同。
这道题当时引起讨论，后来出题人出于对我的信任，发信息让我给他解决，我给了一个解答，随后就得到出题人的肯定，然而过后，我觉得解答有很大的问题，我想找到该题的正确答案，我经常在思索这道题，但几个有过去了，我用了很多方法，仍一筹莫展，不过这个题目引起了我极大兴趣，首先我坚信它结论是正确的，它引出一个重要有趣的组合问题，即
S是由n个元素构成的集合，S1，S2，…Sn是S的任意的n个互不相同的子集，则一定存在S的一个元素a，使得S1-a，S2-a，…Sn-a仍是集合S的n个互不相同的子集。
这是一个很有意思的题，希望广大数学爱好者帮助解决。
http://zhidao.baidu.com/question/132405927.html?si=1

Answer 1

假设去掉任一道题，都有两人答案相同

横轴为题号，竖轴为人编号

1号people为初始答案，其他人答案以1代表与其相反，0代表相同

从第十道题开始依次至第一道，以与1号people第十道题不同者为2号，与2号people第九题不同者为3号，依此类推，则可得去除第一道时，没有两个人做对的题目完全相同，与假设矛盾，又因题号假设顺序任意，原命题得证。

Answer 2

证明有问题:
“若否命题成立，则不同的题目去掉后，满足条件的两人也必不同。这样就需要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的元素多，这也是不可能的，完成了反证法的证明。

Answer 3

我试着用图论的办法来解决

构造一个n点无向图，每点代表一个子集，两点间有路径相连当且仅当两子集的差只有一个元素，并且此子集对为“差为此元素的子集对中最小的一组”

我这种证明的核心在于图的定义，主要是边，我对所有的无序子集对（顶点对）定义了一种良序关系（事实上，由于子集对有限，故良序关系一定存在，这里只是举出一例），子集对<Va,Vb> ≤ <Vc,Vd>(这里a,b,c,d为下标数) 当且仅当min{a,b}<min{c,d}或 min{a,b}=min{c,d}且max{a,b} ≤ max{c,d}，通过这种序关系的定义，我使得每两个子集对（顶点对）都能比较大小。
而边的有无判断不仅基于两顶点对应子集的差，也基于这个序，两点间有边当且仅当这两点对应集合的差只包含一个元素（设为a），并且这个顶点对（子集对）是所有差为a的子集对中最小的那对（大小根据前所述良序定义）。

根据以上定义得出的图，对集合的任意元素a来说，至多有一条边，其端点对应子集的差为a（重要！），于是就有接下去关于无回路的证明了~

首先证明引理：按此定义构造的图中不存在回路
证：假设存在回路v1-v2-v3-...-vk-v1
实际上很显然，若存在v1-v2-v3-…-vk，则按图定义，v1与vk间必有k-1题不同，故v1与vk间不存在边。
k=3时，显然
假设k=i时成立
k=i+1时，v1与vk-1间有k-2个元素不同，因vk-1与vk相连，故这两集合间只有1元素不同（设为p），若p不属于那k-2个元素的集合，则v1与vk有k-1元素不同，若p属于那k-2个元素的集合，则有两条边都以一个元素为差，与图定义矛盾。
引理得证

然后就是图论中的问题：在n点图中，若无回路，一定少于等于n-1条边
证：图的基本性质

这个图论的结论翻译成原题，就是最多有n-1个元素，使得去掉它们其一后有相同子集。
于是得证

Answer 4

这个题为否命题。
反例：假设10个人做的十道题全对任意两个人所做题有9道相同则总共只有11道题去掉任意一道题都会使10个人做的题相同

Answer 5

我给个答案吧，用反证法

给十个题编号为1，2。。。10，每个人对应集合Si，若该人做对了题1，则1
属于Si，否则不属于
假设去掉任意一道题之后，都必然有两个人做对的题目完全相同
不妨设设第一人的集合为S1不为空集，则随便去掉一道属于S1的题j后，有另一个集合等同于S1
又知道在没去掉这道题之前这两人不同，则这个集合为S1/j
以此类推得出某人为空集
这里的矛盾应该看得出来吧