| Author |
Message
|
| smokey |
 Posted: Fri Jul 23, 2010 8:43 pm Post subject: COMPETITION QUESTION |
 |
|
Banned (Trolling)
Joined: 05 Oct 2009
Posts: 113
|
In a mathematical competition, in which 6 problems were
posed to the participants, each two (pair) of these problems were solved by more
than 2/5ths of the contestants. Moreover, no contestant solved all the 6 problems.
Show that there are at least 2 contestants who solved exactly 5 problems
each. |
|
| Back to top |
|
 |
| Fox |
| Posted: Tue Jul 27, 2010 9:41 am Post subject: |
|
|
New Member
Joined: 26 Jul 2010
Posts: 3
|
I don't know how to prove this mathematically, so I put the data in a grid. Along the top of the grid I arranged all the possible combination of pairs of problems.
1,2 1,3 1,4 1,5 1,6 2,3 2,4 2,5 2,6 3,4 3,5 3,6 4,5 4,6 5,6
Down the left side of the grid I arranged the contestants with the problems they got wrong. I chose 15 contestants because it is divisible by 5 and because they could represent every possible combination of wrong problems. I made the assumption that attempting to give each contestant 4 "rights" and 2 "wrongs" and distributing the wrong problems as evenly as possible would maximize the number of contestants who got each problem pair right while minimizing the number of contestants who got 5 problems right with no perfect scores.
What I ended up with was a symmetrical grid with the same numbers across the top and down the left. I either put an X in each box of the grid or left it blank depending on whether a given contestant with 2 wrong problems had that problem pair right. Each row and, more importantly, each column had exactly 6 X's. 6 is 2/5 of 15. But since the question stipulated that each problem pair was soved by MORE than 2/5 of the contestants, they couldn't ALL have gotten only 4 right. In fact, in my example, forcing each problem pair to be represented by 7 contestants (the smallest number that is MORE than 2/5) caused ALL of the contestants to have at least 5 right answers.
I don't know whether a different combination of number of contestants or distribution of wrong answers would yield a better result. |
|
| Back to top |
|
|
| smokey |
| Posted: Wed Jul 28, 2010 5:54 pm Post subject: |
|
|
Banned (Trolling)
Joined: 05 Oct 2009
Posts: 113
|
| Fox wrote: |
I don't know how to prove this mathematically, so I put the data in a grid. Along the top of the grid I arranged all the possible combination of pairs of problems.
1,2 1,3 1,4 1,5 1,6 2,3 2,4 2,5 2,6 3,4 3,5 3,6 4,5 4,6 5,6
Down the left side of the grid I arranged the contestants with the problems they got wrong. I chose 15 contestants because it is divisible by 5 and because they could represent every possible combination of wrong problems. I made the assumption that attempting to give each contestant 4 "rights" and 2 "wrongs" and distributing the wrong problems as evenly as possible would maximize the number of contestants who got each problem pair right while minimizing the number of contestants who got 5 problems right with no perfect scores.
What I ended up with was a symmetrical grid with the same numbers across the top and down the left. I either put an X in each box of the grid or left it blank depending on whether a given contestant with 2 wrong problems had that problem pair right. Each row and, more importantly, each column had exactly 6 X's. 6 is 2/5 of 15. But since the question stipulated that each problem pair was soved by MORE than 2/5 of the contestants, they couldn't ALL have gotten only 4 right. In fact, in my example, forcing each problem pair to be represented by 7 contestants (the smallest number that is MORE than 2/5) caused ALL of the contestants to have at least 5 right answers.
I don't know whether a different combination of number of contestants or distribution of wrong answers would yield a better result. |
Youu are right it cannot be solved with contestant getting 4 right and no more.
There are 15 possible different pairs from a seletion of 6 questions.
There as you found only 6 possible pairs from 4 ie
xx00
x0x0
x00x
0xx0
0x0x
00xx
So yes that make 6 pairs of of 15 which is 2/5
I think you can do better than 7 contestants getting 5 right.
There are two aspects to it, get 5 right only covers 10 pairs
that leaves 5 pairs.
However the problem is those pairs are
xx0000
x0x000
x00x00
x000x0
x0000x
CCCC
A row of 4 correct
However getting 4 right is will only cover 4 of those.
Remember you need 6 pairs per line to get 40%
then I think you need another 15 pairs to push each line over the 40%.
Note with one contestant his pairs count 100%, with 2 lines that is down to 50%
with 3 lines it is only 33% 4=25%.
So beyond 2 lines you need more than one pair on a vertical line, a single pair on the line is only 33% not above the magic 40% |
|
| Back to top |
|
|
|
|
|
