Maths Olympiad Prep

Library / /3 of 9

Number theory Difficulty 6.0 National Olympiad Prove it Switzerland

Problem:
Find all finite sets SS of positive integers with at least two elements, such that if m>nm > n are two elements of SS, then
n2mn \frac{n^{2}}{m-n}
is also an element of SS.

Solution

Solution:
Trying to apply number theoretical methods to deduce something from the fact that mnm-n divides n2n^{2} does not seem to lead anywhere. Instead, we will try to find the extreme values that the quotient n2/(mn)n^{2} /(m-n) can achieve. This will give us some interesting bounds on the elements of SS.

a. First, since SS contains at least two elements, we take l>sl > s to be the largest and smallest elements of SS. Since s2/(ls)s^{2} /(l-s) also belongs to SS we must have
s2lss2sl \frac{s^{2}}{l-s} \geq s \quad \Longrightarrow \quad 2s \geq l

b. Now, consider k<lk < l the second largest element of SS. The number k2/(lk)k^{2} /(l-k) belongs to SS. We claim that k2/(lk)lk^{2} /(l-k) \neq l, which implies
k2lkk2kl \frac{k^{2}}{l-k} \leq k \quad \Longrightarrow \quad 2k \leq l
We prove the previous claim in the following lemma.

Lemma 1
The equation k2/(lk)=lk^{2} /(l-k) = l has no positive integer solutions l>kl > k.

Proof. Assume such a solution exists, then it also solves
l2=k2+kl l^{2} = k^{2} + k l
Since the equation is homogeneous (of degree 2), we can assume that gcd(k,l)=1\operatorname{gcd}(k, l) = 1. Since we must have lk2l \mid k^{2}, we deduce that l=1l = 1. This is a contradiction since kk is a positive integer with k<lk < l.

Combining the two relations above, and using that sks \leq k, we get
l2s2kl l \leq 2s \leq 2k \leq l
Therefore k=sk = s and SS contains exactly two elements. Moreover, the inequalities above also imply l=2sl = 2s. So S={s,2s}S = \{s, 2s\} as desired.

Any such set satisfies the desired property because
s22ss=sS \frac{s^{2}}{2s - s} = s \in S

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.