# Manipulation with strings riddle.

Starting with the "string" $PI$, can I or not transform it into the "string" $PK$ by applying the following rules (each rule can be used any number of times, in any order, and $x$ and $y$ represents a part of a string)?

Rule 1. You can transform the string $xI$, into $xIK$. Example: $PI$ can be transformed into $PIK$.

Rule 2. You can transform the string $Px$ into $Pxx$. Example: $PIIK$ can be transformed into $PIIKIIK$.

Rule 3. You can transform the string $xIIIy$ into $xKy$. Example: $PKIIIK$ can be transformed into $PKKK$.

Rule 4. You can transform the string $xKKy$ into $xy$. Example: $PKKI$ can be transformed into $PI$.

So here's a valid sequence of transformations from $PI$ to $PIK$:

• $PI$ becomes $PII$ using Rule 2.
• $PII$ becomes $PIIII$ using Rule 2.
• $PIIII$ becomes $PIIIIK$ using Rule 1.
• $PIIIIK$ becomes $PIK$ using Rule 3.

HINT: Consider the number of $I$s in a word. Let $n_k$ be the number after $k$ steps, so that $n_0=1$. Rules $1$ and $4$ don’t affect the number of $I$s, so when they’re applied, we have $n_{k+1}=n_k$. Rule $2$ doubles the number, so when it’s applied we have $n_{k+1}=2n_k$. Finally, Rule $3$ reduces the number by $3$, so when it’s applied, we have $n_{k+1}=n_k-3$. Now look at $n_k\bmod 3$; can this ever be $0$?