Serving the Quantitative Finance Community

 
User avatar
billypilgrim
Topic Author
Posts: 0
Joined: September 3rd, 2014, 1:08 pm

Can someone explain?

November 8th, 2014, 8:30 am

Here's the question -In a mathematical competition, in which 6 problems were posed to the participants, every two of these problems were solved by more than 2/5 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.Not sure what does this sentence exactly mean - "every two of these problems were solved by more than 2/5 of the contestants". "Every two of these" - so 15 such combinations. What then? I can't think how to proceed. Can someone post a solution?
 
User avatar
Vanubis1
Posts: 1
Joined: February 21st, 2011, 7:41 am

Can someone explain?

November 10th, 2014, 11:19 am

The more than 2/5 is more or equal or strictly more?If it's a more or equal, you have a solution with 5 mathematicians and only one mathematician with 5 correct answers. A 1 1 1 1 1 0B 1 1 1 0 0 1C 1 0 0 1 1 1D 0 0 1 1 1 1E 0 1 0 1 1 1
Last edited by Vanubis1 on November 9th, 2014, 11:00 pm, edited 1 time in total.
 
User avatar
Vanubis1
Posts: 1
Joined: February 21st, 2011, 7:41 am

Can someone explain?

November 10th, 2014, 11:34 am

If not, you can find an indication on the number of mathematicians to try to find a counter example.If N is this number, you will have one mathematician with 5 corrects answers and N-1 with 4.So for each couple of problems, the N-1 will have a 6/15 probability and the better one 10/15.0.4*N+4/15>E(0.4*N)+1 -> N=2+5*i with i integer.for N=2, it's easy to see you don't have a counter example.So we have to try with N=7.
 
User avatar
Vanubis1
Posts: 1
Joined: February 21st, 2011, 7:41 am

Can someone explain?

November 10th, 2014, 11:47 am

For N=7, you don't have counter example because for each couple of problems, you need 3 correct answers.As the total number of wrong answers is 13 (2*6+1), for one problem, you have 3 wrong answers.And in the 4 mathematicians who have the right answer, you can't have 2 who fail at the same other problem.With 4 mathematicians and 5 other problems, it's impossible with 2 wrong answers for at least 3 mathematicians.
Last edited by Vanubis1 on November 9th, 2014, 11:00 pm, edited 1 time in total.
 
User avatar
billypilgrim
Topic Author
Posts: 0
Joined: September 3rd, 2014, 1:08 pm

Can someone explain?

November 10th, 2014, 1:03 pm

QuoteOriginally posted by: Vanubis1The more than 2/5 is more or equal or strictly more?If it's a more or equal, you have a solution with 5 mathematicians and only one mathematician with 5 correct answers. A 1 1 1 1 1 0B 1 1 1 0 0 1C 1 0 0 1 1 1D 0 0 1 1 1 1E 0 1 0 1 1 1Hmm, thanks for taking the time. I guess it should be strictly more, or else the wordings would have been "solved by at least 2/5 of the contestants". Do you mind explaining this part again - "you will have one mathematician with 5 corrects answers and N-1 with 4. So for each couple of problems, the N-1 will have a 6/15 probability and the better one 10/15".Will this statement be true if 1 gets 5, and N-1 get any number correct (instead of 4) since there is no lower limit to how many one can answer. I'm still thinking if it's possible, with increasing number of participants, to have scenarios where 1 guy gets 5 correct and the rest of them manage to satisfy the condition "every two of these problems were solved by more than 2/5 of the contestants"
 
User avatar
Vanubis1
Posts: 1
Joined: February 21st, 2011, 7:41 am

Can someone explain?

November 10th, 2014, 2:52 pm

Of course, this can be lower but if you find a counter example with a guy at 3 answers, give him another good answer and you have another counter example.
Last edited by Vanubis1 on November 9th, 2014, 11:00 pm, edited 1 time in total.
 
User avatar
Vanubis1
Posts: 1
Joined: February 21st, 2011, 7:41 am

Can someone explain?

November 18th, 2014, 8:01 am

Agree that my example is wrong if it's strictly more than 2/5.Agree that for 5 mathematicians, you must have 4 mathematicians at 5 good answers (it's also true if you have 5*i mathematicians) You can show it directlty by the number of couple of problems:-> you have 15 couples with 3 (2*i+1) good answers -> 45 (30*i+15)A mathematician will have N(N-1)/2 good answers to couple of problems if he has N good answers:So: 15 for 6, 10 for 5, 6 for 4, 3 for 3,1 for 2As nobody has 15, you must have 4*10+1*6 > 45. (30*i+16>30*i+15)Btw, it doesn't answer to the general problem because we don't know there are 5*i mathematicians. If there are 12 for example, 2/5*12=4.8 so we have to find a proof or a counter example with 5 good answers to couple of problems.
Last edited by Vanubis1 on November 17th, 2014, 11:00 pm, edited 1 time in total.
 
