HMMT 二月 2023 · COMB 赛 · 第 3 题

HMMT February 2023 — COMB Round — Problem 3

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.

解析

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. Proposed by: Albert Wang Answer: 70 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, ( ) 8 picking = 70 spots for M s and then filling in the remaining 4 spots with H s first and then T s gives 4 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.