Maths Olympiad Prep

Library / /32 of 42

Algebra Difficulty 6.3 National olympiad Prove it Ireland

Let N\mathbb{N} denote the strictly positive integers. A function f:NNf : \mathbb{N} \to \mathbb{N} has the following properties which hold for all nNn \in \mathbb{N}:
(a) f(n)<f(n+1)f(n) < f(n + 1);
(b) f(f(f(n)))=4nf(f(f(n))) = 4n.
Find f(2022)f(2022).

Solution

Solution 1. We first prove inductively that the following equations hold for all iNi \in \mathbb{N}:
f(14i1)=24i1,f(24i1)=34i1,f(34i1)=44i1=4i. \begin{aligned} f(1 \cdot 4^{i-1}) &= 2 \cdot 4^{i-1}, \\ f(2 \cdot 4^{i-1}) &= 3 \cdot 4^{i-1}, \\ f(3 \cdot 4^{i-1}) &= 4 \cdot 4^{i-1} = 4^i. \end{aligned}
The base case follows easily from the string of inequalities
1<f(1)<f(f(1))<f(f(f(1)))=4. 1 < f(1) < f(f(1)) < f(f(f(1))) = 4.
The inductive step then follows from the assumed identity for f(f(f(n)))f(f(f(n))).

Let A=14i1A = 1 \cdot 4^{i-1} for some iNi \in \mathbb{N}, let SS be the set of integers between AA and 2A2A inclusive, and let TT be the set of integers between 2A2A and 3A3A inclusive. Since ff maps the endpoints of SS to the endpoints of TT, the strictly increasing condition for ff implies that
* f(S)Tf(S) \subset T, and
* SS and f(S)f(S) have the same cardinality.
But SS and TT clearly have the same cardinality, so we must have f(S)=Tf(S) = T, and monotonicity now implies that f(A+k)=2A+kf(A + k) = 2A + k for all 1k4i11 \le k \le 4^{i-1}. In the same way, we see that f(2A+k)=3A+kf(2A+k) = 3A+k for all 1k4i11 \le k \le 4^{i-1}. Finally, f(3A+k)=f(f(f(A+k)))=4A+4kf(3A+k) = f(f(f(A+k))) = 4A+4k for all 1k4i11 \le k \le 4^{i-1}. We now have a formula for f(n)f(n) for all nn.
Writing 2022=1024+998=45+9982022 = 1024 + 998 = 4^5 + 998, we see that
f(2022)=21024+998=3046. f(2022) = 2 \cdot 1024 + 998 = 3046.

Solution 2. Applying ff to f(f(f(n)))=4nf(f(f(n))) = 4n and then using the same equation with nn replaced by f(n)f(n) we get
f(4n)=f(f(f(f(n))))=4f(n) f(4n) = f(f(f(f(n)))) = 4f(n)
for all nNn \in \mathbb{N}, and hence
f(4nn)=4f(4n1n)==4nf(n). f(4^n n) = 4f(4^{n-1} n) = \dots = 4^n f(n).
We know f(1)=2f(1) = 2, f(2)=3f(2) = 3, f(3)=4f(3) = 4 since the function is increasing with
1<f(1)<f(f(1))<f(f(f(1)))=4. 1 < f(1) < f(f(1)) < f(f(f(1))) = 4.
Hence f(4i)=4if(1)=24if(4^i) = 4^i f(1) = 2 \cdot 4^i and f(24i)=4if(2)=34if(2 \cdot 4^i) = 4^i f(2) = 3 \cdot 4^i so
4ix=4i24i1[f(x+1)f(x)]=f(24i)f(4i)=4i. 4^i \le \sum_{x=4^i}^{2 \cdot 4^i - 1} [f(x+1) - f(x)] = f(2 \cdot 4^i) - f(4^i) = 4^i.
Thus f(x+1)f(x)=1f(x+1) - f(x) = 1 for each xx with 4ix24i14^i \le x \le 2 \cdot 4^i - 1. It follows that f(4i+k)=f(4i)+k=24i+kf(4^i + k) = f(4^i) + k = 2 \cdot 4^i + k for 1k4i1 \le k \le 4^i and hence f(2022)=21024+998=3046f(2022) = 2 \cdot 1024 + 998 = 3046 as above.

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.