Question

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

Answer 1

Answer:

For each boy , we know that there is a girl who solved a question in with him. Since a boy solve at most six questions, for a boy and his set of such questions there are at least 11 girls who solve a question in common with the boy such that at least three boys solve that common question. The girls have solved a total of at most 21×6 questions, this can be view as a set with repeated element i.e if a question is solved by more than one girl it appears as many times as the number of girls who have solved it. Let these set of questions be noted as A. Clearly, set A has a size 21×6. We mark each question in set A which has been solved by at least three girls and a boy and we mark it the number of times that is the same as the number of boys that have solved it. Since there are total of 21×11 marks (since there are at least 11 marks for each boy, either a question is marked at least three times, in which case we are done since it has been solved by at least three girls and three boys. Or each question has been marked at most twice. In this case it is clear that more than 21×5 questions in set A have been marked since 26×5×4<21×11 (there are total of 21×11 marks). This implies that there is a girl such that all six of her questions have been marked. By then there must be a question that this girl has solved which has also been solved by at least three boys. Therefore, it must be true that there is a question such that it has been solved by at least three people of each gender.