Boys and Girls Compete in Maths
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.
The problem comes from the IMO 2001 (Problem #3). It was posted at the wu::forums and solved by the participant bearing pseudonym of "Hippo".
The solution is short and elegant.
|Contact| |Front page| |Contents| |Up|
Copyright © 1996-2018 Alexander Bogomolny21 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
|Contact| |Front page| |Contents| |Up|
Copyright © 1996-2018 Alexander Bogomolny71550556