Library / /736 of 1394

, 2023

Combinatorics Difficulty 5.3 AIME, harder Prove it United States

Problem:

Richard starts with the string $HHMMMMTT$ . A move consists of replacing an instance of $HM$ with $MH$ , replacing an instance of $MT$ with $TM$ , or replacing an instance of $TH$ with $HT$ . Compute the number of possible strings he can end up with after performing zero or more moves.

Solution

Solution:

The key claim is that the positions of the $M$ s fully determines the end configuration. Indeed, since all $H$ s are initially left of all $T$ s, the only successful swaps that can occur will involve $M$ s. So, picking $\binom{8}{4} = 70$ spots for $M$ s and then filling in the remaining 4 spots with $H$ s first and then $T$ s gives all possible arrangements.

It is not hard to show that all of these arrangements are also achievable; just greedily move $M$ s to their target positions.

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.