AMC 12 Mock Exam 1 Problem 23

Start. A strictly increasing function on the positive integers satisfies $f(n)\ge n$. If $f(1)=1$ then $f(f(1))=1\ne3$; so $f(1)=a\ge2$ and $f(a)=3$. Since $f(a)\ge a$, $a\le3$. If $a=3$ then $f(3)=3$, but $f(3)>f(1)=3$, a contradiction. Hence $f(1)=2$ and $f(2)=3$.

Tripling. Since $f(f(f(n)))=3f(n)$, and also $f(f(f(n)))=f(3n)$ (apply $f$ to $f(f(n))=3n$), we get $f(3n)=3f(n)$. By induction on $k$: $f(3^k)=2\cdot3^k$ and $f(2\cdot3^k)=3^{k+1}$, because $f(3^{k+1})=3f(3^k)$ and $f(2\cdot3^{k+1})=3f(2\cdot3^k)$.

Filling in. The $3^k-1$ integers strictly between $3^k$ and $2\cdot3^k$ must map to strictly increasing integers strictly between $f(3^k)=2\cdot3^k$ and $f(2\cdot3^k)=3^{k+1}$; there are exactly $3^k-1$ integers there, so $f(m)=m+3^k$ for $3^k\le m\le2\cdot3^k$. Now if $2\cdot3^k\le n\le3^{k+1}$, write $n=m+3^k$ with $3^k\le m\le2\cdot3^k$, so $n=f(m)$ and $f(n)=f(f(m))=3m=3n-3^{k+1}$.

Answer. Since $2\cdot3^6=1458\le2026\le3^7=2187$, we get $f(2026)=3\cdot2026-3^7=6078-2187=\boxed{3891}$.

(The formulas $f(n)=n+3^k$ for $3^k\le n\le2\cdot3^k$ and $f(n)=3n-3^{k+1}$ for $2\cdot3^k\le n\le3^{k+1}$ do define a strictly increasing function with $f(f(n))=3n$, so such an $f$ exists and is unique.)