HMMT 十一月 2022 · 冲刺赛 · 第 24 题

HMMT November 2022 — Guts Round — Problem 24

[12] A string consisting of letters A , C , G , and U is untranslatable if and only if it has no AUG as a consecutive substring. For example, ACUGG is untranslatable. Let a denote the number of untranslatable strings of length n . It is given that there exists a unique n triple of real numbers ( x, y, z ) such that a = xa + ya + za for all integers n ≥ 100. Compute n n − 1 n − 2 n − 3 ( x, y, z ). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT November 2022, November 12, 2022 — GUTS ROUND Organization Team Team ID#

解析

[12] A string consisting of letters A , C , G , and U is untranslatable if and only if it has no AUG as a consecutive substring. For example, ACUGG is untranslatable. Let a denote the number of untranslatable strings of length n . It is given that there exists a unique n triple of real numbers ( x, y, z ) such that a = xa + ya + za for all integers n ≥ 100. Compute n n − 1 n − 2 n − 3 ( x, y, z ). Proposed by: Pitchayut Saengrungkongka Answer: (4 , 0 , − 1) Solution: If a sequence is untranslatable, the first n − 1 letters must form an untranslatable sequence as well. Therefore, we can count a by n • Append any letter to an untranslatable sequence of length n − 1, so 4 a ways. n − 1 • Then, subtract with the case when the sequence ends with AUG . There are a sequences in this n − 3 case. Thus, a = 4 a − a for all integers n ≥ 3, so the answer is (4 , 0 , − 1) n n − 1 n − 3