0
$\begingroup$

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.
$\endgroup$
3
$\begingroup$

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$?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.