2

Function $f:\mathbb N\to\mathbb N$ is defined.If for any natural number $f(n+1)>f(n)$ and $f(f(f(n)))=4n$ , $f(2023)=?$

I attempted to solve it as shown below:

$f(f(f(1)))=4$ and let's say $f(f(1))=x$ then $f(x)=4$ and as $f:\mathbb N\to\mathbb N$ it must be $x\leq4$.Then I tried out these $4$ possible ways and concluded that only $x=3$ works.Because if so $f(3)=4$ , $f(f(1))=3$. From these I found $f(1)=2$ , $f(2)=3$.

And after that I wanted to find other terms but it doesn't give the answer.Is my attempt wrong? If so how to solve this?

NOTE: This question is adapted from a competition that took place in january $2023$.

Anar
  • 183
  • 8
    Please edit to include the source of this problem. Questions involving the current year are frequently used in competitions. – lulu Apr 28 '23 at 15:58
  • 1
    Just wanted to clarify the above comment : Since you mention $f(2023)$, and mention no source, many people may suspect it is from an ongoing competition. (You will find the current year being used as a number in olympiads etc., where the number itself isn't important). So, it's better to add the source of the problem, with a link if possible. Otherewise, this question is unlikely to recieve an answer. – D S Apr 28 '23 at 17:10
  • It doesn't have a link.Even if it did it is not in english.I don't know what to do in this situation.But I can say that it is not an ongoing competition.And don't most of questions in this site have a certain source? – Anar Apr 28 '23 at 17:29
  • What is the answer? $8091$? – Bob Dobbs Apr 29 '23 at 19:40
  • Sorry. I mean $3211$. – Bob Dobbs Apr 29 '23 at 19:52
  • 1
    No @Bob Dobbs . – Anar Apr 29 '23 at 20:18
  • Is S.C.'s answer $3047$ correct? – Bob Dobbs Apr 29 '23 at 20:45
  • Yes, It is correct. – Anar Apr 29 '23 at 20:47

1 Answers1

3

As you argued, $f(1) = 2$, $f(2) = 3$ and $f(3) = 4$. Applying $f$ to each side of the equation $f(f(f(n))) = 4n$, we get $f(f(f(f(n)))) = f(4n)$. On the other hand, setting $n$ to $f(n)$ in $f(f(f(n))) = 4n$, we get $f(f(f(f(n)))) = 4f(n)$ Thus, $f(4n) = f(f(f(f(n)))) = 4f(n)$. By induction, for any integer $a$ and non-negative integer $k$, $f(4^k a) = 4^k f(a)$.

If $a$ is $1$ or $2$, then $f(a + 1) = f(a) + 1$. So

$$ \begin{equation} \begin{split} f(4^k a + 4^k) & = f(4^k (a + 1)) \\ & = 4^k f(a + 1) \\ & = 4^k (f(a) + 1) \\\ & = 4^k f(a) + 4^k \\ & = f(4^k a) + 4^k \end{split} \end{equation} $$

Since $f$ is strictly increasing and integer-valued, this implies that the $4^k + 1$ values $f(4^k a + b)$ for $0 \leq b \leq 4^k$ are precisely the $4^k + 1$ values $f(4^k a) + b$ for $0 \leq b \leq 4^k$. That is, $f(4^k a + b) = f(4^k a) + b = 4^k f(a) + b$.

This is already enough to find $f(2023)$, since $2023 = 4^5 + 999$. $f(2023) = 4^5 f(1) + 999 = 3047$.

However, this isn't enough to find $f(n)$ for all $n$, since it excludes numbers that start with $3$ in base $4$, i.e. numbers of the form $3 * 4^k + b$ with $0 \leq b < 4^k$.

For these numbers, we note that $3 * 4^k + b = f(2 * 4^k + b) = f(f(4^k + b))$ by the above. Thus, $f(3 * 4^k + b) = f(f(f(4^k + b))) = 4(4^k + b)$.

So, for example, $f(13) = f(3 * 4^1 + 1) = 4(4^1 + 1) = 20$.

S.C.
  • 2,630