Maths Olympiad Prep

Library / /15 of 18

Combinatorics Difficulty 7.7 National Olympiad, round 2 Prove it Vietnam

The teacher has 20132013 candies of 1111 different types. She distributes the candies to her students such that no student obtains more than one candy of each type. She then asks each pair of students to write down on the board the number of candy types that they have in common. Let MM be the sum of written numbers.

a)
Find the minimum value of MM.

b)
What happens if the teacher has only 99 different types of candy?

Solution

a) Suppose that there are mm students labeled by 1,2,3,,m1,2,3,\ldots,m and 1111 types of candy denoted by a1,a2,a3,,a11a_1,a_2,a_3,\ldots,a_{11}. Let X={a1,a2,a3,,a11}X=\{a_1,a_2,a_3,\ldots,a_{11}\} and A1,A2,,AmA_1,A_2,\ldots,A_m be the set of candy types that the students 1,2,3,,m1,2,3,\ldots,m received, respectively. We have A1,A2,,AmXA_1,A_2,\ldots,A_m \subset X.

For each i=1,2,3,,11i=1,2,3,\ldots,11, let d(ai)d(a_i) be the number of aia_i candies in the total of 20132013 candies. It is clear that
d(a1)+d(a2)+d(a3)++d(a11)=2013. d(a_1)+d(a_2)+d(a_3)+\ldots+d(a_{11})=2013.
We also have M=1i<jmAiAjM = \sum_{1 \le i < j \le m} |A_i \cap A_j|. For each i=1,2,3,,11i=1,2,3,\ldots,11 then the number of subsets containing aia_i is d(ai)d(a_i), so the number of two subsets having a common element aia_i is (d(ai)2)\binom{d(a_i)}{2}. Therefore, we have
M=1i<jmAiAj=i=111(d(ai)2)=12i=111((d(ai))2d(ai)). M = \sum_{1 \le i < j \le m} |A_i \cap A_j| = \sum_{i=1}^{11} \binom{d(a_i)}{2} = \frac{1}{2} \sum_{i=1}^{11} \left( (d(a_i))^2 - d(a_i) \right).
By the Cauchy-Schwarz inequality, we have i=11112i=111(d(ai))2(i=111d(ai))2=20132\sum_{i=1}^{11} 1^2 \cdot \sum_{i=1}^{11} (d(a_i))^2 \ge \left(\sum_{i=1}^{11} d(a_i)\right)^2 = 2013^2,
so
M12(20132112013). M \ge \frac{1}{2} \left( \frac{2013^2}{11} - 2013 \right).
The equality occurs if and only if d(a1)=d(a2)=d(a3)==d(a11)=201311=183d(a_1) = d(a_2) = d(a_3) = \dots = d(a_{11}) = \frac{2013}{11} = 183. In this case, there always exists a certain number of students that satisfy this condition.

b.
Similarly as in the previous case, let b1,b2,b3,,b9b_1, b_2, b_3, \dots, b_9 be the types of candies and d(bi),i=1,9d(b_i), i = 1, 9 be the number of candies of each type. We have
d(b1)+d(b2)+d(b3)++d(b9)=2013. d(b_1) + d(b_2) + d(b_3) + \dots + d(b_9) = 2013.
We need to find the minimum value of i=19(d(bi))2\sum_{i=1}^{9} (d(b_i))^2.
Notice that if there exists d(bi)d(bj)2d(b_i) - d(b_j) \ge 2 for some 1i,j91 \le i, j \le 9 then we can decrease d(bi)d(b_i) by 11 and increase d(bj)d(b_j) by 11 then
(d(bi))2+(d(bj))2(d(bi)1)2(d(bj)+1)2=2(d(bi)d(bj))>0. (d(b_i))^2 + (d(b_j))^2 - (d(b_i) - 1)^2 - (d(b_j) + 1)^2 = 2(d(b_i) - d(b_j)) > 0.
Therefore, to obtain the minimum value, we need d(bi)d(bj)1d(b_i) - d(b_j) \le 1 for all i,j{1,2,3,,9}i, j \in \{1, 2, 3, \dots, 9\}.
Without loss of generality, we assume that d(a1)d(a2)d(a3)d(a9)d(a_1) \le d(a_2) \le d(a_3) \le \dots \le d(a_9). From the above argument, d(ai)d(a_i) can be either k,k+1k, k+1 for some positive integer kk. Suppose that there are tt numbers kk and 9t9-t numbers k+1k+1. We need to find the minimum value of
M=12(tk2+(9t)(k+1)22013) with tk+(9t)(k+1)=2013t=9k2004. M = \frac{1}{2} (tk^2 + (9-t)(k+1)^2 - 2013) \text{ with } tk + (9-t)(k+1) = 2013 \Leftrightarrow t = 9k - 2004.
Substitute into MM, we have
M=12((9k2004)k2+(20139k)(k+1)22013). M = \frac{1}{2}((9k - 2004)k^2 + (2013 - 9k)(k+1)^2 - 2013).
Since 0t90 \le t \le 9, we have 09k2004920049k20139k=2230 \le 9k - 2004 \le 9 \Rightarrow \frac{2004}{9} \le k \le \frac{2013}{9} \Rightarrow k = 223.
With k=223k=223 then M=12(32232+622422013)M = \frac{1}{2}(3 \cdot 223^2 + 6 \cdot 224^2 - 2013).
In this case, the minimum value is M=12(32232+622422013)M = \frac{1}{2}(3 \cdot 223^2 + 6 \cdot 224^2 - 2013) which can be obtained when we have 33 numbers 223223 and 66 numbers 224224.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.