Maths Olympiad Prep

Library / /17 of 30

Number theory Difficulty 8.3 Shortlist Prove it Germany

Problem:

Decide whether there exists a set MM of positive integers with the following property: For every positive rational number r<1r<1 there exists exactly one finite subset SS of MM such that sS1/s=r\sum_{s \in S} 1 / s = r holds, that is, the sum of the reciprocals of all elements of SS equals rr.

Solution

Solution:

No such set exists, which we will show by a proof by contradiction. Suppose SS has the stated property. Clearly MM is then infinite, and we may assume without loss of generality that 1M1 \notin M. We denote the elements of MM, ordered by size, by m1<m2<m3<m_{1} < m_{2} < m_{3} < \ldots.

Case 1: We have mi2mi1m_{i} \geq 2 m_{i-1} for all i2i \geq 2. Then mi2i1m1m_{i} \geq 2^{i-1} m_{1} holds for all i1i \geq 1, and it follows that
r:=i=11mii=012im1=2m1, r^{*} := \sum_{i=1}^{\infty} \frac{1}{m_{i}} \leq \sum_{i=0}^{\infty} \frac{1}{2^{i} m_{1}} = \frac{2}{m_{1}},
that is, if m13m_{1} \geq 3 or mi>2mi1m_{i} > 2 m_{i-1} holds for at least one ii, then r<1r^{*} < 1. In this case, however, MM does not satisfy the condition stated in the problem text, contrary to the assumption, if s(r,1)s \in (r^{*}, 1) is chosen. Thus we must have m1=2m_{1} = 2 and mi=2mi1m_{i} = 2 m_{i-1} for all ii, so MM consists exactly of the powers of two greater than 11. Since 1/3=i=22i1 / 3 = \sum_{i=2}^{\infty} 2^{-i} cannot be written as a finite sum of reciprocals of powers of two, we also get a contradiction in this case.

Case 2: There exists an i>1i > 1 such that mi<2mi1m_{i} < 2 m_{i-1}. We consider
r:=1mi11mi<1mi. r := \frac{1}{m_{i-1}} - \frac{1}{m_{i}} < \frac{1}{m_{i}}.
By assumption there exists a finite subset SMS \subset M such that sS1/s=r\sum_{s \in S} 1 / s = r holds. Because s<1/mis < 1 / m_{i}, we have miSm_{i} \notin S. But then S1=S{mi}S_{1} = S \cup \{m_{i}\} and S2={mi1}S_{2} = \{m_{i-1}\} are two distinct finite subsets of MM such that the sums of the reciprocals of S1S_{1} and S2S_{2} both equal 1/mi11 / m_{i-1}, which is a contradiction.

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 translated into English from de; metadata (topic, difficulty) added by this project.