Permítanme indicar una secuencia de distintos números naturales por $x_n$, cuyos términos se determina de la siguiente manera: $x_1$ $1$ $x_2$ es el más pequeño distinto número natural $n$ tal que $x_1+x_2$ es divisible por $2$,$3$. Del mismo modo $x_n$ es el más pequeño distinto número natural tal que $x_1+...+x_n$ es divisible por $n$. Así $x_1=1$, $x_2=3$, $x_3=2$.
Ahora el problema es demostrar que (i) $x_n$ es surjective (ii) $x_{(x_n)}$$n$, por ejemplo, $x_2=3$ $x_3=2$
Como otros carteles se han dado cuenta, esto está estrechamente relacionado con la proporción áurea $\varphi = \frac{1+\sqrt{5}}{2}$.
@ Ross Millikan su respuesta es un gran lugar para comenzar.
$\frac{1}{\varphi}+\frac{1}{\varphi ^2}=1$, por lo que podemos partición de los números naturales mayores que 1 en los números de los formularios $\lceil {n \varphi} \rceil, \lceil {n \varphi ^2} \rceil$. (Se añade 1 a la beatty secuencias)
Definir $a_1=1, a_{\lceil {n \varphi} \rceil}=\lceil {n \varphi ^2} \rceil, a_{\lceil {n \varphi ^2} \rceil}=\lceil {n \varphi} \rceil$. Claramente $a_{a_n}=n$.
Que es donde la siguiente observación crucial que $\sum\limits_{i=1}^{n}{a_i}=n \lceil{\frac{n}{\varphi}} \rceil$.
Procedemos por inducción sobre $n$ que $\sum\limits_{i=1}^{n}{a_i}=n \lceil{\frac{n}{\varphi}} \rceil$ y $a_n$ es el entero más pequeño que la satisfacción de las divisiblity relación $n \mid \sum\limits_{i=1}^{n}{a_i}$.
Al$n=1$,$1=1 \lceil{\frac{1}{\varphi}} \rceil$, lo cual es cierto. Al$n=2$,$1+3=2 \lceil{\frac{2}{\varphi}} \rceil$, lo cual es cierto.
Supongamos que tiene de $n=k \geq 2$. A continuación,$\sum\limits_{i=1}^{k}{a_i}=k \lceil{\frac{k}{\varphi}} \rceil$. Considere la posibilidad de 2 casos:
Caso 1: $k+1=\lceil{m \varphi} \rceil$ algunos $m \in \mathbb{Z}^+$. A continuación,$a_{k+1}=\lceil{m \varphi ^2} \rceil=m+\lceil{m \varphi} \rceil=m+k+1$.
Ahora$k+1=m \varphi +1- \{m \varphi \}$$m-1<m-\frac{\{m \varphi \}}{\varphi}=\frac{k}{\varphi}<m<m+\frac{1-\{m \varphi \}}{\varphi}=\frac{k+1}{\varphi}<m+1$. Así $\lceil{\frac{k}{\varphi}} \rceil=m, \lceil{\frac{k+1}{\varphi}} \rceil=m+1$.
$\sum\limits_{i=1}^{k+1}{a_i}=k \lceil{\frac{k}{\varphi}} \rceil+a_{k+1}=km+(m+k+1)=(k+1)(m+1)=(k+1) \lceil{\frac{k+1}{\varphi}} \rceil$.
Minimality: tenga en cuenta que $a_{k+1}=m+k+1<2(k+1)$, y porque tenemos una partición, $a_{k+1} \not =a_i \, \forall i$, por lo que es suficiente para mostrar que $a_i=m$ algunos $i$$1 \leq i \leq k$, o lo que es equivalente, $a_m \leq k$. Si $m=\lceil{b \varphi ^2 } \rceil$ algunos $b \in \mathbb{Z}^+$, que se hacen desde $a_m<m \leq k$. De lo contrario, $m=\lceil{b \varphi} \rceil$ algunos $b \in \mathbb{Z}^+$, lo $a_m=\lceil{b \varphi ^2 } \rceil \leq \lceil{\lceil b \varphi \rceil \varphi } \rceil=\lceil{m \varphi } \rceil=k+1$. Desde $k+1=\lceil{m \varphi} \rceil \not =\lceil{b \varphi ^2 } \rceil = a_m$ (Partición), ahora tenemos la deseada desigualdad $a_m \leq k$.
Caso 2: $k+1=\lceil{m \varphi ^2} \rceil=m+\lceil{m \varphi} \rceil$ algunos $m \in \mathbb{Z}^+$. A continuación,$a_{k+1}=\lceil{m \varphi} \rceil=k+1-m$.
Ahora $k+1=m \varphi ^2 +1-\{m \varphi ^2 \}$.
Como tenemos una partición, $k+1$ no puede ser escrita en la forma $\lceil{i \varphi} \rceil$. Por lo tanto $\exists c \in \mathbb{Z}^+$ tal que $\lceil{c \varphi} \rceil<k+1<\lceil{(c+1) \varphi} \rceil$. (Desde $k>1$.)
Esto le da a $\lceil{c \varphi} \rceil=k, \lceil{(c+1) \varphi} \rceil=k+2$.
Por lo tanto: $k=c \varphi +1-\{c \varphi \}, k+2=(c+1) \varphi +1-\{(c+1) \varphi \}$, por lo que \begin{align} c<c+\frac{1-\{c \varphi \}}{\varphi}=\frac{k}{\varphi}=m \varphi -\frac{\{m \varphi ^2 \}}{\varphi}<m \varphi & <m \varphi +\frac{1-\{m \varphi ^2 \}}{\varphi} \\ & =\frac{k+1}{\varphi} \\ & =c+1-\frac{\{(c+1) \varphi \}}{\varphi} \\ & <c+1 \end{align}
Llegamos $\lceil \frac{k}{\varphi} \rceil =\lceil m \varphi \rceil =\lceil \frac{k+1}{\varphi} \rceil =c+1$, lo $k+1=m+c+1, a_{k+1}=c+1$.
$\sum\limits_{i=1}^{k+1}{a_i}=k \lceil{\frac{k}{\varphi}} \rceil +a_{k+1}=k(c+1)+(c+1)=(k+1)(c+1)=(k+1) \lceil{\frac{k+1}{\varphi}} \rceil$
Minimality: También tenga en cuenta que $a_{k+1}=k+1-m<k+1$, lo $a_{k+1}$ es el entero más pequeño que satisface la relación de divisibilidad, y porque tenemos una partición, $a_{k+1} \not =a_i \, \forall i$.
Estamos, pues, hecho por inducción. Ahora, desde la $x_n$ es único e $a_n$ satisface las condiciones dadas, $x_n=a_n \, \forall n \in \mathbb{Z}^+$ y hemos terminado. I) $x_n$ es surjective y ii) $x_{x_n}=n$ sigue trivialmente.
Yo creo que es inevitable aquí solo para plantear una expresión para la solución y, a continuación, demostrar que cumple con los requisitos, más de deducir la solución de forma directa con los requisitos. Así que voy a utilizar la forma de la solución que se propuso; por otro lado voy demostrar todo lo que sobre él directamente, en lugar de referirse a la teoría.
La pregunta discrimina $0$, negando la ciudadanía de los números naturales, y este sesgo (para mí) complica fórmulas y comprensión. Por lo tanto, voy a adaptar a la pregunta de la siguiente manera por primera anunciar $\def\N{\mathbf N}0\in\N$ (naturalización de $0$) y, a continuación, cambiando todo lo que un paso hacia abajo: $a_i=x_{i+1}-1$ todos los $i\in\N$. A continuación, la siguiente formulación es claramente equivalente a la pregunta: la secuencia de $(a_i)_{i\in\N}$ se determina el requisito de que cada una de las $a_i\in\N$ es mínima tal que $a_i\neq a_j$$0\leq j<i$, e $a_0+a_1+\ldots+a_i$ es divisible por $i+1$ (en particular uno ha $a_0=0$). Muestran que el mapa de $i\mapsto a_i$ es una involución de $\N$, en otras palabras $a_{a_i}=i$ todos los $i\in\N$ (por supuesto, esto implica que el mapa es surjective).
Voy a utilizar el piso y el techo funciones ampliamente; también voy a indicar las complementarias de la parte fraccionaria $\def\dn#1{\lfloor#1\rfloor}\def\up#1{\lceil#1\rceil}\up x-x$ de un número real $x$$\def\cfr#1{\operatorname{cf}(#1)}\cfr x$, y la proporción áurea por $\phi$. El último satisface $1+\phi=\phi^2$ y por lo tanto también se $1/\phi+1=\phi$$1/\phi^2+1/\phi=1$, que las identidades suele ser utilizada sin necesidad de mencionar.
Para un entero $k>0$ dos condiciones complementarias será importante. La condición denotado $\def\lo{\operatorname{low}}\lo(k)$ se dijo a si $$ \cfr{k\phi}=\cfr{k/\phi}<1/\phi=1-1/\phi^2 \quad\text{o, equivalentemente,}\quad \cfr{k/\phi^2}>1/\phi^2=1-1/\phi $$ mientras que la condición denotado $\def\hi{\operatorname{high}}\hi(k)$ se dijo a si $$ \cfr{k\phi}=\cfr{k/\phi}>1/\phi=1-1/\phi^2 \quad\text{o, equivalentemente,}\quad \cfr{k/\phi^2}<1/\phi^2=1-1/\phi $$ (las equivalencias debido a la $\cfr{k\phi}+\cfr{k/\phi^2}=1$). Los casos son mutuamente excluyentes, y la igualdad no puede suceder, ya que significaría $(k+1)/\phi\in\mathbf N$, lo cual es imposible debido a $\phi$ es irracional.
Al $\lo(l)$, y luego poner las $n=\up{l/\phi}$ ha $\cfr{l/\phi}=n-l/\phi<1/\phi$, y por lo $n\phi-l=\phi(n-l/\phi)<1$ donde $l=\dn{n\phi}$; por el contrario $\lo(\dn{n\phi})$ es válido para cada entero $n>0$. Del mismo modo al $\hi(h)$, y luego poner las $n=\up{h/\phi^2}$ ha $\cfr{h/\phi^2}=n-h/\phi^2<1/\phi^2$, lo $n\phi^2-h=\phi^2(n-h/\phi^2)<1$ donde $h=\dn{n\phi^2}$; por el contrario $\hi(\dn{n\phi^2})$ es válido para cada entero $n>0$.
Ahora defina $(a_i)_{i\in\N}$ explícitamente por $$ a_i= \begin{cases} 0 & \text{if %#%#%,} \\ \up{i\phi}=i+\up{i/\phi} & \text{if %#%#%,} \\ \dn{i/\phi}=i-\up{i/\phi^2} & \text{if %#%#%.} \\ \end{casos} $$ La escritura de los índices de $i=0$ $\lo(i)$ $\hi(i)$ obtenemos $l$. Del mismo modo la escritura de los índices de $\lo(l)$$l=\dn{n\phi}$$a_l=l+n=\dn{n\phi+n}=\dn{n\phi^2}$, obtenemos $h$. Vemos que $$ a_{\dn{n\phi}}=\dn{n\phi^2} \quad\text{y}\quad a_{\dn{n\phi^2}}=\dn{n\phi} \qquad\text{para todos los $\hi(h)$,} $$ y ya que este cubre todos los casos, claramente $h=\dn{n\phi^2}$ es una involución de $a_h=h-n=\dn{n\phi^2-n}=\dn{n\phi}$.
En la divisibilidad de la condición, que se sigue de la siguiente hecho más fuerte. Aunque sencillo, por inducción, que en realidad no dar ninguna comprensión profunda de por qué esta divisibilidad tiene.
Lema 1 Para todos los $n\in\N$ ha $i\mapsto A_i$.
Prueba por inducción sobre $\N$. Para $k\in\N$ la suma es vacío y el lado derecho es $\sum_{i<k}a_i=k\dn{k/\phi}$. Ahora suponga que el lema para $k$, a deducir por $k=0$. Si $0$, $k$ donde $k+1$$\hi(k)$; también se $\phi\up{k/\phi}-k>1$ en este caso, y así $$ \sum_{i\leq k}a_i=k\dn{k/\phi}+\dn{k/\phi} =(k+1)\dn{k/\phi}=(k+1)\dn{(k+1)/\phi}. $$ Por otro lado, si $\up{k/\phi}>(k+1)/\phi$, $\dn{(k+1)/\phi}=\dn{k/\phi}$ donde $a_k=\dn{k/\phi}$$\lo(k)$; también se $\phi\up{k/\phi}-k<1$ en este caso, y así $$ \sum_{i\leq k}a_i=k\dn{k/\phi}+\arriba{k\phi} =k\dn{k/\phi}+\dn{k/\phi}+1+k=k(k+1)(\dn{k/\phi}+1)=(k+1)\dn{(k+1)/\phi}. $$
Finalmente, para mostrar que cada una de las $\up{k/\phi}<(k+1)/\phi$ es el mínimo número de satisfacer los requisitos de inyectividad y la divisibilidad, la siguiente va a ser utilizado.
Lema 2 Siempre que $\dn{(k+1)/\phi}=\dn{k/\phi}+1$ ha $a_k=\up{k\phi}$; por otra parte $a_i$ mantiene si y sólo si $0\leq i<\dn{k/\phi}$.
Prueba. De $i\in\{a_0,a_1,\ldots,a_{k-1}\}$ $\dn{k/\phi}\in\{a_0,a_1,\ldots,a_{k-1}\}$ es de la siguiente manera (usando$\lo(k)$$i\leq\dn{k/\phi}-1$, lo $a_i\in\{\up{i\phi},\dn{i/\phi}\}$. Asimismo, para $\phi>1$ uno se $a_i<k$, por lo que deberemos $i=a_{a_i}\in\{a_0,a_1,\ldots,a_{k-1}\}$ menos $i=\dn{k/\phi}$. Pero $a_i\leq k$ significa que $\dn{k/\phi}\in\{a_0,a_1,\ldots,a_{k-1}\}$, mientras que tenemos $a_i=k$, lo que sólo puede ocurrir si $a_i=k=a_{a_k}$, que es el si $i=a_k$; por el contrario si $i<k$ $a_k<k$ y, de hecho,$\hi(k)$.
Ahora para envolver todo, la secuencia de $\hi(k)$ define una involución de $i=\dn{k/\phi}=a_k$ que por lema $a_i=k$ satisface la condición de divisibilidad. Para mostrar que cada una de las $(a_i)_{i\in\N}$ es el mínimo para satisfacer la condición de divisibilidad y la distinción de los anteriores valores de $\N$, de la nota de primera que menos $1$ mantiene, el valor de $a_k$ es el primero en su clase de congruencia modulo $a_i$, por lo que la divisibilidad solo se muestra es mínima. Al $\lo(k)$ sí, lema $a_k=\dn{k/\phi}<k+1$ muestra que todos los valores de $k+1$ ya están presentes entre los valores anteriores $\lo(k)$. Pero en este caso $2$ es el segundo en su clase de congruencia modulo $i\leq\dn{k/\phi}$, después de lo prohibido valor de $a_0,a_1,\ldots,a_{k-1}$, por lo que uno tiene minimality aquí.
Anexo Lema 2 se utiliza sólo para una pequeña parte de arriba (sólo en el caso de $a_k=\up{k\phi}=\dn{k/\phi}+k+1$). Sin embargo toda su fuerza es útil para demostrar que los pares de $k+1$ también forman el conjunto de los puestos de frío (seguro pares, perdiendo posiciones) en el juego de Wijthoff del Nim, donde los jugadores se turnan para modificar un par de números naturales, la disminución de cualquiera de ellos o a ambos por la misma cantidad, y un jugador incapaz de mover (en la posición $\dn{k/\phi}$) pierde. Las posiciones son clasificados de manera inductiva como frío/caliente: $i=\dn{k/\phi}$ es frío; cualquier posición desde la que se puede mover a una posición de frío es caliente; cualquier posición en la que uno se puede mover sólo a caliente posiciones en frío. El hecho de que $(k,a_k)$ es el conjunto de los puestos de frío para este juego se traduce en la siguiente declaración.
La proposición $(0,0)$ es el lexicográficamente de la secuencia mínima para que el mapa de $(0,0)$ es inyectiva $\{\,(k,a_k)\mid k\in\N\,\}$, y el mapa de $(a_i)_{i\in\N}$ es inyectiva $i\mapsto a_i$.
Prueba. Desde $\N\to\N$, se ve que ambos mapas son, de hecho, bijections. El establecimiento de minimality requiere un poco más de trabajo. Lema 2 muestra que al $i\mapsto a_i-i$ mantiene, el valor de $\def\Z{\mathbf Z}\N\to\Z$ es el primer valor no utilizado todavía. Para el caso de $\dn{n\phi^2}-\dn{n\phi}=n$, primero observar que los valores de $\hi(k)$ $a_k=\dn{k/\phi}$ formulario contiguo segmento de $\lo(k)$: el valor de $a_i-i$ ocupa el $0\leq i<k$, los valores de $\Z$ $k=0$ $0$ corriendo a través de las $0<l<k$ y ocupan los correspondientes valores positivos $\lo(l)$, mientras que los valores de $l=\dn{n\phi}$ $0<n<k/\phi$ $\dn{n\phi^2}-\dn{n\phi}=n$ corriendo a través de las $0<h<k$, y ocupar los correspondientes valores negativos $\hi(h)$. Por lo tanto, hay $h=\dn{n\phi^2}$ valores sucesivos $0<n<k/\phi^2$ que están prohibidas a $\dn{n\phi}-\dn{n\phi^2}=-n$, y el valor real $k$ ocupa el primer libre positivo valor $a_i-i$. Esto significa que para probar minimality en este caso, es suficiente para excluir como candidatos a $a_k-k$ los valores de a $a_k=\up{k\phi}$ incluido, pero esto es lo que lexema 2 no.
Esto no es ni siquiera un comienzo en una solución; es simplemente algunas observaciones que podrían ser útiles (o al menos de interés), y que son demasiado largo para un comentario.
Voy a escribir $x(n)$$x_n$. Algo muy interesante que pasa si escribimos $n$ $x(n)$ en una modificación de la Zeckendorf la notación. La modificación es que voy a escribir
$$n=\sum_{k\ge 1}e_kF_k\;,$$
donde cada una de las $e_k\in\{0,1\}$, y si el estándar de representación, que no utiliza $F_1$,$e_2=1$, le permitir $e_2=1,e_1=0$$e_2=0,e_1=1$. La elección no será, sin embargo, ser al azar.
En primer lugar, aquí está el primer $19$ valores de $x(n)$, marcado para mostrar que a este punto no hay ningún contraejemplo a la afirmación de que $x\big(x(n)\big)=n$$n\in\Bbb Z^+$.
$$\begin{array}{r} n:&1&\color{red}{2}&\color{red}{3}&\color{blue}{4}&\underline{5}&\color{blue}{6}&\color{green}{7}&\underline{8}&\color{cyan}{9}&\color{magenta}{10}&\color{green}{11}&\color{purple}{12}&\tiny{13}&\color{cyan}{14}&\tiny{15}&\color{magenta}{16}&\tiny{17}&\tiny{18}&\color{purple}{19}\\ x_n:&1&\color{red}{3}&\color{red}{2}&\color{blue}{6}&\underline{8}&\color{blue}{4}&\color{green}{11}&\underline{5}&\color{cyan}{14}&\color{magenta}{16}&\color{green}{7}&\color{purple}{19}&\tiny{21}&\color{cyan}{9}&\tiny{24}&\color{magenta}{10}&\tiny{27}&\tiny{29}&\color{purple}{12} \end{array}$$
Aquí es la misma tabla de modificación Zeckendorf notación:
$$\begin{array}{r|r|r|r|c|c} n&x(n)&n_{\text{Zeck}}&x(n)_{\text{Zeck}}&\text{Shift}&\text{Fibonacci numbers}\\ \hline 1&1&10&1&\to&F_2,F_1\\ 2&3&100&1000&\leftarrow&F_3,F_4\\ 3&2&1000&100&\to&F_4,F_3\\ 4&6&1001&10010&\leftarrow\\ 5&8&10000&100000&\leftarrow&F_5,F_6\\ 6&4&10010&1001&\to\\ 7&11&10100&101000&\leftarrow\\ 8&5&100000&10000&\to&F_6,F_5\\ 9&14&100001&1000010&\leftarrow\\ 10&16&100100&1001000&\leftarrow\\ 11&7&101000&10100&\to\\ 12&19&101001&1010010&\leftarrow\\ 13&21&1000000&10000000&\leftarrow&F_7,F_8\\ 14&9&1000010&100001&\to\\ 15&24&1000100&10001000&\leftarrow\\ 16&10&1001000&100100&\to\\ 17&27&1001001&10010010&\leftarrow\\ 18&29&1010000&10100000&\leftarrow\\ 19&12&1010010&101001&\to \end{array}$$
La elección de $F_1$ o $F_2$ en la representación de $n$ es determinada por la dirección de la rotación. Si reemplazamos $\to$$0$$\leftarrow$$1$, el Cambio de la columna se convierte en
$$0101101011011010110\;,$$
que es el principio de Fibonacci palabra, OEIS A096270, que es el punto fijo del mapa $0\mapsto01,1\mapsto011$.
No es una respuesta, pero podría ayudar a alguien. Yo no puedo probar esto, es la observación. Con $\phi = \frac {1+\sqrt 5}2$, los naturales mayor que $1$ se dividen en pares $\lceil n\phi \rceil$$\lceil n\phi^2 \rceil$. Esta es una partición como $\frac 1\phi + \frac 1{\phi^2}=1$. A continuación,$a_{\lceil n\phi \rceil}=\lceil n\phi^2 \rceil$$a_{\lceil n\phi^2 \rceil}=\lceil n\phi \rceil$. La brecha entre ellos los elementos de la pareja es$n$$\phi^2=1+\phi$. Yo no puedo relacionar esta a la divisibilidad de la prueba.
Ver este documento, Una Curiosa Bijection en Números Naturales por B. J. Venkatachala en el Diario de Secuencias de Enteros, Vol. 12 (2009).
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
