Maths Olympiad Prep

Library / Vietnamese Mathematical Olympiad /27 of 68

Vietnamese Mathematical Olympiad

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 ai≠0a_i \neq 0 for all ii, 1≤i≤20141 \le i \le 2014. Denote ai=xi/yia_i = x_i/y_i where xi,yi∈Z+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 z≡zi(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 zi≡0(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 zi≡1(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 zi≡2(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 0≤k≤20140 \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 0≤k≤20140 \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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.