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.