HMMT 二月 2022 · COMB 赛 · 第 3 题

HMMT February 2022 — COMB Round — Problem 3

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

解析

Michel starts with the string HM M T . An operation consists of either replacing an occurrence of H with HM , replacing an occurrence of M M with M OM , or replacing an occurrence of T with M T . For example, the two strings that can be reached after one operation are HM M M T and HM OM T . Compute the number of distinct strings Michel can obtain after exactly 10 operations. Proposed by: Gabriel Wu Answer: 144 Solution: Each final string is of the form HM xM 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.