Manipulación con cuerdas acertijo.

Question

A partir de la "cadena" $PI$ ¿Puedo o no transformarlo en la "cadena"? $PK$ aplicando las siguientes reglas (cada regla puede utilizarse cualquier número de veces, en cualquier orden, y $x$ y $y$ representa una parte de una cadena)?

Regla 1. Puede transformar la cadena $xI$ en $xIK$ . Por ejemplo: $PI$ puede transformarse en $PIK$ .

Regla 2. Puede transformar la cadena $Px$ en $Pxx$ . Por ejemplo: $PIIK$ puede transformarse en $PIIKIIK$ .

Regla 3. Puede transformar la cadena $xIIIy$ en $xKy$ . Por ejemplo: $PKIIIK$ puede transformarse en $PKKK$ .

Regla 4. Puede transformar la cadena $xKKy$ en $xy$ . Por ejemplo: $PKKI$ puede transformarse en $PI$ .

He aquí una secuencia válida de transformaciones de $PI$ a $PIK$ :

• $PI$ se convierte en $PII$ utilizando la Regla 2.
• $PII$ se convierte en $PIIII$ utilizando la Regla 2.
• $PIIII$ se convierte en $PIIIIK$ utilizando la Regla 1.
• $PIIIIK$ se convierte en $PIK$ utilizando la Regla 3.

Answer 1

CONSEJO: Considere el número de $I$ s en una palabra. Deja que $n_k$ sea el número después de $k$ pasos, de modo que $n_0=1$ . Reglas $1$ y $4$ no afectan al número de $I$ s, así que cuando se aplican, tenemos $n_{k+1}=n_k$ . Regla $2$ duplica el número, así que cuando se aplica tenemos $n_{k+1}=2n_k$ . Por último, la norma $3$ reduce el número en $3$ por lo que cuando se aplica, tenemos $n_{k+1}=n_k-3$ . Ahora mira $n_k\bmod 3$ ; ¿puede esto ser $0$ ?