Browse · MathNet
PrintNational Olympiad of Argentina
Argentina counting and probability
Problem
In a school with 5 grades there are 250 girls and 250 boys. Each grade has 100 students. Teams of one girl and one boy from the same grade must be formed for a contest. At least 19 students in each grade are girls and at least 19 are boys. Find the greatest number of teams that can be formed with certainty.
Solution
The answer is . Let there be girls and boys in grade , . Consider a table with in the first row and in the second row. Mark the smaller of the numbers for each . The number of teams that can be formed is the sum of the five marked numbers. At least three marked numbers are in the same row. Suppose for instance that are marked. Since , and , each of and is at most . Because , it follows that .
Due to , , the number of teams in grades 1, 2, 3 is , hence it is at least . Also at least teams can be formed in each of grades 4 and 5. So teams can be formed always. The example , shows that is the greatest number in question.
Due to , , the number of teams in grades 1, 2, 3 is , hence it is at least . Also at least teams can be formed in each of grades 4 and 5. So teams can be formed always. The example , shows that is the greatest number in question.
Final answer
126
Techniques
Pigeonhole principleColoring schemes, extremal arguments