Demostrar que si $z^n$ es un palíndromo para algunos $n>0$ entonces $z$ también es un palíndromo para cualquier alfabeto E.

Question

Demostrar que si $z^n$ es un palíndromo para algunos $n>0$ entonces $z$ también es un palíndromo para cualquier alfabeto E.

He aquí una prueba de la afirmación anterior:

Dejemos que $w = x^n$ . Si $n = 1$ entonces el resultado es trivial.
Supongamos que $n > 1$ . Entonces $$x^n = reverse (x^n) = (reverse (x))^n.$$ Escriba esto como $$x x \dots x = reverse (x) reverse (x) \dots reverse (x).$$ Pero $x$ y $reverse (x)$ tienen la misma longitud, por lo que $x = reverse (x)$ .

¿Puede alguien justificar esta línea en la prueba? $$reverse (x^n) = (reverse (x))^n$$

O proporcionar un prueba alternativa .

Answer 1

Un simple argumento demuestra la afirmación. Esencialmente, demuestra explícitamente que $\text{rev}(z^n) = (\text{rev}(z))^n$ (si lo supones, no hay nada que demostrar).

Antes de mostrar el argumento, algunos preliminares. Cualquier palabra puede escribirse como $z = z_1 \dots z_k$ , donde $k \geq 0$ es la longitud de $z$ y el $z_i$ son caracteres simples de cualquier alfabeto $E$ . Una palabra $z = z_1 \dots z_k$ es palíndromo si $z = \text{rev}(z)$ donde $\text{rev}(z) = z_k \dots z_1$ .

Veamos ahora la prueba. La hipótesis del enunciado dice que, para algunos $n > 0$ tenemos $z^n = \text{rev}(z^n)$ . Escrito de forma más explícita, para $z = z_1 \dots z_k$ tenemos

\begin {align} z^n &= \overbrace { \overbrace {z_1 \dots z_k}^z \N - \cdots \ \overbrace {z_1 \dots z_k}^z}^{n \text {veces}} \\ &= \\ \text {rev}(z^n) &= z_k \dots z_1 \ \cdots \ z_k \dots z_1 \end {align}

(Obsérvese que la primera aparición de $z_k$ en $\text{rev}(z^n)$ corresponde a la última aparición de $z_k$ en $z^n$ y la primera aparición de $z_{k-1}$ en $\text{rev}(z^n)$ corresponde a la última aparición de $z_{k-1}$ en $z^n$ y así sucesivamente. Esta es la forma de construir $\text{rev}(z^n)$ de $z^n$ .)

Desde $n > 0$ la identidad $z^n = \text{rev}(z^n)$ es válida, en particular, para la primera $k$ caracteres de $z^n$ y $\text{rev}(z^n)$ Por lo tanto \begin {align} z = z_1 \dots z_k = z_k \dots z_1 = \text {rev}(z) \end {align} Por lo tanto, $z$ es palíndromo.

---

Tenga en cuenta que no hemos asumido que $\text{rev}(z^n) = (\text{rev}(z))^n$ . En realidad, el hecho de que $\text{rev}(z^n) = (\text{rev}(z))^n$ es una consecuencia inmediata de lo que hemos demostrado.

Answer 2

$$\begin{array}{rcl} z^k \in \text{Palindrome} &\implies& z^k = \text{rev}(z^k) \\ &\implies& z^k{}_1 = z^k{}_{kn}~,~z^k{}_2 = z^k{}_{kn-1}~,~z^k{}_3 = z^k{}_{kn-2}~,~\dots \\ &\implies& z_1 = z_n~,~z_2 = z_{n-1}~,~z_3 = z_{n-2}~,~\dots \\ &\implies& z \in \text{Palindrome} \end{array}$$

La tercera línea se desprende de $z^k{}_{a} = z_{a ~\rm{mod}~ n}$