复杂抽屉原则三题

jhmath

复杂抽屉原则三题

1、时钟的表盘上按标准的方式标着1、2、3、4……、11、12这12个数，在其上任意做n个120°的扇形，每一个都恰好覆盖4个数，每两个覆盖的数不全相同。如果从这任做的n个扇形中总能恰好取出3个覆盖整个钟面的全部12个数，求n的最小值。

　　3个是最有利的情况，“任意做”变成了“恰好做”比如第一个覆盖1234，第二个覆盖5678，第三个覆盖9101112，而题中把“任意做N个”与“总能恰好取3个”搭配起来，所要表达的意思是要考虑最不利的情况，如果我作的三个是1234，4567，891011，      能找得出三个来覆盖整个表盘吗？
　　哪为什么是9个呢？一是我们可以找出这么一种排法恰好满足要求， 比如这9个分别是：1234，2345，3456，4567，5678，6789，78910，891011，9101112，  如果少一个是这样的8个，1234，2345，3456，4567，5678，6789，78910，891011，  12这个数还没用到，怎么找得出。
　　二是必须有9个，在最不利的情况下也能包含1-12这12个数，比如已经有1234，哪再画一个至少得增加一个数或者是2345，或者是12 1 2 3 ，再画8次必定至少能增加8个数，一共12个不同的数。
　　从反面考虑，N的最大值也只有12。分别为 1234，2345，3456，4567，5678，6789，78910，891011，9101112，101112 1，1112 1 2，12 1 2 3      这十二个不同的扇形。从这十二个扇形中至多任意去掉几个后还能保证找得出三个覆盖整个表盘呢？ 当然最多只能去掉三个，如  2345，3456，4567，要是再去掉1234，那4这个数从剩下的8个里是无论如何也找不到了，因此答案是9。
　　怎么用抽屉原理来解这道题呢？
   把可画出的以1--12为第一个数字的全部12个扇形分成如下4组，即4个抽屉。每个抽屉里的3个扇形都能覆盖整个表盘。（1234   5678   9101112）（ 2345，6789，101112 1）（3456，78910，1112 1 2），（4567，891011，12 1 2 3  ）    
   现在就是考虑至少取出多少个扇形（当作苹果）才能保证有三个扇形（苹果）取自同一个抽屉。 根据抽屉原理的计算方法得：4*2+1=9，也就是每个抽屉取两个接着再取1个，不管怎么取都与已经取出的另两个来自同一个抽屉，也就是这3个扇形能覆盖整个表盘，所以N至少是9才能确保结论成立。

阳光6848

n的最小值为9。
当n=8时，可以找到一种方法，不能覆盖钟面的12个数字，
如（1，2，3，4）；（2，3，4，5）；（3，4，5，6）；（4，5，6，7）；
（5，6，7，8）；（6，7，8，9）；（7，8，9，10），（8，9，10，11）。
所对应的8个扇形未能覆盖数字12，更不能找到3个扇形恰能盖住12个数字。
当n=9时，总能找到3个扇形恰能盖住12个数字。为了证明其成立，将扇形
所盖住的数字分成四类：
第一类：（1，2，3，4）；（5，6，7，8）；（9，10，11，12）
第二类：（2，3，4，5）；（6，7，8，9）；（10，11，12，1）
第三类：（3，4，5，6）；（7，8，9，10）；（11，12，1，2）
第四类：（4，5，6，7）；（8，9，10，11）；（12，1，2，3）。
每一类所对应的3个扇形都能覆盖钟面的12个数字。任取9个扇形时，相当于从上述
4类中任取9个，比存在3个数组属于同一类，这一类的3个数组所对应的三个扇形便能
覆盖住钟面的12个数字。
2、试卷上共有4道选择题，每题有3个可供选择的答案 。一群学生参加考试。结果是对于其中任何3人，都有一个题目的答案互不相同。问参加考试的学生最多有多少人？

阳光6848

当参加考试的人数=9时可以实现任何三人都有一个题目的答案互不相同。
假设每题的选择答案是a,b,c
   人   1    2    3    4    5    6    7    8    9
题
1       a    a    a    b    b    b    c    c    c
2       a    b    c    a    b    c    a    b    c
3       a    b    c    c    a    b    b    c    a
4       a    b    c    b    c    a    c    a    b
当参加考试的人数=10时,我们先看第一题，肯定有一个答案的人数小于等于3，
也就是说肯定有7个以上的人，他们第一道题的答案不超过两种。再来看这7个
人和第二道题，肯定有一个答案的人数小于等于2，也就是说肯定有5个以上的人，
他们第二道题的答案不超过两种。也就是说肯定有5个以上的人第一道和第二道
题的答案都不超过两种。再来看这5个人和第三道题，肯定有一个答案的人数小
于等于1，也就是说肯定有4个以上的人，他们第三道题的答案不超过两种。也就
是说肯定有4个以上的人第一道题、第二道题和第三道题的答案都不超过两种。
最后再看这4个人和第四道题，肯定有一个答案的人数小于等于1，也就是说肯定
有3个以上的人，他们第四道题的答案不超过两种。也就是说肯定有3个以上的人
第一道题、第二道题、第三道题和第四道题的答案都不超过两种。这就跟题目的
要求矛盾了。

3、8个学生角8道题目
⑴若每道题至少被5人解出，请说明可以找到两个学生，每道题至少被这两个学生中的一个解出。
⑵如果每道题只有4个学生解出，那么⑴的结论一般不成立。试构造一个例子说明这点。

若每道题至少被5人解出，请说明可以找到两个学生，每道题至少被这两个学生中的一个解出。

我们可分4种情况讨论一下：
1.假设解题最多的人A解出8道题
  这是我们可以选他和任意一个人都能满足题目要求。
2.解题最多的人A解出7道题
  A没有解出的那道题至少有五个人解出，我们任选一个和A能满足题目要求。
3.解题最多的人A解出6道题
  A没有解出的那两道题每道题有五个人解出，共有10个人次解出，但只有7个人，肯定有一个人全部解出了这两道题。
  我们就选他和A能满足题目要求。
4.解题最多的人A解出5道题
  也就是说每人都解出了5道题。我们任选一个人设为A,A没有解出的那三道题每道题有五个人解出，共有15个人次解出，
  但只有7个人，肯定有一个人解出了三道题。我们就选他和A能满足题目要求。

　提醒：欲看更多精华回帖请到奥数论坛注册查看。

http://bbs.aoshu.cn/dispbbs.asp?boardid=11&star=1&replyid=112350&id=15727&skin=0&page=1