Author Topic: 每周一题:三人为众 (8/9/04 -- 8/15/04)  (Read 10236 times)

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
每周一题:三人为众 (8/9/04 -- 8/15/04)
« on: 八月 09, 2004, 11:33:56 am »
上周题目讨论:

TESTPOST的解答是对的。这题的关键是要用到抽屉原理。N个抽屉里放N+1只袜子,必定有一个抽屉里放两只以上的袜子。这个原理用到的时候很多。不过这抽屉和袜子有时不是那么明显。只要设对了抽屉和袜子,许多难题就迎刃而解了。

我们这周的题目可以说是推广了的抽屉原理题目。比上周的要难一些。抽屉里还要带抽屉。袜子也不是现成的。不过如果找对了抽屉,定好了袜子,这题目解起来就容易了。

本周题目:

21个男生与21个女生一起参加数学竞赛。竞赛有很多题目。已知每个学生所解出来的题目不超过6个。而且,任何一对男女生都解出一个共同的题目。也就是说随便挑一个男生,再随便挑一个女生,他们两个所解出的题目中都有一个共同的。现在请证明,至少有一个题目由三个男生与三个女生共同解出。

注意,如果把题目中的21换成20,这道题就不对了。所以你的证明中一定要用到21。

testpost

  • Newbie
  • *
  • Posts: 23
每周一题:三人为众 (8/9/04 -- 8/15/04)
« Reply #1 on: 八月 09, 2004, 07:44:16 pm »
Here's my answer. I can prove 20x20 too. If I am right, your
condition is too relax. Please point out my flaw if there is.

For reference, number 21Ms to M(1), M(2), ... M21 and Ms to
F(1), F(2), ... F(21). Becase each M and F got a common question,
we select 21x21 questions Q(m,n) answered by M(m) and F(n). Q have
21x21 members. (some of them are the same question). It is not
neccessary to arrange them into 21 by 21 matrix. But if you do so,
it will make it easy for me to explain.

What we then need to prove is a member Q(x,y)'s value appears
at 3 different column (3M) and 3 different line (3F).

Assume the set of questions in Q answered by at least 3M {M}
Assume the set of questions in Q answered by at least 3F {F}

For each M(m), Q(m,n) have only 6 cases. So, it can only have 10
non-{M} members. i.e. at least 11 {M} members. (easy to prove)

So, we know Q have more {M} members than non-{M} members. On other
hand, we will also know Q have more {F} than non-{F} members. So,
there are members belongs both {M} and {F}. So, we got it proved.

In case we change 21 to 20, the statement still hold true but just a
little more complex: We will find exact half member of {M} and {F}
if {M} and {F} don't have common. Also, we can easily see that
only case to get this is any one have exact 6 answers with distribute
of (10, 2, 2, 2, 2, 2). I emit rest of prove because it is very
simple.
testposttestposttestpost

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
每周一题:三人为众 (8/9/04 -- 8/15/04)
« Reply #2 on: 八月 09, 2004, 09:04:35 pm »
Think again.  I can easily give you an example for 20 x 20 where no problem was solved by 3 girls and 3 boys at the same time.  The example can't be wrong. :)

testpost

  • Newbie
  • *
  • Posts: 23
每周一题:三人为众 (8/9/04 -- 8/15/04)
« Reply #3 on: 八月 10, 2004, 12:48:14 pm »
I must out of my mind. You are right, This is one only case though
with 24 total Qs. So, ignore my second part at previous post.

Also, correct my previous post with M and F. One of M should be F.
It is not affect rest of prove.
testposttestposttestpost

packman

  • Full Member
  • ***
  • Posts: 226
每周一题:三人为众 (8/9/04 -- 8/15/04)
« Reply #4 on: 八月 10, 2004, 01:30:46 pm »
testpost: Can you explain the following in more details? Thanks.
======
For each M(m), Q(m,n) have only 6 cases. So, it can only have 10
non-{M} members. i.e. at least 11 {M} members. (easy to prove)
======
简单==完美

testpost

  • Newbie
  • *
  • Posts: 23
每周一题:三人为众 (8/9/04 -- 8/15/04)
« Reply #5 on: 八月 10, 2004, 03:37:23 pm »
I missed M and F up. It should be:

For any M(m), Q(m,y) {y=1 to 21} - 21 items have 6 values. There are maxium 10 non-{F} = 5x2. All rest should be {F}.

Forgive me for my expression. Hope you get it.
testposttestposttestpost