4
$\begingroup$

Suppose that $21$ girls and $21$ boys enter a mathematics competition. Furthermore, suppose that each entrant solves at most $6$ questions, and for every boy-girl pair, there is at least $1$ question that they both solved. Show that there is a question that was solved by at $3$ three girls and at leat $3$ boys.

My question is, why is the number $3$ special here, for example, I tried proving this question in the following way. Fix a girl $g$, this girl could've at most solved $6$ questions $q_1,\dots,q_6$. For the sake of contradiction, assume Each question was solved by at most 2 boys or at most two girls. We first consider if there is at most $2$ boys, then for each of the $6$ questions $g$ answered, there could be at most $2$ pairs involving her and $2$ other boys that solved this question, so for all her $6$ questions, there could be at most $12$ pairs that involve her and other boys. If we sum up this number over all $g$, ($21$ in total), we get the number of pairs is at most $21\times 6 \times 2=252$. This is a contradiction since there are $21^2=441$ pairs of boy-girls, the second case for at most $2$ girls also goes the same by symmetry, so in both cases we have a contradiction.

My question: Why is the number $3$ special here? If it would've been replaced by $4$, then our last equation would be $21 \times 6 \times 3=378$ which is still less than $441$, am I missing something here?

$\endgroup$
  • $\begingroup$ I think that you should prove that there exists a problem that was solved by at least 3 boys AND at least 3 girls, instead of trying to prove that there exists a problem solved by at least 3 boys OR at least 3 girls $\endgroup$ – Stefan4024 Oct 26 '16 at 9:38
  • $\begingroup$ @Stefan4024 Isn't the negation of there exists a problem that was solved by atleast 3 boys and atleast 3 girls, its negation is for all questions, at most 2 boys solved it OR at most 2 girls solved it, because I am proceding by contradiction. $\endgroup$ – AspiringMat Oct 26 '16 at 9:41
  • $\begingroup$ Yeah, but your proof isn't alright. You proof that there exists a problem solved by at least 3 boys and a problem that is sovled by at least 3 girls. The thing that you haven't done is to prove that there exists a problem solved by at least 3 boys AND at least 3 girls. For example what if we have a problem that is solved by $3$ boys and $2$ girls? You proof guarantees it's existence, but it doesn't help us at all, as it still satifies the negated condition, namely the second statement, which is enough as it's OR statement. The negated statement hasn't been contradicted yet. $\endgroup$ – Stefan4024 Oct 26 '16 at 10:03
  • $\begingroup$ I think he's trying to investigate that every question is solved either by less than 3 girls OR less than 3 boys - if that is falsified, then SOME question has to be solved by 3 or more girls AND 3 or more boys. $\endgroup$ – Cato Oct 26 '16 at 10:38
  • $\begingroup$ @stefan4024 - 'at most 2 boys or at most two girls' 3 boys and 2 girls does satisfy that condition - he's trying to prove that not all questions can fit into the condition - can you take 3/2 and fit them all into the condition space $\endgroup$ – Cato Oct 26 '16 at 10:43
1
$\begingroup$

We know that there are at least $21^2 = 441$ connections between a boy and a girl. Let $S$ be the set of such connections ($|S| \ge 441$). Now color all the connections with different colours, depending on the problems. We can now write $S=A \cup B \cup C$, where in the subset $A$ are the connections corresponding to problems solved by at most $2$ girls, in $B$ are the connections corresponding to a problem solved by at most $2$ boys and in $C$ are the connections corresponding to a problem solved by at least $3$ boys and at least $3$ girls. Note that each of connection must be in at least one of this sets and also let's note that $A$ and $B$ mustn't be disjoint. Obviously now our goal is to prove that $C \not = \emptyset$.

So now assume that $C = \emptyset$ and pick a random boy and as it has solved at most $6$ problems we have that there at least one of this problem has been solved by at least $3$ girls. So at most $5$ problems have been solved by at most $2$ girls. That means that each boy contributes to a $A$ by at most $5 \cdot 2 = 10$ connections. Therefore we have that $|A| \le 21 \cdot 10 = 210$. Similar reasoning gives us that $|B| \le 21 \cdot 10 = 210$.

So now:

$$|S| = |A \cup B \cup C| = |A \cup B| = |A| + |B| - |A \cap B| \le 210 + 210 = 420$$

But this contradict the fact that $|S| \ge 441$, meaning that our assumption that $C = \emptyset$ is wrong. Therefore there is a connection in $C$ corresponding to a problem solved by at least $3$ boys and at least $3$ girls, guaranteeing the existence of such problem.

$\endgroup$
1
$\begingroup$

An elegant solution can be found here:

https://books.google.nl/books?id=NWhIDQAAQBAJ&pg=PA123&lpg=PA123&dq=21+girls+21+girls+problem+solved+by+at+most+6&source=bl&ots=URHyJ6yHLq&sig=cLbSr7B-cDqMDff2MGs4_zDqPQc&hl=nl&sa=X&ved=0ahUKEwiE5OW4mvjPAhXEVRoKHdH9Ai4Q6AEIOTAE#v=onepage&q=21%20girls%2021%20girls%20problem%20solved%20by%20at%20most%206&f=false

The idea is as follows: Start by making a $21\times 21$ matrix and assign to each problem a different letter. The entry $(i,j)$ consists of letters (problems) that girl $i$, and boy $j$ both solved.

Observation 1: In each row and in each column there will appear at most 6 distinct letters.

Observation 2: There will be at least 11 entries (squares) in each row, that contains a letter that appears at least 3 times in that row. The same holds for every column.

Color the squares that contain a letter that appears at least 3 times in the same row red.

Color the squares that contain a letter that appear at least 3 times in the same column blue.

By a pidgeon hole argument you can show there is a square that is coloured both red and blue, which shows there is a problem that is solved by at least 3 girls, and 3 boys.

Since $21^2 < 21\times 11 + 21\times 11$ there must be a square that is both red and blue.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.