Maths Olympiad Prep

Library / /450 of 520

Combinatorics Difficulty 6.9 National olympiad Prove it

Example 4 Assume that 2n+12 n+1 positive integers a1,a2,,a2n+1a_{1}, a_{2}, \cdots, a_{2 n+1} have the property: any 2n2 n of these numbers can be divided into two disjoint nn-element subsets, and the sums of the nn numbers in the two subsets are equal, then these 2n+12 n+1 numbers must all be equal.

Solution

To prove that if there are 2n+12n+1 positive integers satisfying the property described in the problem, we call these 2n+12n+1 positive integers a "good array". Let's assume a1a2a2n+1a_{1} \leqslant a_{2} \leqslant \cdots \leqslant a_{2 n+1}, and a1=1a_{1}=1 (because reducing the smallest number to 1 and subtracting the same number from the other numbers still results in a "good array").

From the problem statement, we know that 2((i=12n+1ai)aj)(j=1,2,3,,2n+1)2 \mid\left(\left(\sum_{i=1}^{2 n+1} a_{i}\right)-a_{j}\right)(j=1,2,3, \cdots, 2 n+1), which means a1a2a3a4a2n+1i=12n+1ai(mod2)a_{1} \equiv a_{2} \equiv a_{3} \equiv a_{4} \equiv \cdots \equiv a_{2 n+1} \equiv \sum_{i=1}^{2 n+1} a_{i}(\bmod 2).

Since a1=1a_{1}=1, it follows that a1,a2,a3,,a2n+1a_{1}, a_{2}, a_{3}, \cdots, a_{2 n+1} are all positive odd numbers.
Let bi=ai+12(i=1,2,,2n+1)b_{i}=\frac{a_{i}+1}{2}(i=1,2, \cdots, 2 n+1). Since a1,a2,,a2n+1a_{1}, a_{2}, \cdots, a_{2 n+1} are all positive odd numbers, b1,b2,b3,,b2n+1b_{1}, b_{2}, b_{3}, \cdots, b_{2 n+1} are all positive integers and it is easy to see that b1,b2,b3,,b2n+1b_{1}, b_{2}, b_{3}, \cdots, b_{2 n+1} also form a "good array".

If x>1x > 1, then b2n+1=a2n+1+12<a2n+1b_{2 n+1}=\frac{a_{2 n+1}+1}{2}<a_{2 n+1}. Repeatedly performing this transformation, we will eventually obtain a "good array" whose maximum term is 1. Since in the above transformation, the smallest term in each array is always 1, the terms in this "good array" are all 1. Considering the way the transformation is performed (changing xx to x+12\frac{x+1}{2}), it follows that the original 2n+12n+1 numbers a1,a2,,a2n+1a_{1}, a_{2}, \cdots, a_{2 n+1} are all 1.

This completes the proof of the original proposition.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.