Seguimiento de la secuencia de números naturales

Question

Seguimiento de la secuencia de

Denotar por $\mathbb{N}=\{0,1,2,...\},~$ el conjunto de los números naturales, y por $I_{m}=\{0,1,...,m-1\}\,$ el conjunto de los números naturales menores que el natural dado el número de $m$. Deje $c=(c_0,c_1,...,c_{m-1})\,$ $m$- secuencia de los números naturales, y $p=max\{c_0,c_1,...,c_{m-1}\},\,$ la mayor duración de la secuencia de $c$

A continuación, la secuencia

$t(c)=(t_0,t_1,...,t_p)\,$

donde $t_j,j\in I_{p+1}\,$ denotar el número de términos de la secuencia de $ c$ eso son iguales a $j$, se llama traza de $c$. Es claro que los términos de la traza cumple las condiciones

$t_0+t_1+...+t_p=m\,$

$t_1+2t_2+...+pt_p=c_0+c_1+...+c_{m-1}\,$

Denotan por

$t^{0}(c)=c\,$

$t^{n}(c)=t(t^{n-1}(c))\,$

1.El conjunto de secuencias

$B=\{(1,0,0,1),(2,2),(0,0,2),(2,0,1),(1,1,1),(0,3)\}\,$

que es el ciclo de longitud 6 se llama "'pulsera de secuencias"', porque para cada secuencia $c$ $B$ tiene

$t^6 (c)=c\,$

2.El conjunto de secuencias

$R=\{(0,1,1),(1,2)\}\,$

que es el ciclo de longitud 2 que se llama "'anillo de secuencias"', porque para cada secuencia $c $ $R$ tiene

$t^2 (c)=c\,$

El conjunto

$ H=B\cup R\,$ es llamado "' agujero negro de secuencias"'

Razones por las que el nombre se porque supongo que:

Reclamo: Para cada secuencia finita $a$ de los números naturales existe número natural $n$ tal que $t^n(a)\in H\,$, en otras palabras, cada secuencia converge a $H$.

Secuencia $a$ es de tipo $B$ si su convergen a$H$$B$, por ejemplo, secuencia $(2,3)$ es de tipo $B$ porque

$t^3((2,3))=(0,0,2)\in B\,$

Y las secuencias que converge a $H$ $R$ son de tipo $R$, por ejemplo, la secuencia de $(0)$ es de tipo $R$ porque

$t^6((0))=(1,2)\in R\,$

Mis preguntas son.

1. Es mi suposición de verdad
2. Si es cierto ¿cómo decidir de qué tipo es cualquier secuencia finita de números naturales
3. Se puede hacer en cualquier programa o algorithme para determinar de qué tipo es cierta secuencia. Gracias

Answer 1

Esta no es una solución completa, pero parece reducir el problema a un análisis de los casos de $m\le2$.

Voy a escribir $t^k$ $k$- composición del pliegue de $t$ con sí mismo, por lo que que $t^1=t$, $t^2=t\circ t$, etc.

Yo también voy a escribir $|\{c\}|$ para el número de elementos distintos de la $m$-tupla $c=(c_0,c_1,\dots,c_{m-1})\in\mathbb{N}^m$.

Y voy a escribir cosas como $(n,m^k,p)$ como abreviación $(n,m,m,\dots,m,p)$ donde $m$ es repetido $k$ veces.

Una primera observación es que el $t(c)=t(c')$ para cualquier permutación $c'$ de $c$.

Lema: $|t^2(c)|\geq |c|$ si y sólo si $|\{c\}|=1$, o $|\{c\}|=2$ $c=(a,b^{|c|-1})$ (hasta permutación) donde $a\ne b$.

Prueba: Tenemos $|t^2(c)|=\max\{t_0,\dots,t_p\}+1$, lo $|t^2(c)|\ge |c|$ si y sólo si $|t^2(c)|\in \{|c|,|c|,+1\}\ffi \{|c|-1,|c|\}\cap \{t_0,\dots,t_p\}\ne \emptyset$, que es equivalente a las condiciones por encima de.

Reclamo: Si $m=|c|\ge 3$ $|t^n(c)|<|c|$ algunos $n\ge1$.

Comentario: Esto nos permite reducir para el caso de $m\in \{1,2\}$ a establecer la reclamación en la pregunta, si es cierto.

La prueba de la demanda: este es un caso-por-caso de análisis.

1. Si $|\{c\}|>2$ $n=2$ va a hacer por el lema.

2. Si $|\{c\}|=1$,$c=(0^m)\implies t(c)=(m)$, o $c=(1^m)\implies t(c)=(0,m)$ o $c=(2^3)\implies t^6(c)=(0,3)$, o $c=(2^m)$ donde $m\ge4$, por lo que el $t(c)=(0,0,m)$ o $c=(x^m)$ donde $x\ge3$. En este caso, $t(c)=(0^x,m)$, $t^2(c)=x,0^{m-1},1), t^3(c)=(m-1,1,0^{x-2},1)$, $t^4(c)=(x-2,2,0^{m-3},1)$. If $m\ge4$ o $x\ge5$ $|\{t^4(c)\}|>2$ , lo $|t^4(c)|=m$ $|t^6(c)|<m$ por el lema. Si $m=3$$x\in \{3,4\}$$t^7(c)=(0,3)$.

