Maths Olympiad Prep

Library / Auswahlklausur /16 of 31

Auswahlklausur

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 ∑s∈S1/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 1∉M1 \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 mi≥2mi−1m_{i} \geq 2 m_{i-1} for all i≥2i \geq 2. Then mi≥2i−1m1m_{i} \geq 2^{i-1} m_{1} holds for all i≥1i \geq 1, and it follows that
r∗:=∑i=1∞1mi≤∑i=0∞12im1=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 m1≥3m_{1} \geq 3 or mi>2mi−1m_{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=2mi−1m_{i} = 2 m_{i-1} for all ii, so MM consists exactly of the powers of two greater than 11. Since 1/3=∑i=2∞2−i1 / 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<2mi−1m_{i} < 2 m_{i-1}. We consider
r:=1mi−1−1mi<1mi. r := \frac{1}{m_{i-1}} - \frac{1}{m_{i}} < \frac{1}{m_{i}}.
By assumption there exists a finite subset S⊂MS \subset M such that ∑s∈S1/s=r\sum_{s \in S} 1 / s = r holds. Because s<1/mis < 1 / m_{i}, we have mi∉Sm_{i} \notin S. But then S1=S∪{mi}S_{1} = S \cup \{m_{i}\} and S2={mi−1}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/mi−11 / m_{i-1}, which is a contradiction.

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