Si $f:\mathbb N\to\mathbb N$ tal que $f\big(f(x)\big)=3x$ , entonces encuentra $f(2013)$ .

Question

Si $f:\mathbb N\to\mathbb N$ tal que $f\big(f(x)\big)=3x$ entonces cuál es el valor de $f(2013)$ ?

Answer 1

Podemos definir dos funciones $g$ y $h$ de esta manera: $$g(0)=h(0)=0$$ $$g(3k)=3g(k)$$ $$g(3k+1)=3k+2$$ $$g(3k+2)=9k+3$$ $$h(3k)=3h(k)$$ $$h(3k+1)=9k+6$$ $$h(3k+2)=3k+1$$

Puede comprobar fácilmente que $g$ y $h$ satisfacen la condición del problema, y que $g(2013)=6030$ y que $h(2013)=2010$ , por lo que no podemos adivinar el valor de $f(2013)$ con esa única condición.

Esta idea se puede generalizar: Sea $A$ sea el conjunto de números naturales que no son múltiplos de $3$ . Sea $\{B,C\}$ cualquier partición de $A$ (es decir, $B\cup C=A$ y $B\cap C=\emptyset)$ con la única condición de que ambos conjuntos sean infinitos. Tomemos por ejemplo: cuadrados y no cuadrados, primos y no primos, etc. Dado que $B$ y $C$ son infinitos y contables existe una biyección $\sigma$ de $B$ a $C$ . De hecho, hay infinitas biyecciones de este tipo.

Ahora define: $f(0)=0$ , $f(3k)=3f(k)$ , $f(k)=\sigma(k)$ si $k\in B$ y $f(k)=3\sigma^{-1}(k)$ si $k\in C$ . Demostremos que $f(f(x))=3x$ para todos $x$ por inducción. Esto se cumple claramente para $x=0$ .

Entonces, para cada $x>0$ tenemos tres posibilidades:

• si $x$ es un múltiplo de $3$ entonces $x=3k$ Así que $f(f(x))=f(f(3k))=f(3f(k))=3f(f(k))=3\cdot3k=3x$ por la hipótesis de inducción. Nótese que $k<x$ .
• si $x\in B$ entonces $f(f(x))=f(\sigma(x))=3\sigma^{-1}(\sigma(x))=3x$
• si $x\in C$ entonces $f(f(x))=f(3\sigma^{-1}(x))=3f(\sigma^{-1}(x))=3\sigma(\sigma^{-1}(x))=3x$

c.q.d.

Está claro que el valor concreto de $f(2013)$ depende fuertemente de la partición elegida y de la biyección elegida para esa partición.

De hecho, sospecho que $f(2013)$ puede ser cualquier múltiplo de $3$ .

Answer 2

En lo que sigue, construiré una función $f$ (¡que no es creciente!) que satisface $f(f(x)) = 3x$ para $x \in \mathbb N$ y $f(x) = 4026$ .

¿Qué tal si dividimos la multiplicación por 3 en una multiplicación por 2 y otra por 1,5? Para ello, tendríamos que detectar si ya hemos multiplicado nuestro argumento por 2 y luego multiplicarlo por 1,5.

Entonces, ¿cómo podemos detectar eso?

Si nos dan un número impar, está claro que tenemos que multiplicar por 2 porque no lo hemos hecho ya. Si tomamos la función simple

$$ f_1(x) = \begin{cases} 2*x & \text{if $x$ is not divisible by 2}\\ x + x/2 & \text{otherwise} \end{cases} $$ Entonces esta función muestra el siguiente comportamiento (salida de un script):

3 * 1 = 3 == 3 = f(2) = f(f(1))
3 * 2 = 6 == 6 = f(3) = f(f(2))
3 * 3 = 9 == 9 = f(6) = f(f(3))
3 * 4 = 12 != 9 = f(6) = f(f(4))
3 * 5 = 15 == 15 = f(10) = f(f(5))
3 * 6 = 18 == 18 = f(9) = f(f(6))
3 * 7 = 21 == 21 = f(14) = f(f(7))
3 * 8 = 24 != 18 = f(12) = f(f(8))

En otras palabras, tiene la propiedad $f_1(f_1(x)) = 3x$ si $x$ no es divisible por 4. ¿Cómo podemos solucionarlo? Esta función hace un mejor trabajo:

$$ f_2(x) = \begin{cases} 2*x & \text{if $x$ is not divisible by 2}\\ x + x/2 & \text{if $x$ is not divisible by 4}\\ 2*x & \text{if $x$ is not divisible by 8}\\ x + x/2 & \text{otherwise} \end{cases} $$ donde la primera condición de coincidencia determina el valor. Esta función muestra el siguiente comportamiento:

