Maths Olympiad Prep

Library / /769 of 860

Algebra Difficulty 5.5 AIME, harder Find the answer

Let f:NNf: \mathbb{N} \rightarrow \mathbb{N} be a strictly increasing function such that f(1)=1f(1)=1 and f(2n)f(2n+1)=9f(n)2+3f(n)f(2n)f(2n+1)=9f(n)^{2}+3f(n) for all nNn \in \mathbb{N}. Compute f(137)f(137).

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Plugging in n=1n=1 gives f(2)f(3)=12f(2)f(3)=12, therefore (f(2),f(3))=(2,6)(f(2), f(3))=(2,6) or (3,4)(3,4). However, the former implies f(4)f(5)(6+1)(6+2)>42=922+32f(4)f(5) \geq (6+1)(6+2)>42=9 \cdot 2^{2}+3 \cdot 2 which is impossible; therefore f(2)=3f(2)=3 and f(3)=4f(3)=4. We now show by induction with step size 2 that f(2n)=3f(n)f(2n)=3f(n) and f(2n+1)=3f(n)+1f(2n+1)=3f(n)+1 for all nn; the base case n=1n=1 has already been proven. Assume the statement is true for n<2kn<2k. Applying the given and the inductive hypothesis, we have f(4k)f(4k+1)=(3f(2k))(3f(2k)+1)=(9f(k))(9f(k)+1)f(4k+2)f(4k+3)=(3f(2k+1))(3f(2k+1)+1)=(9f(k)+3)(9f(k)+4)\begin{aligned} f(4k)f(4k+1) & =(3f(2k))(3f(2k)+1)=(9f(k))(9f(k)+1) \\ f(4k+2)f(4k+3) & =(3f(2k+1))(3f(2k+1)+1)=(9f(k)+3)(9f(k)+4) \end{aligned} Let x=f(4k+1)x=f(4k+1). Since ff is strictly increasing, this implies xf(4k)f(4k+1)>9f(k)x \geq \sqrt{f(4k)f(4k+1)}>9f(k) and xf(4k+2)f(4k+3)1<9f(k)+3x \leq \sqrt{f(4k+2)f(4k+3)}-1<9f(k)+3. So x=9f(k)+1x=9f(k)+1 or x=9f(k)+2x=9f(k)+2. Since 9f(k)+29f(k)+2 does not divide 9f(k)(9f(k)+1)9f(k)(9f(k)+1), we must have f(4k+1)=x=9f(k)+1f(4k+1)=x=9f(k)+1 and f(4k)=9f(k)f(4k)=9f(k). A similar argument shows that f(4k+2)=9f(k)+3f(4k+2)=9f(k)+3 and f(4k+3)=9f(k)+4f(4k+3)=9f(k)+4, and this completes the inductive step. Now it is a straightforward induction to show that ff is the function that takes a number's binary digits and treats it as base 3. Since 137=100010012137=10001001_{2} in binary, f(137)=100010013=37+33+1=2215f(137)=10001001_{3}=3^{7}+3^{3}+1=2215.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.