a) Suppose that there are m students labeled by 1,2,3,…,m and 11 types of candy denoted by a1,a2,a3,…,a11. Let X={a1,a2,a3,…,a11} and A1,A2,…,Am be the set of candy types that the students 1,2,3,…,m received, respectively. We have A1,A2,…,Am⊂X.
For each i=1,2,3,…,11, let d(ai) be the number of ai candies in the total of 2013 candies. It is clear that
d(a1)+d(a2)+d(a3)+…+d(a11)=2013.
We also have M=∑1≤i<j≤m∣Ai∩Aj∣. For each i=1,2,3,…,11 then the number of subsets containing ai is d(ai), so the number of two subsets having a common element ai is (2d(ai)). Therefore, we have
M=1≤i<j≤m∑∣Ai∩Aj∣=i=1∑11(2d(ai))=21i=1∑11((d(ai))2−d(ai)).
By the Cauchy-Schwarz inequality, we have ∑i=11112⋅∑i=111(d(ai))2≥(∑i=111d(ai))2=20132,
so
M≥21(1120132−2013).
The equality occurs if and only if d(a1)=d(a2)=d(a3)=⋯=d(a11)=112013=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,…,b9 be the types of candies and d(bi),i=1,9 be the number of candies of each type. We have
d(b1)+d(b2)+d(b3)+⋯+d(b9)=2013.
We need to find the minimum value of ∑i=19(d(bi))2.
Notice that if there exists d(bi)−d(bj)≥2 for some 1≤i,j≤9 then we can decrease d(bi) by 1 and increase d(bj) by 1 then
(d(bi))2+(d(bj))2−(d(bi)−1)2−(d(bj)+1)2=2(d(bi)−d(bj))>0.
Therefore, to obtain the minimum value, we need d(bi)−d(bj)≤1 for all i,j∈{1,2,3,…,9}.
Without loss of generality, we assume that d(a1)≤d(a2)≤d(a3)≤⋯≤d(a9). From the above argument, d(ai) can be either k,k+1 for some positive integer k. Suppose that there are t numbers k and 9−t numbers k+1. We need to find the minimum value of
M=21(tk2+(9−t)(k+1)2−2013) with tk+(9−t)(k+1)=2013⇔t=9k−2004.
Substitute into M, we have
M=21((9k−2004)k2+(2013−9k)(k+1)2−2013).
Since 0≤t≤9, we have 0≤9k−2004≤9⇒92004≤k≤92013⇒k=223.
With k=223 then M=21(3⋅2232+6⋅2242−2013).
In this case, the minimum value is M=21(3⋅2232+6⋅2242−2013) which can be obtained when we have 3 numbers 223 and 6 numbers 224.