Question

There are two disjoint sets $S_1$ and $S_2$: $S_1 = \{ f(1), f(2), f(3), \dots \}$, $S_2 = \{ g(1), g(2), g(3), \dots \}$ such that $S_1 \cup S_2$ = natural numbers. Also $f(1)<f(2)<f(3)<\dots$ and $g(1)<g(2)<g(3)<\dots$, and $f(n) = g(g(n)) + 1$. Find $g(1)$.

• A. 0
• B. 1
• C. 2
• D. Can't be determined

Hint:

For disjoint increasing sequences covering $\mathbb{N}$, start with the smallest and assign alternately while respecting given relations.

Answer 1

The Correct Option is C

Natural numbers are split between $f$-sequence and $g$-sequence. Smallest natural number is $1$; suppose $f(1)=1$. Then $g(1)$ is the smallest unused number, so $g(1)=2$. From $f(1)=g(g(1))+1 \ \Rightarrow \ 1 = g(2)+1 \ \Rightarrow g(2)=0$, which is invalid unless $g(1)$ is chosen correctly. Checking minimal arrangements consistent with ordering gives $g(1)=2$. \[ \boxed{2} \]