Maths Olympiad Prep

Library / /55 of 62

Number theory Difficulty 7.0 National Olympiad, round 2 Prove it Ukraine

a) Does there exist a set AA that has 20162016 pairwise different positive integers and such a property: for every non-empty subset BAB \subset A that is not equal to AA and every non-empty subset C(AB)C \subset (A \setminus B) the sum of the elements of subset BB is not divisible by the sum of the elements of subset CC?

b) Does there exist a set AA that has 20162016 pairwise different positive integers and such a property: for every non-empty subset BAB \subset A that is not equal to AA and contains at least 22 elements and every non-empty subset C(AB)C \subset (A \setminus B) the product of the elements of subset BB is divisible by the sum of the elements of subset CC?

Solution

a)
Let us firstly choose numbers in such a way: 2,3,5,,p20162, 3, 5, \ldots, p_{2016}, where pip_i is a prime number in increasing order. Then we will write down all the possible combinations of subsets BB and CC. Its amount is finite. Let there are NN such pairs. Successively we will change the elements in a particular way. And we will build ordered set AA, at every step we will change some of its elements comparing with the previous step. We will identify the elements as a1,a2,,a2016a_1, a_2, \ldots, a_{2016} (at the 00 step (at the beginning) ai=pia_i = p_i, i=1,,2016i=1, \ldots, 2016). Elements of the sets BB and CC will be determined by their indices. For instance, B={1,4,2000}B = \{1, 4, 2000\} means that the set BB includes a1,a4a_1, a_4 and a2000a_{2000} elements of AA, after their change at the previous step.

Let us look at the sets A,B,CA, B, C in kk-th row. Let p=p2016+kp = p_{2016+k}. Now we multiply all the elements of the set CC by pp, and from the elements of the set BB - the first element (with the lowest index aja_j) we do not multiply by pp, and the rest of the elements (if the set BB contains only one element, we do not have the rest) multiply by pp. Thus the sum of the elements of the set BB is not divisible by pp, and the sum of the elements of the set CC is divisible by pp, hence the sum of the elements of BB is not divisible by the sum of the elements of CC.

In such a way we will make NN steps and show that the obtained set satisfies the conditions.

Let us choose sets BB and CC arbitrarily (the sets are determined by the sets of indices), let it correspond to kk-th row of the table. Then from the elements of set BB all but one are divisible by p2016+kp_{2016+k}, and among elements of set CC all are divisible by it, as is the sum.

It is clear that similarly we can build a corresponding set, that contains arbitrarily finite amount of pairwise distinct elements.

b)
Let us show how such a set can be built for arbitrarily finite amount of elements nn. Let N=(n(n+1)2)!N = \left(\frac{n(n+1)}{2}\right)!. Let us build the corresponding set: ai=iNa_i = i \cdot N, i=1,,ni=1, \ldots, n. Let us show that it satisfies the conditions. Consider any subset CC, sum of its elements LL is not greater than LM=(1+2++n)N=n(n+1)2NL \le M = (1+2+\ldots+n) \cdot N = \frac{n(n+1)}{2} N, thus it can be written as KNK \cdot N, where Kn(n+1)2K \le \frac{n(n+1)}{2}. The product of any two numbers of the set AA is divisible by N2N^2, thus it is divisible by LL, since NN is divisible by any number less than n(n+1)2\frac{n(n+1)}{2}, thus it is divisible by KK.

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.