Maths Olympiad Prep

Track / Stage 5 / 44 of 400 #1124 of 2444

Problem 1124

AIME late
Combinatorics Difficulty 5.1 Prove it China Western Mathematical Olympiad · 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.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

Let aia_i be the number of boy students in the iith\text{th} row, then the number of girl students in this row is 75 - a_i.Bythegivencondition,wehave. By the given condition, we have i=122(Cai2+C75ai2)11×C752\sum_{i=1}^{22} \left( C_{a_i}^2 + C_{75-a_i}^2 \right) \le 11 \times C_{75}^2.Thatis,. That is, i=122\sum_{i=1}^{22} (a_i^2 - 75a_i) \le -30,525,implying, implying i=122\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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.