Let be a positive integer. Suppose some collection of integers are written on a blackboard satisfying the following properties.
* Every number written satisfies .
* Every with is written at least once.
* The sum of all the numbers written is even.
Prove that by marking some of the numbers written by and the rest by , it is possible to make the sum of those marked by equal to the sum of those marked by .
Solutions — 2
Solution 1
Suppose we line up the numbers written on the blackboard in a non-increasing order and represent them as , with for each . We mark each of the numbers by or in order in the following way. Start with , and at each step compare the sum of those numbers already marked by with the sum of those already marked by . If the former is less than the latter then mark the next number by , otherwise mark it by .
Let us show by induction on that after the time when the number gets marked, the difference between the sum of those numbers marked by and the sum of those marked by is no bigger than .
For , this difference is clearly .
Suppose the assertion holds for . Let us denote by the difference of the sum of those numbers marked by and the sum of those marked by prior to the time of the marking of . By the rule of our marking procedure, this difference after the marking of becomes . In view of the assumptions made on the numbers on the blackboard to begin with, we have or . By the induction hypothesis, we have , and therefore, we get .
Thus we conclude that the assertion holds for .
Since the last number , we see that the difference of those numbers marked by and those marked by when the markings of all the numbers are done does not exceed 1. On the other hand, since by assumption the sum of all the numbers written on the blackboard is even, the difference of the sum of those marked by and those marked by cannot equal 1. Thus, we can conclude that the two sums in question must coincide.
Solution 2
Since there are only finite number of possibilities for marking the given set of numbers by and , there must be ways to get the marking done for which the difference of the sum of those marked by and the sum of those marked by is the minimum. Choose one such method of marking. We will show that for this choice of the marking method the difference in question must be 0. Suppose on the contrary this difference is greater than 0. Since the sum of all the numbers given is even, this difference cannot be equal to 1, and hence is greater than or equal to 2. Without the loss of generality, we may assume that the sum of those numbers marked by is bigger. Now consider the following procedure:
Denote by the number smallest among the numbers marked by .
If , then choose one of those 's marked by and change its marking to .
If , then choose one of those 's marked by and change its marking to and choose one of those 's marked by and change its marking to .
We note that the procedure outlined above is possible, since by assumption the sum of the numbers marked by is greater than the sum of those marked by so there exist numbers marked by and thus we can choose the one smallest among them. Furthermore, if , then by assumption there must be at least one among the numbers written on the blackboard and all those must be marked by .
Finally, we see that after performing the procedure above, we end up with the situation where the difference of the sum of those marked by and the sum of those marked by is 2 less than the case for the marking method chosen originally, and this contradicts the minimality assumption. Thus the difference in question for the marking method chosen originally must equal 0.