Maths Olympiad Prep

Library / /48 of 94

Combinatorics Difficulty 6.7 National Olympiad Prove it Japan

Let NN be a positive integer. Suppose some collection of integers are written on a blackboard satisfying the following properties.
* Every number kk written satisfies 1kN1 \le k \le N.
* Every kk with 1kN1 \le k \le N is written at least once.
* The sum of all the numbers written is even.
Prove that by marking some of the numbers written by O\mathcal{O} and the rest by ×\times, it is possible to make the sum of those marked by O\mathcal{O} equal to the sum of those marked by ×\times.

Solutions — 2

Solution 1

Suppose we line up the numbers written on the blackboard in a non-increasing order and represent them as a1,a2,,ama_1, a_2, \dots, a_m, with akak+1a_k \ge a_{k+1} for each kk. We mark each of the numbers a1,a2,,ama_1, a_2, \dots, a_m by \bigcirc or ×\times in order in the following way. Start with a1a_1, and at each step compare the sum of those numbers already marked by \bigcirc with the sum of those already marked by ×\times. If the former is less than the latter then mark the next number by \bigcirc, otherwise mark it by ×\times.
Let us show by induction on ii that after the time when the number aia_i gets marked, the difference between the sum of those numbers marked by \bigcirc and the sum of those marked by ×\times is no bigger than aia_i.
For i=1i=1, this difference is clearly a1a_1.
Suppose the assertion holds for i=k1i = k-1. Let us denote by dd the difference of the sum of those numbers marked by \bigcirc and the sum of those marked by ×\times prior to the time of the marking of aka_k. By the rule of our marking procedure, this difference after the marking of aka_k becomes dak|d - a_k|. In view of the assumptions made on the numbers on the blackboard to begin with, we have ak1=aka_{k-1} = a_k or =ak+1= a_k + 1. By the induction hypothesis, we have 0dak+10 \le d \le a_k + 1, and therefore, we get akdak1ak-a_k \le d - a_k \le 1 \le a_k.
Thus we conclude that the assertion holds for i=ki = k.
Since the last number am=1a_m = 1, we see that the difference of those numbers marked by O\mathcal{O} and those marked by ×\times 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 O\mathcal{O} and those marked by ×\times 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 O\mathcal{O} and ×\times, there must be ways to get the marking done for which the difference of the sum of those marked by O\mathcal{O} and the sum of those marked by ×\times 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 O\mathcal{O} is bigger. Now consider the following procedure:
Denote by tt the number smallest among the numbers marked by O\mathcal{O}.
If t=1t=1, then choose one of those 11's marked by O\mathcal{O} and change its marking to ×\times.
If t>1t > 1, then choose one of those tt's marked by O\mathcal{O} and change its marking to ×\times and choose one of those t1t-1's marked by ×\times and change its marking to O\mathcal{O}.
We note that the procedure outlined above is possible, since by assumption the sum of the numbers marked by O\mathcal{O} is greater than the sum of those marked by ×\times so there exist numbers marked by O\mathcal{O} and thus we can choose the one smallest among them. Furthermore, if t>1t > 1, then by assumption there must be at least one t1t-1 among the numbers written on the blackboard and all those must be marked by ×\times.
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 O\mathcal{O} and the sum of those marked by ×\times 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.

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.