Maths Olympiad Prep

Library / /21 of 53

Number theory Difficulty 6.4 National olympiad Prove it Vietnam

Find all sets of 2014 rational numbers not necessarily distinct such that: If an arbitrary number in the set is removed, one always can divide the remaining 2013 numbers into three sets such that each set has exactly 671 elements and the products of all elements in each set are equal.

Solution

Suppose that the tuple (a1,a2,,a2014)(a_1, a_2, \dots, a_{2014}) satisfies the given condition. We investigate two following cases.

Case 1. If there exists a zero in this tuple, it is easy to check that there are at least four zeros. Otherwise, if the tuple has four zeros then it satisfies the given condition.

Case 2. Suppose that ai0a_i \neq 0 for all ii, 1i20141 \le i \le 2014. Denote ai=xi/yia_i = x_i/y_i where xi,yiZ+x_i, y_i \in \mathbb{Z}^+ and gcd(xi,yi)=1\gcd(x_i, y_i) = 1. It is clear that the tuple (a1,,a2014)(a_1, \dots, a_{2014}) satisfies the given condition if and only if the sequence (ta1,,ta2014)(t a_1, \dots, t a_{2014}) is satisfied, where tt is the least common multiple of y1,,y2014y_1, \dots, y_{2014}. Hence, we can assume that aia_i's are nonzero integers.

For any prime pp, denote Zp=(z1,z2,,z2014)Z_p = (z_1, z_2, \dots, z_{2014}) to be the set of exponents of pp in (a1,a2,,a2014)(a_1, a_2, \dots, a_{2014}). Then ZpZ_p is a set of non-negative integers with the following condition: if we remove an arbitrary number from them, then the remaining numbers can be divided into 3 separate groups of 671 elements that have the same sum of all elements. (♣)

We will show that all elements of ZpZ_p are equal. Otherwise, suppose that z1,,z2014z_1, \dots, z_{2014} are not the same, then we can choose a set where the value of z=z1+z2++z2014z = z_1 + z_2 + \dots + z_{2014} is smallest. Note that if we remove ziz_i then the remaining elements can be divided into three groups of equal sums, hence zzi(mod3)z \equiv z_i \pmod 3 for all i=1,2,,2014i = 1, 2, \dots, 2014. Hence, we investigate three sub-cases.

2.1. Suppose that zi0(mod3)z_i \equiv 0 \pmod 3 for all i=1,2,,2014i = 1, 2, \dots, 2014. Then the set
(z13,z23,,z20143) \left( \frac{z_1}{3}, \frac{z_2}{3}, \dots, \frac{z_{2014}}{3} \right)
also satisfies condition ♣ with the sum of elements smaller than zz. This is a contradiction.

2.2. Suppose that zi1(mod3)z_i \equiv 1 \pmod 3 for all i=1,2,,2014i = 1, 2, \dots, 2014. Then consider the set
(z1+23,z2+23,,z2014+23), \left( \frac{z_1+2}{3}, \frac{z_2+2}{3}, \dots, \frac{z_{2014}+2}{3} \right),
we also have a contradiction.

2.3. Suppose that zi2(mod3)z_i \equiv 2 \pmod 3 for all i=1,2,,2014i = 1, 2, \dots, 2014. Consider the set
(z1+13,z2+13,,z2014+23), \left( \frac{z_1+1}{3}, \frac{z_2+1}{3}, \dots, \frac{z_{2014}+2}{3} \right),
and we also have a contradiction.

Therefore, we always have z1=z2==z2014z_1 = z_2 = \cdots = z_{2014} for all pp. This implies that the absolute values of aia_i's are all the same.

Let 0k20140 \le k \le 2014 be the number of negative numbers in aia_i's. One can check that all possible values of kk are k{1,2,2012,2013}k \notin \{1, 2, 2012, 2013\}.

In conclusion, all 2014-tuples satisfying the given condition are:
* the tuple contains at least 4 zeros, or
* the tuple contains 2014 numbers of the same nonzero absolute values, and let 0k20140 \le k \le 2014 be the number of negative numbers in the tuple then k{1,2,2012,2013}k \notin \{1, 2, 2012, 2013\}.

\boxed{}

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 and solution reproduced as published; topic and difficulty added by this site.