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.
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.
Make a sheet 21×21; rows are boys, columns are girls. For each problem, color it boy if at least 3 boys solved it, color it girl if at least 3 girls solved it. Write to the corresponding cell of the table an arbitrary problem solved by both the girl and the boy and if the problem is colored, color the cell. Suppose at first no cell is colored both girl and boy.
Lemma: Now in each row(boy) there is at least 11 girl colored cells, and in each column(girl) there is at least 11 boy colored cells.
Summed together there are at least 21·11 girl colored cells and 21·11 boy colored cells 21·11·2>21·21 therefore a cell is colored by both boy and girl ... contradiction.
So the lemma: For a given person, maximize the number of problems solved by the person which were solved by at most 2 persons of opposite sex. Clearly 2×5 is the maximum, therefore 21 - 10 = 11 is the lower bound for the number of problems colored by the opposite sex.
