Maths Olympiad Prep

Library / /16 of 31

Algebra Difficulty 8.3 Shortlist Prove it Baltic Way

Let T={1,3,6,10,15,}\mathbb{T} = \{1, 3, 6, 10, 15, \dots\} be the set of triangular numbers, i.e. numbers of the form Tn=n(n+1)2T_n = \frac{n(n+1)}{2}. Let ff be a function defined on the set of positive integers such that
1) f(n)f(n) is a positive integer for each nn;
2) f(uv)=f(u)f(v)f(uv) = f(u)f(v) for any pair (u,v)(u, v) of coprime numbers;
3) f(a+b+c)=f(a)+f(b)+f(c)f(a + b + c) = f(a) + f(b) + f(c) for a,b,cTa, b, c \in \mathbb{T}.
Prove that f(n)=nf(n) = n for all nn.

Solution

It is not difficult to find f(n)f(n) for small nn:
f(11)=f(1)f(1) therefore f(1)=1; f(1 \cdot 1) = f(1)f(1) \text{ therefore } f(1) = 1;
f(3)=f(1)+f(1)+f(1)=3; f(3) = f(1) + f(1) + f(1) = 3;
f(5)=f(1+1+3)=5; f(5) = f(1 + 1 + 3) = 5;
f(10)=f(1+3+6)=4+3f(2) and f(10)=f(25)=f(2)f(5)=5f(2) therefore f(2)=2. f(10) = f(1 + 3 + 6) = 4 + 3f(2) \text{ and } f(10) = f(2 \cdot 5) = f(2)f(5) = 5f(2) \text{ therefore } f(2) = 2.
Now we use induction. Suppose that f(n)=nf(n) = n for all n<Nn < N. Let us show that f(N)=Nf(N) = N. Since ff is multiplicative we may assume that N=prN = p^r for some prime pp. Consider several similar cases.

1) N=3rN = 3^r. Then
f(3T3r1)=3f(T3r1)=3f(3r1(3r1+1)2)=3f(3r1)f(3r1+12) f(3T_{3^{r-1}}) = 3f(T_{3^{r-1}}) = 3f\left(\frac{3^{r-1}(3^{r-1}+1)}{2}\right) = 3f(3^{r-1})f\left(\frac{3^{r-1}+1}{2}\right)
And from the other hand
f(3T3r1)=f(3r(3r1+1)2)=f(3r)f(3r1+12) f(3T_{3^{r-1}}) = f\left(\frac{3^r(3^{r-1}+1)}{2}\right) = f(3^r)f\left(\frac{3^{r-1}+1}{2}\right)
So we conclude that f(3r)=3rf(3^r) = 3^r since f(3r1)=3r1f(3^{r-1}) = 3^{r-1} by induction hypothesis.

and
f(Ts1+Ts1+Ts)=f(s(3s1)2)=f(s2)f(3s1)=s2f(pr). f(T_{s-1} + T_{s-1} + T_s) = f\left(\frac{s(3s-1)}{2}\right) = f\left(\frac{s}{2}\right)f(3s-1) = \frac{s}{2}f(p^r).
Hence f(pr)=prf(p^r) = p^r.

3) N=prN = p^r, where pp is an odd prime and pr=3s+1p^r = 3s + 1. Similarly we have
f(Ts1+Ts+Ts)=s(s1)2+s(s+1)2+s(s+1)2=s(3s+1)2=spr2=f(s(3s+1)2)=f(s2)f(3s+1)=s2f(pr). \begin{aligned} f(T_{s-1} + T_s + T_s) &= \frac{s(s-1)}{2} + \frac{s(s+1)}{2} + \frac{s(s+1)}{2} = \frac{s(3s+1)}{2} = \frac{sp^r}{2} \\ &= f\left(\frac{s(3s+1)}{2}\right) = f\left(\frac{s}{2}\right)f(3s+1) = \frac{s}{2}f(p^r). \end{aligned}
Hence f(pr)=prf(p^r) = p^r.

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.