Maths Olympiad Prep

Library / /17 of 18

Algebra Difficulty 8.0 National olympiad, round 2 Prove it Argentina

Find all functions f:NRf: \mathbb{N} \to \mathbb{R} that satisfy the equation
f(x+y)=f(x)+f(y) f(x + y) = f(x) + f(y)
for all x,yNx, y \in \mathbb{N} such that 106106<xy<106+10610^6 - 10^{-6} < \frac{x}{y} < 10^6 + 10^{-6}.

Solution

All functions of the form f(x)=cxf(x) = cx with cRc \in \mathbb{R} are solutions; they are the only ones. More generally let b>a>0b > a > 0, and let the open interval Δ=(a,b)\Delta = (a, b) contain an integer (in our case a=106106a = 10^6 - 10^{-6}, b=106+106b = 10^6 + 10^{-6}). Consider any function f:NRf: \mathbb{N} \to \mathbb{R} such that f(x+y)=f(x)+f(y)f(x + y) = f(x) + f(y) holds whenever xyΔ\frac{x}{y} \in \Delta. We prove that f(n)=cnf(n) = cn for all nNn \in \mathbb{N} with a real constant cc.

To begin with let us show that f(n+1)f(n)=f(n)f(n1)f(n+1) - f(n) = f(n) - f(n-1) for all sufficiently large nn. The reason is that for each sufficiently large nNn \in \mathbb{N} there is a zNz \in \mathbb{N} such that
f(n+1)f(n)=f(z+1)f(z)=f(n)f(n1). f(n + 1) - f(n) = f(z + 1) - f(z) = f(n) - f(n - 1).
To ensure the first equality it is enough to take a zz so that zn+1Δ\frac{z}{n+1} \in \Delta and z+1nΔ\frac{z+1}{n} \in \Delta. Then by hypothesis f(x+y)=f(x)+f(y)f(x + y) = f(x) + f(y) will hold with x=zx = z, y=n+1y = n + 1 and also with x=z+1x = z + 1, y=ny = n. Hence f(z)+f(n+1)=f(n+z+1)=f(z+1)+f(n)f(z) + f(n+1) = f(n+z+1) = f(z+1) + f(n), as desired. Likewise the second equality will hold provided that znΔ\frac{z}{n} \in \Delta and z+1n1Δ\frac{z+1}{n-1} \in \Delta. Since zn+1<zn<z+1n<z+1n1\frac{z}{n+1} < \frac{z}{n} < \frac{z+1}{n} < \frac{z+1}{n-1}, it suffices to find an integer zz so that a<zn+1a < \frac{z}{n+1} and z+1n1<b\frac{z+1}{n-1} < b, i.e. a(n+1)<z<b(n1)1a(n + 1) < z < b(n - 1) - 1. Such an integer does exist for nn large enough. Indeed b(n1)1b(n - 1) - 1 and a(n+1)a(n + 1) differ by (ba)n(a+b+1)(b - a)n - (a + b + 1) which is greater than 1 for n>a+b+2ban > \frac{a+b+2}{b-a}.

In summary there exists a kNk \in \mathbb{N} such that f(n+1)f(n)f(n+1) - f(n) has the same value for all nkn \ge k. Then by standard induction
()f(n)=(nk)[f(k+1)f(k)]+f(k)for all nk. (*) \quad f(n) = (n-k)[f(k+1)-f(k)] + f(k) \quad \text{for all } n \ge k.
There are x,yNx, y \in \mathbb{N} such that x,ykx, y \ge k and xyΔ\frac{x}{y} \in \Delta. For instance choose a rational rsΔ\frac{r}{s} \in \Delta (r,sNr, s \in \mathbb{N}) and set x=rk,y=skx = rk, y = sk. Take one such pair x,yx, y and compute f(x),f(y),f(x+y)f(x), f(y), f(x+y) by the formula ()(*); this can be done because x,y,x+ykx, y, x+y \ge k. Replace the obtained values in f(x+y)=f(x)+f(y)f(x+y) = f(x)+f(y), which holds because xyΔ\frac{x}{y} \in \Delta. Simplification leads to kf(k+1)=(k+1)f(k)kf(k+1) = (k+1)f(k). Hence f(k)k=f(k+1)k+1=cR\frac{f(k)}{k} = \frac{f(k+1)}{k+1} = c \in \mathbb{R}; equivalently f(k)=ckf(k) = ck and f(k+1)=c(k+1)f(k+1) = c(k+1). Then ()(*) takes the form f(n)=cnf(n) = cn for all nkn \ge k. It remains to show that f(n)=cnf(n) = cn for all nNn \in \mathbb{N}.

Only finitely many nNn \in \mathbb{N} may possibly disobey f(n)=cnf(n) = cn. Suppose that such values exist, and let qq be the greatest one of them. Choose an integer wΔw \in \Delta and set x=wq,y=qx = wq, y = q. Then x/wΔx/w \in \Delta, hence f((w+1)q)=f(wq)+f(q)f((w+1)q) = f(wq) + f(q). If w>1w > 1 then (w+1)q>wq>q(w+1)q > wq > q, so by the choice of qq we have f((w+1)q)=c(w+1)qf((w+1)q) = c(w+1)q, f(wq)=cwqf(wq) = cwq. However then f(q)=c(w+1)qcwq=cqf(q) = c(w+1)q - cwq = cq, contrary to the assumption that qq violates f(n)=cnf(n) = cn. And if w=1w = 1 then (w+1)q=2q>q(w+1)q = 2q > q, so f(2q)=2cqf(2q) = 2cq. On the other hand f((w+1)q)=f(wq)+f(q)f((w+1)q) = f(wq) + f(q) takes the form f(2q)=2f(q)f(2q) = 2f(q) which leads to the impossible f(q)=cqf(q) = cq again. This completes the proof.

*Remark.* The main assumption is f(x+y)=f(x)+f(y)f(x + y) = f(x) + f(y) whenever xyΔ\frac{x}{y} \in \Delta, where Δ\Delta is an arbitrary open interval with positive endpoints. It ensures f(n)=cnf(n) = cn for all sufficiently large values of nn. However the additional assumption that Δ\Delta contains an integer is essential to infer that f(n)=cnf(n) = cn for all nNn \in \mathbb{N}. Consider for instance the function f:NRf: \mathbb{N} \to \mathbb{R} defined by f(n)=nf(n) = n for n5n \ge 5 and f(n)=2010f(n) = 2010 for n{1,2,3,4}n \in \{1, 2, 3, 4\} (in fact f(1),f(2),f(3),f(4)f(1), f(2), f(3), f(4) can be arbitrary). The interval Δ=(3/2,5/3)\Delta = (3/2, 5/3) does not contain fractions with denominators 1,2,3,41, 2, 3, 4. So xyΔ\frac{x}{y} \in \Delta implies xy5x \ge y \ge 5; the equation f(x+y)=f(x)+f(y)f(x + y) = f(x) + f(y) is satisfied for such values. Thus ff is a function that satisfies the main assumption and f(n)=nf(n) = n for n5n \ge 5 but not for all nn.

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.