OMI 1987 - función

Question

Demostrar que no existe ninguna función $f: \mathbb{N} \to \mathbb{N}$ tal que $f(f(n))=n+1987, \ \forall n \in \mathbb{N}$.

Answer 1

Aquí es un enfoque alternativo. Es obvio que tal $f$ debe ser una inyección. Ahora, mira a los conjuntos de $\mathbb{N}$, $A = f(\mathbb{N})$ y $B = f(f(\mathbb{N})) = \{n + 1987 \ | \ n \in \mathbb{N}\}$.

Es fácil ver que $B \subconjunto de Un \subconjunto \mathbb{N}$, y también de la inyectividad de $f$ que $f$ induce un bijection entre los distintos conjuntos de $\mathbb{N} \setminus$ y $A \setminus B$. Por lo tanto, $\mathbb{N} \setminus B = (\mathbb{N} \setminus A) \cup (A \setminus B)$ debe contener un número par de elementos. Pero $|\mathbb{N} \setminus B| = 1987$, lo cual es una contradicción, y hemos terminado.

Answer 2

Aquí es una generalización.

La proposición. Para enteros positivos $k,$ l, la ecuación funcional $$ f^k(n)=n+l\qquad\text{para todo $n$} $$ no tiene soluciones de $f$ en función de $\Bbb Z\a\Bbb Z$, o en las funciones que $\Bbb N\a\Bbb$ N, a menos de $k$ divide a $l$.

En el caso de que $k\mid l$, uno no tiene soluciones, por ejemplo $n\mapsto n+l/k$.

Prueba. Suponga que $f$ satisface la ecuación funcional.

• Para todo $n$ una $f(n+l)=f^{k+1}(n)=f(n)+l$.
• Por lo tanto $f(n+l)-(n+l)=f(n)-n$ y $f(n)-n$ es constante cuando $n$ varía a través de cualquier clase de congruencia modulo $l$.
• La imagen debajo de $f$ de tal congruencia de la clase es, por tanto, otro de la congruencia de la clase, y $f$ da lugar a una función $\bar f:\Bbb Z/l\Bbb Z\a\Bbb Z/l\Bbb Z$.
• Desde $(\bar f)^k(\bar n)=\bar n$ para todo $\bar n\in\Bbb Z/l\Bbb Z$, esta función $\bar f$ es un bijection.
• Poner $S=\sum_{i=0}^{l-1}(f(i)-i)$; $l$ divide a $S$ desde $\sum_{i=0}^{l-1}f(i)\equiv\binom l2=\sum_{i=0}^{l-1}i\pmod l$, así que poner $s=S/l$.
• A partir de la ecuación funcional de $\sum_{i=0}^{l-1}\bigl(f^k(i)-i\bigr)=\sum_{i=0}^{l-1}l=l^2$.
• Por una suma telescópica, $f^k(i)-i=\sum_{j=0}^{k-1}\bigl(f^{j+1}(i)-f^j(i)\bigr)$.
• Desde cada $(\bar f)^j$ es un bijection, esto implica $$\sum_{i=0}^{l-1}\bigl(f^k(i)-i\bigr) =\sum_{j=0}^{k-1}\sum_{i=0}^{l-1}(f^{j+1}(i)-f^j(i)\bigr) =\sum_{j=0}^{k-1}S=kS=kls.$$
• Por lo tanto $l^2=kls$, por lo que $l=ks$ y $k$ divide a $l$.

Answer 3

Sólo una menor variación de la respuesta por user58512, para la diversión; como respuesta que funciona incluso si reemplazamos $\Bbb N$ en $\Bbb Z$. La ecuación $f(n+1987)=f(n)+1987$ en esa respuesta significa que $$f(n+1987)-(n+1987)=f(n)-n,$$ lo que demuestra que $f(n)-n$ sólo depende de la clase de $n$ modulo $1987$. También el mapa de $\bar f$ que $f$ induce en $\Bbb Z/1987\Bbb Z$ es surjective (la clase de $n$ es en la imagen de $\bar f^2$), de ahí bijective: $f(n)$ ejecuta a través de todas las clases de congruencia como $n$ se ejecuta sobre todas las clases de congruencia modulo $1987$.

Ahora vamos a $S$ es igual a la suma de $f(n)-n$ sobre todo el las clases de congruencia, obviamente, un número entero. Pero calculando la suma de $1987=f(f(n))-n=\bigl(f(f(n))-f(n)\bigl)+\bigr(f(n)-n\bigr)$ de entre todas las clases de congruencia, uno se pone en una mano el número impar $1987^2$, y por otro lado la cantidad de $2S$; contradicción.

Answer 4

Sugerencia de $\ $mod $\rm\,p\!:\ f(f(n)) = n+p\equiv n\:$ es una involución, por lo tanto $\rm\p\:$ impar $\Rightarrow$ que tiene un punto fijo de $\rm\:f(n)\equiv n,\:$ entonces $\rm\:f(n) = n\!+\!k p,\ k\in\Bbb Z.\:$ Ahora la órbita de $\rm\:f\:$ $\rm\n\,$ produce una contradicción

$$\rm\begin{array}{rlcl} &\rm n &\rm \&\rm \color{#C00}{n+kp} \\ \&\rm \color{#0A0}{n\!+\!p} &\rm \&\rm n\!+\!(k\!+\!1)p \\ \&\rm n\!+\!2p &\rm \&\rm n\!+\!(k\!+\!2)p\\ \&\rm n\!+\!3p &\rm \&\rm n\!+\!(k\!+\!3)p\\ &\rm\ \cdots &\rm &\rm \quad\cdots \\ \&\rm \color{#C00}{n\!+\!kp} &\rm \&\rm n\!+\!(k\!+\!k)p = \color{#0A0}{n\!+\!p}\ \Rightarrow\ 2k=1\ \Rightarrow\Leftarrow\: k\in\Bbb Z\\ \end{array}$$

Comentario de $\ $ Esta fue una sugerencia que he publicado hace muchos años en otro de matemáticas foro. Usted puede encontrar más posts aquí la explotación de la paridad y de involuciones mediante la búsqueda en la involución y Wilson (grupo de teóricos forma de Wilson del teorema).

Answer 5

Me contestó una menor variación de esta pregunta aquí: Funciones tal que $f(f(n))=n+2015$, conscientes de que era una de la OMI pregunta. Mi prueba podría ser un poco más cortos que los que se dan aquí:

Supongamos que dicha función existe. A continuación, defina la función $$g\colon \{1,\cdots,1987\}\\{1,\cdots,1987\},\qquad g(n)=f(n)\mod{1987}.$$ Luego de $g$ es una involución de ${1,\cdots,1987}$. Puesto que hay un número impar de elementos, de ello se sigue que $g$ tiene un punto fijo, por ejemplo, de $k$. Entonces $f(k)=k+1987j$ $j$, con lo cual $f(f(k))=k+1987\cdot 2j\no=k+1987$ contradicción.