Question

Suppose that 21 girls and 21 boys enter a mathemat- ics 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

Individuals shall draw a table consisting of 21 boys in each column and 21 girls in each row as shown on the image below.

The table will have 21x21 = 441 boxes. Mark each box with a letter showing the problem solved by both that boy and girl. Since at least one problem was solved by a girl and a boy, therefore each box will have a letter. Each entrant solved at most six questions, so there can be at most six letters in any row or column. This means six different letters can be there in a row only if at least 11 of the boxes contain letters appearing three or more times in the row. Individuals go through each row and color all the boxes, say blue. Therefore, 11 boxes in each row must be colored blue.

The number of the boxes that must be colored blue = 21 x 11 = 231. Individuals can apply the same process to the columns and color at least 231 boxes, say green. But the total boxes are 441 only. Therefore, by Pigeonhole principle, there will be some boxes which will be both blue and green. The problem of doubly colored boxes represents a problem solved by at least three boys and three girls.