Maths Olympiad Prep

Library / /54 of 65

Number theory Difficulty 6.4 National Olympiad Prove it Bulgaria

Problem:
Let MM be the set of the rational numbers in the interval (0,1)(0,1). Does there exist a subset AA of MM such that every number from MM can be represented in a unique way as a sum of one or finitely many distinct numbers from AA?

Solution

Solution:
Assume, for a contradiction, that there exists such a set.

We first prove that if aAa \in A, then A(a2,a)=A \cap \left(\frac{a}{2}, a\right) = \varnothing. To do this suppose the contrary, i.e. there exists aa' in AA and a>a>a2a > a' > \frac{a}{2}. Then the number aa<a2a - a' < \frac{a}{2} can be represented as a sum of one or finitely many different numbers from AA. Since each of these numbers is less than a2\frac{a}{2}, the number a=a+(aa)a = a' + (a - a') has two different representations of the required type (as aa and as aa' plus the numbers of the representation of aaa - a'), a contradiction.

In particular, it follows from the above that in every interval [12i,12i1)\left[\frac{1}{2^i}, \frac{1}{2^{i-1}}\right), i=1,2,i = 1, 2, \ldots, there is at most one element of AA. Since the set AA is infinite (otherwise we can obtain only a finite number of sums of different numbers from AA) it easily follows that the numbers of AA can be ordered in an infinite sequence a1,a2,a_1, a_2, \ldots, which satisfies ai2ai+1a_i \geq 2 a_{i+1} for every ii. If this inequality is strict for some ii, then
s=i=2ai<i=2a12i1=a1 s = \sum_{i=2}^{\infty} a_i < \sum_{i=2}^{\infty} \frac{a_1}{2^{i-1}} = a_1
This shows that the numbers from the interval (s,a1)(s, a_1) cannot be represented as a sum of one or finitely many different numbers from AA.

Therefore ai+1=a12ia_{i+1} = \frac{a_1}{2^i} for every ii. Now it is easy to see that only the numbers of the form a1m2na_1 \frac{m}{2^n} can be represented as a sum of one or a finite number of different numbers from AA. Thus any rational number with an odd denominator which is coprime with the denominator of a1a_1 cannot be represented as required. This is a contradiction which completes the proof.

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.