Maths Olympiad Prep

Library / /4 of 54

Combinatorics Difficulty 5.1 AIME, harder Prove it China

Arrange 16501\,650 students in 2222 rows by 7575 columns. It is known that for any two columns, the number of occasions that two students in the same row are of the same sex does not exceed 1111. Prove that the number of boy students does not exceed 928928.

Solution

Let aia_i be the number of boy students in the ii\text{th}row,thenthenumberofgirlstudentsinthisrowis row, then the number of girl students in this row is 75 - a_i.Bythegivencondition,wehave. By the given condition, we have \sum_{i=1}^{22} \left( C_{a_i}^2 + C_{75-a_i}^2 \right) \le 11 \times C_{75}^2.Thatis,. That is, \sum_{i=1}^{22} (a_i^2 - 75a_i) \le -30,525,implying, implying \sum_{i=1}^{22} (2a_i - 75)^2 \le 1,650$. Using Cauchy's Inequality, we have
[i=122(2ai75)]222i=122(2ai75)236,300. \left[ \sum_{i=1}^{22} (2a_i - 75) \right]^2 \le 22 \sum_{i=1}^{22} (2a_i - 75)^2 \le 36,300.
Then i=122(2ai75)<191\sum_{i=1}^{22} (2a_i - 75) < 191, and i=122ai<191+1,6502<921\sum_{i=1}^{22} a_i < \frac{191 + 1,650}{2} < 921. That means the number of boy students does not exceed 928928.

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.