El tamaño máximo posible de $R$ ¿_____?

Question

Una función $f : N^+ N^+$ definido en el conjunto de enteros positivos $N^+$ cumple las siguientes propiedades:

$f(n) = f(n/2)$ si $n$ es incluso

$f(n) = f(n+5)$ si $n$ es impar

Sea $R = \{i| j : f(j) = i\}$ sea el conjunto de valores distintos que $f$ toma. El tamaño máximo posible de $R$ ¿_____?

---

Mi intento:

Supongamos $: f(1) = x.$ Entonces,

$f(2) = f(2/2) = f(1) = x$

$f(3) = f(3+5) = f(8) = f(8/2) = f(4/2) = f(2/1) = f(1) = x$

Del mismo modo, $f(4) = x$

$f(5) = f(5+5) = f(10/2) = f(5) = y$

Por lo tanto, tendrá dos valores. Todos los múltiplos de $5$ tendrá valor $y$ y otros tendrán valor $x$ . Tendrá $2$ valores diferentes.

¿Puede explicarlo de manera formal, por favor?

Answer 1

Supongamos que ha calculado $f$ de $1$ a $5$ como tú. Ahora supongamos que conoce el valor de $f(i)$ con $1 \leq i \leq n$ y sólo tienes $2$ valores. ¿Puede calcular $f(n+1)$ ? Por supuesto: si es par es igual a $f((n+1)/2)$ que es $x$ o $y$ , si es impar es $f((n+1)-5)$ que es $x$ o $y$ (tenga en cuenta que $n+1-5=n-4>0$ por lo que es un buen valor para $f$ ).

Lo que queda por demostrar ahora es que tal función existe: mantener la función que es $1$ quand $n$ no es divisible por $5$ y $2$ quand $n$ es divisible por $5$ y comprobar que satisface las dos peticiones. Concretamente, observe que dividiendo por $2$ o restando $5$ no cambia el hecho de ser o no divisible por $5$ para que pueda reducir cada $n$ a un número comprendido entre $1$ y 5 sin cambiar su divisibilidad por $5$ .