|
|
|
|
|
|
|
|
|
 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.
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
|
| 28735586 |  |
|