Olympiad Maths Prep

Library / /4 of 4

Combinatorics Difficulty 4.6 AIME Prove it Turkey

Each student in the class has chosen one mathematics and one physics problem out of 2020 mathematics and 1111 physics problems such that different students choose different pairs of problems. Given that for each student, at least one of the problems chosen by him is chosen by at most one more student, determine the maximum possible number of students in the class.

Solution

For 1i201 \le i \le 20 and 1j111 \le j \le 11 we define ai,ja_{i,j} as follows; ai,j=1a_{i,j} = 1 if the ii-th mathematics problem and jj-th physics problem are chosen by some student, ai,j=0a_{i,j} = 0 otherwise. Now we can reformulate the problem: Find the maximal possible value of the expression
A=i=120j=111ai,j under the following two conditions: A = \sum_{i=1}^{20} \sum_{j=1}^{11} a_{i,j} \text{ under the following two conditions:}
 ai,j=0 or 1 \bullet\ a_{i,j} = 0 \text{ or } 1
* if ak,l=1a_{k,l} = 1 for some kk and ll, then at least one of the sums j=111ak,j\sum_{j=1}^{11} a_{k,j} and i=120ai,l\sum_{i=1}^{20} a_{i,l} does not exceed 22.

First of all, let us show that A54A \le 54. Suppose that ak,l=1a_{k,l} = 1. We say that kk is *1-good*, if
j=111ak,j2; we say that l is 2-good if i=120ai,l2. \sum_{j=1}^{11} a_{k,j} \le 2; \text{ we say that } l \text{ is 2-good if } \sum_{i=1}^{20} a_{i,l} \le 2.
If the total number of 1-good values of kk is 2020, then A220=40A \le 2 \cdot 20 = 40.
If the total number of 2-good values of ll is 1111, then A211=22A \le 2 \cdot 11 = 22.
If the total number of 1-good values of kk is 1919, then A219+11=49A \le 2 \cdot 19 + 11 = 49.
If the total number of 2-good values of ll is 1010, then A211+20=32A \le 2 \cdot 11 + 20 = 32.
Finally, if the total number of 1-good values of kk is less than or equal to 1818 and the total number of 2-good values of ll is less than or equal to 99, then the total number of good values is at most 2727 and readily A227=54A \le 2 \cdot 27 = 54, since the number of nonzero terms of AA is less than or equal to twice the number of good values. Thus, A54A \le 54.

Now we give an example for A=54A = 54. Let ai,j=1a_{i,j} = 1 only for
(i,j){(i,j):i{1,20} or j{1,11}}{(1,1),(20,1),(1,11),(20,11)}. (i,j) \in \{(i,j) : i \in \{1,20\} \text{ or } j \in \{1,11\}\} \setminus \{(1,1), (20,1), (1,11), (20,11)\}.
The conditions are readily satisfied and we are done.

Looking for a route rather than 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.