3 * 1 = 3 == 3 = f(2) = f(f(1))
3 * 2 = 6 == 6 = f(3) = f(f(2))
3 * 3 = 9 == 9 = f(6) = f(f(3))
3 * 4 = 12 == 12 = f(8) = f(f(4))
3 * 5 = 15 == 15 = f(10) = f(f(5))
3 * 6 = 18 == 18 = f(9) = f(f(6))
3 * 7 = 21 == 21 = f(14) = f(f(7))
3 * 8 = 24 == 24 = f(12) = f(f(8))
3 * 9 = 27 == 27 = f(18) = f(f(9))
3 * 10 = 30 == 30 = f(15) = f(f(10))
3 * 11 = 33 == 33 = f(22) = f(f(11))
3 * 12 = 36 == 36 = f(24) = f(f(12))
3 * 13 = 39 == 39 = f(26) = f(f(13))
3 * 14 = 42 == 42 = f(21) = f(f(14))
3 * 15 = 45 == 45 = f(30) = f(f(15))
3 * 16 = 48 != 36 = f(24) = f(f(16))

En otras palabras, maneja cualquier $x$ que no es divisible por 16 correctamente. Ahora es sencillo construir la función $f$ .

Este es un código lisp común que implementa $f$ y genera la salida anterior.

(labels
    ((fn (x)
       (flet ((indivisible-by (x y)
                (/= 0 (mod x y))))
         (do ((k 1 (1+ k)))
             ((indivisible-by x (expt 2 k))
              (if (oddp k)
                  (* 2 x)
                  (+ x (/ x 2)))))))
     (fn-bits (x) ; Same function, more intuitive
       (flet ((count-trailing-zeroes (x)
                (do ((k 0 (1+ k)))
                    ((logbitp k x) k))))
         (if (oddp (count-trailing-zeroes x))
             (+ x (/ x 2))
             (* 2 x))))
     (g (x)
       (cond
         ((= 0 x) 0)
         ((= 0 (mod x 3)) (* 3 (g (/ x 3))))
         ((= 1 (mod x 3)) (+ x 1))
         ((= 2 (mod x 3)) (- (* 3 x) 3))))
     (h (x)
       (cond
         ((= 0 x) 0)
         ((= 0 (mod x 3)) (* 3 (h (/ x 3))))
         ((= 1 (mod x 3)) (+ (* 3 x) 3))
         ((= 2 (mod x 3)) (- x 1))))
     (f (x) (fn-bits x))) ;; Choose a function to test here
  (format t "==========================================~%")
  (format t "We have f(2013) = ~a.~%~%" (f 2013))
  (loop for x from 1 to 16 do
    (let* ((fx (f x))
           (ffx (f fx))
           (3x (* 3 x))
           (proper (= 3x ffx)))
      (format t "3 * ~a = ~a ~a ~a = f(~a) = f(f(~a))~%"
              x 3x (if proper "==" "!=") ffx fx x))))

Las funciones $g$ y $h$ se han tomado de la respuesta de @user2425 para comparar.

Actualización : ¿Por qué la función $f$ ¿funciona como se espera? Considere la entrada $x$ en representación binaria y contar el número de ceros finales. Si llamo a este número $N$ , lo que $f$ hace es multiplicar $x$ por 2 si $N$ es par y por 1,5 si $N$ es impar.

Si $N$ es impar, entonces $x$ se multiplica por 2 y después, $N$ es par. Si $N(x)$ es par, entonces $N(x/2)$ es impar y también lo es $N(x+x/2)$ . En consecuencia, $N$ es impar después de una multiplicación por $1.5.$

Answer 3

Probablemente podemos suponer que $f$ es una función estrictamente creciente.

Sabemos que $f(f(1))=3$ Entonces, ¿qué es? $f(1)$ ? No puede ser $3$ y no puede ser $1$ , por lo que debemos tener $f(1)=2$ y $f(2)=3$ . También necesitamos $6=f(f(2))=f(3)$ Así que $f(3)=6$ . Y así sucesivamente. $9=f(f(3))=f(6)$ , $18=f(9)$ , $54=f(18)$ ...

Desde $f(3)=6$ y $f(6)=9$ podemos derivar que $f(4)=7$ y $f(5)=8$ .

A partir de ahí $f(7)=12$ y $f(8)=15$ .

A partir de ahí $f(12)=21$ y sabemos $18=f(9)<f(10)<f(11)<f(12)=21$ por lo que sabemos que $f(10)=19$ y $f(11)=20$ .

Es probable que puedas ir subiendo.

También sabemos que $2013=3\cdot11\cdot61$ por lo que necesitamos $2013=f(f(11\cdot61))$ y así $f(2013)=3f(11\cdot61)$

Pero espero que haya una solución más fácil :)