Library / /343 of 1394

, 2022

Combinatorics Difficulty 5.0 AIME, harder Find the answer United States

Problem:

Michel starts with the string $H M M T$ . An operation consists of either replacing an occurrence of $H$ with $H M$ , replacing an occurrence of $M M$ with $M O M$ , or replacing an occurrence of $T$ with $M T$ . For example, the two strings that can be reached after one operation are $H M M M T$ and $H M O M T$ . Compute the number of distinct strings Michel can obtain after exactly 10 operations.

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:

Each final string is of the form $H M x M T$ , where $x$ is a string of length 10 consisting of $M$ s and $O$ s. Further, no two $O$ s can be adjacent. It is not hard to prove that this is a necessary and sufficient condition for being a final string.

Let $f(n)$ be the number of strings of length $n$ consisting of $M$ s and $O$ where no two $O$ s are adjacent. Any such string of length $n+2$ must either end in $M$ , in which case removing the $M$ results in a valid string of length $n+1$ , or $M O$ , in which case removing the $M O$ results in a valid string of length $n$ . Therefore, $f(n+2)=f(n)+f(n+1)$ . Since $f(1)=2$ and $f(2)=3$ , applying the recursion leads to $f(10)=144$ .

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.