3. Si $|\{c\}|=2$ $c$ no es de la forma $(x,y^{m-1})$ (hasta permutación), a continuación, $|t^2(c)|<|c|$ por el lema.

4. Si $|\{c\}|=2$$c=(x,y^{m-1})$, supongamos primero que $x<y$. Nosotros ha $t(c)=(0^x,1,0^{y-x-1},m-1)$ $t^2(c)=(y-1,1,0^{m-3},1)$ y si $y\ge3$ $t^3(c)=(m-3,2,0^{y-3},1)$ , por lo que si $m>3$ $|t^4(c)|=\max\{m-3,2\}+1=\max\{m-2,3\}<m$, mientras que si $m=3=y$ la comprobación de las tres posibilidades de $c=(x,3,3)$ $x\in \{0,1,2\}$ da $t^{11}(c)=(0,3)$, y si $m=3<y$ $t^4(c)=t(0,2,0^{y-3},1)=(y-2,1,1)$ $t^5(c)=(0,1,0^{y-4},1), t^6(c)=(y-3,1,1),\dots, t^{2(y-1)}(c)=(1,1,1), t^{2y-1}(c)=(0,3)$. Si $y\in \{1,2\}$ $|t^3(c)|=2$ . Si $c=(x,y^{m-1})$ donde $x>y$ $t(c)$ es una permutación de $t(y,x^{m-1})$, por lo que el argumento de la anterior se aplica.

Answer 2

A raíz de mac respuesta parcial, la suposición es verdadera para $m \in \{1,2\}$, con lo que parece ser cierto en general.

Si $m=1$, $c=(x)$ para algunos $x \in \mathbb{N}$. Si $x>0$, $t(c) = (0^x,1)$, y bien $x=1$, en cuyo caso $t^2(c) = (0,2), t^3(c) = (1,0,1)$, e $t^4(c) = (1,2) \in R$. Si $x=0$, $t(c) = (1)$, y estamos en el primer caso.

Ahora vamos a $m=2$$c = (x,y)$. Observación: Si $n>2$, $t^2((n,2)) = (n-1,2)$, mientras que $t((2,2)) = (0,0,2) \in B$, lo $t^{1+2(n-2)}((n,2)) = t^{2n-3}((n,2)) \in B$ siempre $n \ge 2$.

Si $x=y \in \{0,1\}$, $t(c) = (0^x,2),t^2(c) = (x,0,1)$, y $t^4(c) = (0,1,1) \in R$.

Si $x=y>1$, $t(c) = (0^x,2),t^2(c) = (x,0,1),t^3(c) = (1,1,0^{x-2},1)$, y $t^4(c) = (x-2,3)$.

Si $x=y=2$, $t^4(c) \in B$; si $x=y \in \{3,4\}$, $t^6(c) = (2,2) \in B$; y si $x=y=5$, $t^{10}(c) = (2,2) \in B$.

Si $x=y>5$, $t^5(c) = (0,0,0,1,0^{x-6},1)$, y $t^6(c) = (x-3,2)$ donde $x-3>2$, de donde $t^{6+2(x-3)-3}(c) = t^{2x-3}(c) \in B$ por la Observación.

Ahora, supongamos, sin pérdida de generalidad que $x<y$; a continuación,$t(c) = (0^x,1,0^{y-x-1},1)$, e $t^2(c) = (y-1,2)$, en $R$ si $y=2$. Si $y=1$, $t^4(c) = (1,2) \in R$. Y si $y \ge 3$, la Observación se asegura de que $t^{2+2(y-1)-3}(c) = t^{2y-3}(c) \in B$.