2013-02-26, 04:37 PM
If a girl only solved 1 question, then in order for for each girl-boy pair to have solved a question, it would mean all 21 boys solved that question too. This is the sorta logic you use.
Each student answered at most 6 questions right, so there are a max of 6*21 = 126 solutions per team. Therefore there are no more than 252 questions which anyone answered correctly.
Each boy-girl pair needs a link, which is a shared solution. There are 21*21 = 441 of these links.
Any particular question that multiple students got right takes care of m*n links (m girls, n boys). Call these m_i and n_i, where i is the index of the question.
sum(m_i) <= 126.
sum(n_i) <= 126.
sum(m_i*n_i) >= 441.
For all i, assume one of m_i or n_i is = 2.*
Let j = [i | m_i =2], k = [i not in j]. ie. split up the questions. We can safely say that n_k = 2 because otherwise we have a k such that m_k>2, n_k>2.
sum(m_j*n_j) = sum(2*n_j) = 252 - 2*|k|. This is 2*sum(n_i) minus the n_k's.
sum(m_k*n_k) = sum(2*m_k) = 252 - 2*|j|
sum(m_i*n_i) = sum(m_j*n_j) + sum(m_k*n_k) = 504 - 2*|i|.
Thus, 441 <= 504-2*|i|
2*|i| <= 63
|i| <= 31
That is, the students answered at most 31 distinct problems correctly.
Take 30, for example - what would this solution look like?
15 questions on each side, answered by exactly 2 students - distributing them evenly means 9 students with 2 of them, 12 with 1. (2*9+12 = 30 total answers)
The 12 students with 1 answer have 5 other answers that are shared with exactly 2 boys, but as many girls as they want, taking care of 10 boys. This means that each of those 12 questions has 11 boys answering it, minimum.
The 9 students with 2 answers have 4 other questions taking care of 8 boys. So their 2 answers have to handle 13 boys together - ie m_1 + m_2 >= 13.
So of the 15 questions, at least 6 have 11 and the other 9 have 13/2. This adds to 124.5 of the boys' answers. But what about the 30 from the boys' own 2-answer questions? The boys have to have answered more than 6 correctly each to allow this. Clearly 30 doesn't work.
Decreasing the number of distinct problems answered correctly doesn't help.
28 total, 14 on each side means 7 with 2, 14 with 1. The 14 with 1 have 5 other answers taking care of 10 boys, so 7*11 boys' responses consumed. The 7 with 2 have 4 other answers for 8 boys, leading to 7*13/2. This adds to 122.5 - still too high.
For <11 on a side, there's a girl whose answers were all only hit by 2 boys - she only links to 12, and that contradicts the requirements.
In general, for x>=11, x on a side means (2*x-21) with 2, 21-(2*x-21) = 42-2*x with 1. Then there are (21-x)*11 + (2*x-21)*13/2 + 2*x questions answered by boys. Expanding this out gets 21*11-21*13/2 -11*x + 13*x + 2*x = 94.5 + 4x. At a minimum, x=11, this is still 138.5 questions on the boys' side.
Hence always a contradiction.
* if m_i or n_i is 0, it's exactly the same as the case where that student answered one fewer question. If m_i or n_i is 1, it just restricts the problem space. So assume all questions were answered by 2 people of one sex, and an unknown number of the other.
Possibly not the most straightforward way of handling it, it's just the way I approached the problem. Basically you can split it up by the total number of questions anyone answered right - fewer than 22 contradicts one way, greater than 31 in another, and in between a third way.
Each student answered at most 6 questions right, so there are a max of 6*21 = 126 solutions per team. Therefore there are no more than 252 questions which anyone answered correctly.
Each boy-girl pair needs a link, which is a shared solution. There are 21*21 = 441 of these links.
Any particular question that multiple students got right takes care of m*n links (m girls, n boys). Call these m_i and n_i, where i is the index of the question.
sum(m_i) <= 126.
sum(n_i) <= 126.
sum(m_i*n_i) >= 441.
For all i, assume one of m_i or n_i is = 2.*
Let j = [i | m_i =2], k = [i not in j]. ie. split up the questions. We can safely say that n_k = 2 because otherwise we have a k such that m_k>2, n_k>2.
sum(m_j*n_j) = sum(2*n_j) = 252 - 2*|k|. This is 2*sum(n_i) minus the n_k's.
sum(m_k*n_k) = sum(2*m_k) = 252 - 2*|j|
sum(m_i*n_i) = sum(m_j*n_j) + sum(m_k*n_k) = 504 - 2*|i|.
Thus, 441 <= 504-2*|i|
2*|i| <= 63
|i| <= 31
That is, the students answered at most 31 distinct problems correctly.
Take 30, for example - what would this solution look like?
15 questions on each side, answered by exactly 2 students - distributing them evenly means 9 students with 2 of them, 12 with 1. (2*9+12 = 30 total answers)
The 12 students with 1 answer have 5 other answers that are shared with exactly 2 boys, but as many girls as they want, taking care of 10 boys. This means that each of those 12 questions has 11 boys answering it, minimum.
The 9 students with 2 answers have 4 other questions taking care of 8 boys. So their 2 answers have to handle 13 boys together - ie m_1 + m_2 >= 13.
So of the 15 questions, at least 6 have 11 and the other 9 have 13/2. This adds to 124.5 of the boys' answers. But what about the 30 from the boys' own 2-answer questions? The boys have to have answered more than 6 correctly each to allow this. Clearly 30 doesn't work.
Decreasing the number of distinct problems answered correctly doesn't help.
28 total, 14 on each side means 7 with 2, 14 with 1. The 14 with 1 have 5 other answers taking care of 10 boys, so 7*11 boys' responses consumed. The 7 with 2 have 4 other answers for 8 boys, leading to 7*13/2. This adds to 122.5 - still too high.
For <11 on a side, there's a girl whose answers were all only hit by 2 boys - she only links to 12, and that contradicts the requirements.
In general, for x>=11, x on a side means (2*x-21) with 2, 21-(2*x-21) = 42-2*x with 1. Then there are (21-x)*11 + (2*x-21)*13/2 + 2*x questions answered by boys. Expanding this out gets 21*11-21*13/2 -11*x + 13*x + 2*x = 94.5 + 4x. At a minimum, x=11, this is still 138.5 questions on the boys' side.
Hence always a contradiction.
* if m_i or n_i is 0, it's exactly the same as the case where that student answered one fewer question. If m_i or n_i is 1, it just restricts the problem space. So assume all questions were answered by 2 people of one sex, and an unknown number of the other.
Possibly not the most straightforward way of handling it, it's just the way I approached the problem. Basically you can split it up by the total number of questions anyone answered right - fewer than 22 contradicts one way, greater than 31 in another, and in between a third way.