Math Question

[SolicShooter]

21 girls and 21 boys participate in a math competition. The results show that: Each contestant solved at most six problems, and for each pair of a girl and a boy, there was at least one problem that they both solved.

Prove that there is a problem that was solved by at least three girls and at least three boys.

I'm just stumped... help please :)?

[happylight]

Assume that no problem was solved by more than two girls and more than two boys.

As given by the problem, for any one boy, there are 21 girl-boy pairings with him and another girl. Each pairing has a problem that is solved by both him and the girl.
If no problem was solved by more than two girls, then there must be at least 11 unique problems among these pairings. This means the boy has solved at least 11 problems which contradicts the fact that each contestant solved at most 6 problems. In fact, there must be a problem that is solved by at least four girls.

Same argument goes for the reversed gender.

Therefore there must be a problem that was solved by at least four girls and at least four boys.

[Kalovale]

@happylight

Nevermind, here's the chart for the logic strategy:

[happylight]

Nevermind, here's the chart for the logic strategy:

It's AND, not OR. Also the original statement is 'at least' not 'at most.' But yea... something like that... proof by contradiction.

[Kalovale]

It's AND, not OR. Also the original statement is 'at least' not 'at most.' But yea... something like that... proof by contradiction.

No, and no. You didn't see the change in the quantifier from existential to universial (namely, from "there exists a problem" to "all problems").
Also, it is OR. You're negating the AND statement, by De Morgans, you get an OR. Everything needs to be negated (sure you can skip steps, but that makes it confusing and hard to follow). ~(for all) = (there exists), ~AND = OR, ~(at least) = at most.

Short of being technical, I could just make sense of it intuitively:

Is (1) **[no problem was solved by at least three girls]** sufficient to establish that (2) **[a problem that was solved by at least three girls and at least three boys] is false**? Why yes. The same applies for (3) **[no problem was solved by at least three boys]**. (1) and (3) are each individually sufficient for the truth of ~(2). Therefore in order for (2) to be true, both of them have to be false.

And **[no problem was solved by at least three girls/boys]** is logically equivalent to **[All problems were solved with at most 2 girls/boys]**.

EDIT: Oh man, that markdown.

[Locked]

Look up combinatorics or pigeonhole principle in particular.

[happylight]

No, and no. You didn't see the change in the quantifier from existential to universial (namely, from "there exists a problem" to "all problems").
Also, it is OR. You're negating the AND statement, by De Morgans, you get an OR. Everything needs to be negated (sure you can skip steps, but that makes it confusing and hard to follow). ~(for all) = (there exists), ~AND = OR, ~(at least) = at most.

Short of being technical, I could just make sense of it intuitively:

Is (1) **[no problem was solved by at least three girls]** sufficient to establish that (2) **[a problem that was solved by at least three girls and at least three boys] is false**? Why yes. The same applies for (3) **[no problem was solved by at least three boys]**. (1) and (3) are each individually sufficient for the truth of ~(2). Therefore in order for (2) to be true, both of them have to be false.

And **[no problem was solved by at least three girls/boys]** is logically equivalent to **[All problems were solved with at most 2 girls/boys]**.

EDIT: Oh man, that markdown.

I thought the first statement on your image was the original, not the negation of it. If that's the case why'd you draw an arrow back to it at the end.

[Kalovale]

assumption -> contradiction OR contradiction -> original assumption is false

That arrow leading back to it says "therefore this is bullpomegranate".

[Stereo]

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.