In a mathematical competition, in which \(6\) problems were posed to the participants, every two of these problems were solved by more than \(\frac 25\) 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.
Radu Gologan and Dan Schwartz
=====================
The corner case presented below is the main difficulty of the problem. For that I have a near brute force solution, but I also attached a nice and elegant one from somebody else!
=====================
Proof:
Let's say each problem pair is solved by at least \(\frac 25n+\delta\) contestants where \(\delta\in\{1/5,2/5,3/5,4/5\}\). The number of contestants that solved \(5\) problems is \(x\). Double counting gives us
\({4\choose 2} n+\left({5\choose 2}-{4\choose 2}\right)x\ge {6\choose 2}(\frac 25n+\delta)\), or
\(6n+4x\ge 6n+15\delta\)
If \(\delta\ge 2/5\) then \(x\ge2\) as described.
If \(\delta=1/5\) and \(x=1\), then \(n=5k+2\) and \(14\) of the \(15\) problem pairs are solved by \(2k+1\) contestants; the remaining problem pair is solved by \(2k+2\) contestants. Moreover, one contestant, called winner, solved \(5\) problems and the rest solved \(4\). Everything adds up now but we will show contradiction.
We focus on what happens before the winner solves the \(5\)-th problem. Let the problems be \(A\), \(B\), \(C\), \(D\), \(E\), and \(F\) up to isomorphism. Everybody solves \(4\) problems, and all problem pairs are solved by \(2k+1\) contestants except for
Case \(1\):
\(AB\), \(AC\), and \(AD\) are solved by \(2k\) contestants.
Case \(2\):
\(AB\), \(AC\), \(AD\), and \(AE\) are solved by \(2k\) contestants, and \(AF\) are solved by \(2k+2\) contestants.
Case \(3\):
\(AB\), \(AC\), \(AD\), and \(AE\) are solved by \(2k\) contestants, and \(EF\) are solved by \(2k+2\) contestants.
Case \(4\):
\(AB\), \(AC\), \(AD\), and \(AE\) are solved by \(2k\) contestants, and \(BC\) are solved by \(2k+2\) contestants.
Then we want to reverse the mapping from \(4\)-problem sets solving stats to \(2\)-problem sets solving stats. Both forward and backward relations are expressed by a \(15\times15\) matrix. The forward matrix has exactly \({4\choose 2}=6\) ones per row and column, and the backward matrix is the inverse of the forward one, which is what we want.
It'd sound brute-force to find the inverse matrix, but it takes less than a minute if you know the trick! Due to symmetry, the inverse has only \(3\) distinct entries.
The second column in the table above is the coefficients for \(CDEF\). The bottom row is the constant term in the number of contestants who solve \(CDEF\), since the term related to \(k\) never changes. For each case, we show two columns. Although they look like two different inputs, they're from different permutations on \(\{A,B,C,D,E,F\}\) and are used to show the number of contestants who solve other \(4\)-problem sets such as \(ACEF\).
Finally, the two sums at the bottom for each case that differ by non-integer number concludes our proof, as they show that the number of contestants that solve \(4\)-problem sets cannot be all integers.
Q.E.D.
=====================
Below is a very nice and elegant proof that I found here showing that it is impossible to have everybody solve exactly \(4\) problems except a winner that solves \(5\), and every problem pair solved by \(2k+1\) contestants except one by \(2k+2\).
Proof:
Consider a graph \(G\) with vertices \(\{A,B,C,D,E,F\}\). The number of edges between any two vertices is the number of contestants who solve both problems.
On one hand, because contestants who solve \(4\) problems do not change any vertex degree modulo \(3\), the winner alone determines the degree of all vertices. Specifically, the \(5\) problems solved by the winner all have degree \(4-3=1\) modulo \(3\), and the last problem has degree \(0\) modulo \(3\).
On the other hand, all edges have multiplicity \(2k+1\) except for one that have multiplicity \(2k+2\), meaning that the \(2\) problems connected by this last edge have different degree from the rest \(4\), contradiction.
Q.E.D.
Finally, the two sums at the bottom for each case that differ by non-integer number concludes our proof, as they show that the number of contestants that solve \(4\)-problem sets cannot be all integers.
Q.E.D.
=====================
Below is a very nice and elegant proof that I found here showing that it is impossible to have everybody solve exactly \(4\) problems except a winner that solves \(5\), and every problem pair solved by \(2k+1\) contestants except one by \(2k+2\).
Proof:
Consider a graph \(G\) with vertices \(\{A,B,C,D,E,F\}\). The number of edges between any two vertices is the number of contestants who solve both problems.
On one hand, because contestants who solve \(4\) problems do not change any vertex degree modulo \(3\), the winner alone determines the degree of all vertices. Specifically, the \(5\) problems solved by the winner all have degree \(4-3=1\) modulo \(3\), and the last problem has degree \(0\) modulo \(3\).
On the other hand, all edges have multiplicity \(2k+1\) except for one that have multiplicity \(2k+2\), meaning that the \(2\) problems connected by this last edge have different degree from the rest \(4\), contradiction.
Q.E.D.
No comments:
Post a Comment