Competition problem — Combinatorics

Library / /82 of 128

Combinatorics Difficulty 5.7 AIME, harder Prove it Philippines

Problem:

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.

Solution

Solution:

We assign the weight $4^{k}$ to each $G$ in the sequence, where $k$ is the number of $A$ 's to the right of this $G$ . In each operation, if $4^{k}$ is the weight of the $G$ in the $"AG"$ being replaced, then each of the three $G$ 's in $"GAAA"$ have a weight of $4^{k-1}$ . So the sum of the weights decreases by $4^{k} - 3 \cdot 4^{k-1} = 4^{k-1}$ in each operation. Since the sum of weights in the initial sequence is finite, and the sum of the weights of all $G$ 's must be a nonnegative integer, Silverio can only perform a finite number of operations.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.