2015 USAMO Problems/Problem 1

Let the set be {-1007, -1006, ...0,1,2...1006, 1007],namely all the consecutive integers from -1007 to 1007. Notice that the operation does not change the sum or the mean of the set, which is 0.

There are 1007 pairs of opposite integers {a,-a}. After the first two elements are chosen, there are at least 1005 such pair. For each such pair we perform the operation of average, hence reducing these 2010 elements to 0. Then use the other 5 elements together with three 0's produced to form the group of eight: {a1,a2,a3,a4,a5,a6=0,a7=0,a8=0}, and perform the operation in the following order: (a1,a2)-> (m1,m1), (a3,a4)->(m2,m2), (a3,a4)->(m3,m3), (a3,a4)->(m4,m4), where m1=(a1+a2)/2, etc. Then, (m1,m2)->(m11, m11) for two groups, (m3,m4)->(m12,m12) for the other two groups, and finally (m11,m12) -> (m111, m111) for all the eight elements. Since the sum of the eight-group is 0, m111 must also be 0. Therefore, all the elements are reduced to 0.

The key to the algorithm is to form 2^k subset, which is guaranteed to be reducible to all the members of the same value, namely the mean. Then before that if we could always choose M >=N-2^k members to form pairs, each yielding the average of the total group, then all the members are reduced to the average. Under the condition that two arbitrary elements are chosen first, we need only N>=4 to guarantee this result. But for N=2 the first operation leads to equal elements, so N=3 is the only case when all the members may not be reduced to average.