User avatar
wileysw
Posts: 7
Joined: December 9th, 2006, 6:13 pm

Can someone explain?

November 24th, 2014, 2:48 am

there were couple of similar combinatorics problems discussed before - the common strategy is to count in two ways (see e.g., here).suppose total of N contestants, we will count the number of combination (call it S) of the pair of problems solved by some contestant:(1) every two problems were solved by more than 2/5 of the contestants, so [$]\displaystyle S\ge\frac{2N+1}{5}{6\choose 2}=6N+3[$];(2) each person who solved x problems solved [$]\displaystyle {x\choose 2}[$] pairs of problems. note [$]\displaystyle N{4\choose 2}\lt 6N+3\le S[$], so at least one person solved 5 problems; suppose only one person solved 5 problems, this time note[$]\displaystyle{3\choose 2}+(N-2){4\choose 2}+{5\choose 2}\lt 6N+3\lt (N-1){4\choose 2}+{5\choose 2}=6N+4[$],we must have one contest solved 5 problems and the rest all solved 4 problems each; on top of that, each pair of problem must be solved by exactly (2N+1)/5 contestants except one pair was solved by (2N+1)/5+1 contestants(this leads to 5|2N+1, which had been shown by Vanubis1 with a simpler argument).then i found it easier to think in graph theory terms:consider the complete graph K6 with each vertex as a problem and each edge as a pair of problem that was solved, so we have (2N+1)/5 copies of K6 + a copy of K2 (i.e., the one extra edge) that needs to be decomposed into exactly (N-1) copies of K4 and one copy of K5.to show this is impossible, consider the degree from each vertex:(1) the two vertices of K2 has the same degree of 2N+2, while the others have the degree of 2N+1;(2) but the only vertex not covered by K5 (the problem not solved by the highest scorer) has the degree =0 (mod 3), as it's covered only by K4's, while for the other ones =1 (mod 3), contradiction.
 
User avatar
Vanubis1
Posts: 1
Joined: February 21st, 2011, 7:41 am

Can someone explain?

November 24th, 2014, 8:59 am

I was waiting wileysw's answer and i' m not disappointing...For people who prefers matrix (to enable an easier understanding in Excel for example) rather than vertex, you can translate the answer.If you write the mathematicians answers in a N*6 matrix with 0 and 1: A,the 6*6 matrix transpose(A)*A gives you on the diagonal the number of good answers for a single problem and on the non-diagonal the number of good answers for couple of problems.By calling degree (like wileys) the sum of the non-diagonal terms for each row (or column), you can apply his last two remarks to find the contradiction.
Last edited by Vanubis1 on November 23rd, 2014, 11:00 pm, edited 1 time in total.
 
User avatar
billypilgrim
Topic Author
Posts: 0
Joined: September 3rd, 2014, 1:08 pm

Can someone explain?

November 24th, 2014, 11:45 am

QuoteOriginally posted by: wileyswthere were couple of similar combinatorics problems discussed before - the common strategy is to count in two ways (see e.g., here).suppose total of N contestants, we will count the number of combination (call it S) of the pair of problems solved by some contestant:(1) every two problems were solved by more than 2/5 of the contestants, so [$]\displaystyle S\ge\frac{2N+1}{5}{6\choose 2}=6N+3[$];(2) each person who solved x problems solved [$]\displaystyle {x\choose 2}[$] pairs of problems. note [$]\displaystyle N{4\choose 2}\lt 6N+3\le S[$], so at least one person solved 5 problems; suppose only one person solved 5 problems, this time note[$]\displaystyle{3\choose 2}+(N-2){4\choose 2}+{5\choose 2}\lt 6N+3\lt (N-1){4\choose 2}+{5\choose 2}=6N+4[$],we must have one contest solved 5 problems and the rest all solved 4 problems each; on top of that, each pair of problem must be solved by exactly (2N+1)/5 contestants except one pair was solved by (2N+1)/5+1 contestants(this leads to 5|2N+1, which had been shown by Vanubis1 with a simpler argument).then i found it easier to think in graph theory terms:consider the complete graph K6 with each vertex as a problem and each edge as a pair of problem that was solved, so we have (2N+1)/5 copies of K6 + a copy of K2 (i.e., the one extra edge) that needs to be decomposed into exactly (N-1) copies of K4 and one copy of K5.to show this is impossible, consider the degree from each vertex:(1) the two vertices of K2 has the same degree of 2N+2, while the others have the degree of 2N+1;(2) but the only vertex not covered by K5 (the problem not solved by the highest scorer) has the degree =0 (mod 3), as it's covered only by K4's, while for the other ones =1 (mod 3), contradiction.Nice, thanks. Hadn't seen the earlier threads on similar problems. This seems like a more formal way of proving it.