A function $f: \Bbb{N^+} \rightarrow \Bbb{N^+}$, defined on the set of positive integers $\Bbb{N^+}$,…

Question

A function $f: \Bbb{N^+} \rightarrow \Bbb{N^+}$, defined on the set of positive integers $\Bbb{N^+}$, satisfies the following properties: $f(n)=f(n/2)$ if $n$ is even $f(n) = f(n+5)$ if $n$ is odd Let $R=\{ i \mid \exists{j} : f(j)=i \}$ be the set of distinct values that $f$ takes. The maximum possible size of $R$ is __________.

Accepted Answer

Correct answer: 2 — Answer: 2 Key idea: For any n, repeated use of the even rule reduces n to an odd number (its odd part). For an odd number o define T(o) as the odd part of o+5. The function value f at any n equals f of the odd number reached, and that odd number evolves under repeated application of T. If o>5 is odd then (o+5)/2 < o, so applying T strictly decreases the odd number until it becomes ≤5. Thus every odd number eventually reaches one of 1, 3, or 5. Compute T on these small odds: T(1)= odd part of 1+5 = 3, and T(3)= odd part of 3+5 = 1, so 1 and 3 form a 2-cycle. T(5)= odd part of 5+5 = 5, so 5 is a fixed point. Hence every n is mapped by f to either the value f(1)=f(3) or the value f(5). So the image R has at most two elements. This bound is achievable: define f so that f(n)=A for numbers whose T-trajectory reaches 1 or 3, and f(n)=B (with B ≠ A) for numbers whose trajectory reaches 5. This satisfies both rules and gives |R|=2.

A function \(f: \Bbb{N^+} \rightarrow \Bbb{N^+}\), defined on the set of…