Question 131
Silverio is very happy for the 25th year of the PMO. In his jubilation, he ends up writing a finite sequence of $A$'s and $G$'s on a nearby blackboard. He then performs the following operation: if he finds at least one occurrence of the string $"AG"$, he chooses one at random and replaces it with $"GAAA"$. He performs this operation repeatedly until there is no more $"AG"$ string on the blackboard. Show that for any initial sequence of $A$'s and $G$'s, Silverio will eventually be unable to continue doing the operation.