Maths Olympiad Prep

Library / /8 of 11

Combinatorics Difficulty 6.5 National olympiad Prove it Argentina

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 126126. Let there be aia_i girls and bib_i boys in grade ii, 1i51 \le i \le 5. Consider a 2×52 \times 5 table with a1,,a5a_1, \dots, a_5 in the first row and b1,,b5b_1, \dots, b_5 in the second row. Mark the smaller of the numbers ai,bia_i, b_i for each ii. 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 a1,a2,a3a_1, a_2, a_3 are marked. Since b419b_4 \ge 19, b519b_5 \ge 19 and a4+b4=a5+b5=100a_4+b_4 = a_5+b_5 = 100, each of a4a_4 and a5a_5 is at most 10019=81100-19=81. Because a1+a2+a3+a4+a5=250a_1 + a_2 + a_3 + a_4 + a_5 = 250, it follows that a1+a2+a3=250(a4+a5)250281=88a_1 + a_2 + a_3 = 250 - (a_4 + a_5) \ge 250 - 2 \cdot 81 = 88.

Due to aibia_i \le b_i, 1i31 \le i \le 3, the number of teams in grades 1, 2, 3 is a1+a2+a3a_1 + a_2 + a_3, hence it is at least 8888. Also at least 1919 teams can be formed in each of grades 4 and 5. So 88+219=12688+2 \cdot 19 = 126 teams can be formed always. The example (a1,a2,a3,a4,a5)=(29,29,30,81,81)(a_1, a_2, a_3, a_4, a_5) = (29, 29, 30, 81, 81), (b1,b2,b3,b4,b5)=(71,71,70,19,19)(b_1, b_2, b_3, b_4, b_5) = (71, 71, 70, 19, 19) shows that 126126 is the greatest number in question.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.