Maths Olympiad Prep

Library / /1 of 4

Algebra Difficulty 5.9 AIME, harder Prove it Silk Road Mathematics Competition

A set SS of real numbers is such that 1+1xS1 + \frac{1}{x} \in S for each xSx \in S. Is it possible that SS contains exactly 2025 elements?

Solution

Answer. The answer is no.

Let f(x)=1+1xf(x) = 1 + \frac{1}{x} and f(n)(x)=f(f(f(x)))f^{(n)}(x) = f(f(\dots f(x))) (where ff is applied nn times). For each xSx \in S the set SS contains all numbers of the form f(n)(x)f^{(n)}(x). If SS is finite, then f(k)(x)=f()(x)f^{(k)}(x) = f^{(\ell)}(x) for some k>k > \ell. Since f(a)=f(b)f(a) = f(b) implies a=ba = b, f(k)(x)=xf^{(k-\ell)}(x) = x. Thus each xSx \in S is a root of equation f(n)(x)=xf^{(n)}(x) = x for some positive integer nn.

The functions f(n)(x)f^{(n)}(x) obviously are of the form px+qrx+s\frac{px+q}{rx+s} with some p,q,r,sp, q, r, s (it is immediate for n=1n=1, and ff transforms every such function into a function of this form). Therefore, the equation f(n)(x)=px+qrx+s=xf^{(n)}(x) = \frac{px+q}{rx+s} = x is reduced to an equation of the form rx2+(sp)xq=0rx^2 + (s-p)x - q = 0 which is an equation of degree at most 2. This equation is not identical (since, for example, f(2)=12f(-2) = \frac{1}{2} and therefore f(n)(2)f^{(n)}(-2) is positive for all positive integers nn), hence it cannot have more than two real roots. However, the roots 1+52\frac{1+\sqrt{5}}{2} and 152\frac{1-\sqrt{5}}{2} of f(x)=xf(x) = x are also roots of f(n)(x)=xf^{(n)}(x) = x and therefore its only roots.

We see now that if SS is finite, it can contain at most two elements.

Second solution. There is an alternative way to prove that for every xx except φ=1+52\varphi = \frac{1+\sqrt{5}}{2} and φˉ=152\bar{\varphi} = \frac{1-\sqrt{5}}{2}, f(n)(x)f^{(n)}(x) and xx would not coincide.

If x<1x < -1, then f(x)>0f(x) > 0 and therefore all f(n)(x)f^{(n)}(x) are positive.

If 0<x10 < x \le 1, then f(x)>1f(x) > 1, and all of f(n)(x)f^{(n)}(x) are greater than 1.

If x>1x > 1, then f(x)φ=1+1x11φ=xφxφ<xφ|f(x) - \varphi| = |1 + \frac{1}{x} - 1 - \frac{1}{\varphi}| = \frac{|x-\varphi|}{x\varphi} < |x - \varphi|, that is, the distance from f(n)(x)f^{(n)}(x) to φ\varphi decreases as nn increases.

Finally, if 1<x<0-1 < x < 0, while the terms of the sequence x,f(x),f(f(x)),x, f(x), f(f(x)), \dots remain in the interval (1,0)(-1, 0), their distances between each term of the sequence and φˉ\bar{\varphi} would increase (indeed, f(t)φˉ=1+1t11φˉ=tφˉtφˉ>tφˉ|f(t) - \bar{\varphi}| = |1 + \frac{1}{t} - 1 - \frac{1}{\bar{\varphi}}| = \frac{|t-\bar{\varphi}|}{t\bar{\varphi}} > |t - \bar{\varphi}|), and when a term appears outside this interval, all the proceeding terms would also be outside of this interval.

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 and solution reproduced as published; topic and difficulty added by this site.