4

Two functions $f,g:\mathbb{N} \to \mathbb{N}$ meet the following conditions.

For $A=\{f(n)|n \in \mathbb{N}\}, B=\{g(n)|n \in \mathbb{N}\}$,

  1. $A \cap B=\emptyset$
  2. $A \cup B= \mathbb{N}$
  3. $g(n)=f(f(n))+1 \quad \forall n \in \mathbb{N}$
  4. $f(n+1)>f(n)$, $g(n+1)>g(n)$.

Question: Find $f(240)$

This is a math contest problem but I have no idea.

I tried:

$f(1)=1$ or $g(1)=1$

i) If $f(1)=1: g(1)=f(f(1))+1=f(1)+1=2$

ii) If $g(1)=1: g(1)=f(f(1))+1=1, f(f(1))=0$

Therefore $f(1)=1, g(1)=2$

And then $f(2)=3$ or $g(2)=3$

i) If $f(2)=3: g(2)=f(f(2))+1=f(3)+1$

ii) If $g(2)=3: g(2)=f(f(2))+1=3, f(f(2))=2=g(1)$

Therefore $f(2)=3, g(2)=f(3)+1>4$

Therefore $f(3)=4$

...

Should I keep doing this?

Thanks for your help.

gt6989b
  • 54,422

1 Answers1

0

Hint: Prove that $f$ and $g$ are unique. Then, show that $f(n)=\lfloor \phi n\rfloor$ and $g(n)=f(n)+n=\left\lfloor \phi^2n\right\rfloor$, where $\phi:=\frac{1+\sqrt5}2$, satisfy the conditions.

Batominovski
  • 49,629
  • I'll also add that the motivation for selecting $\phi$ and $\phi^2$ is from Beatty's Theorem. See https://en.wikipedia.org/wiki/Beatty_sequence – rkm0959 Dec 04 '15 at 07:51