Silverio is very happy for the 25th year of the PMO. In his jubilation, he ends up writing a finite sequence of As and Gs 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 As and Gs, Silverio will eventually be unable to continue doing the operation.
Problem
Source: Philippine MO 2023/5
Tags: combinatorics, Strings, Operations, PMO
gghx
19.03.2023 14:22
Sketch: note the number of Gs don't change, label them $G_1,\cdots G_n$ from left to right. Note their order never swaps. We prove by induction that the number of moves on each G is bounded. For $G_1$ it is obvious as it would keep moving towards the front. Suppose it is true for $G_{i-1}$. Then, it never changes position after some point. From then on $G_i$ would get closer to $G_{i-1}$ whenever it is operated on. This cannot happen an infinite number of times. The induction is complete.
starchan
19.03.2023 14:25
Number the positions of the string from left to right with numbers. For any string $S$ define it's weight $w(S)$ as the sum $\sum_{p} \frac{1}{2^p}$ where the sum is over all positions $p$ which contain the letter $G$. Observe that the number of $G$'s is always fixed and that after each operation it's weight $w(S)$ strictly increases. The problem concludes after noticing that you cannot have an infinite sequence of increasing weights, all containing the same number of $G$s. (hint: use base $2$).
carefully
19.03.2023 22:12
After each move, the string becomes lexicographically later, while the number of G's remains the same. The rest is trivial.