HMMT 十一月 2018 · 冲刺赛 · 第 10 题

HMMT November 2018 — Guts Round — Problem 10

[ 8 ] Abbot writes the letter A on the board. Every minute, he replaces every occurrence of A with AB and every occurrence of B with BA , hence creating a string that is twice as long. After 10 minutes, 10 there are 2 = 1024 letters on the board. How many adjacent pairs are the same letter?

解析

[ 8 ] Abbot writes the letter A on the board. Every minute, he replaces every occurrence of A with AB and every occurrence of B with BA , hence creating a string that is twice as long. After 10 minutes, 10 there are 2 = 1024 letters on the board. How many adjacent pairs are the same letter? Proposed by: Yuan Yao Answer: 341 Let a denote the number of adjacent pairs of letters that are the same after n minutes, and b the n n number of adjacent pairs that are di ↵ erent. Lemma 1. a = b for all n 0. n n 1 Proof. Any adjacent pair of identical letters XX at stage n either came from the same letter of stage n 1 ( W ! XX ), or two adjacent letters of stage n 1 ( V W ! M XXN ). Because A ! AB and B ! BA , they cannot have come from the same letter. If they came from a pair of adjacent letters, then observing what each adjacent pair of letters results in in the next minute, AA ! ABAB AB ! ABBA BA ! BAAB BB ! BABA we see that our adjacent pair V W must have been AB or BA . The number of such pairs is precisely b . n 1 n From the relation a + b = 2 1 for all n 0, we obtain the recurrence relation n n n 1 a = 2 1 a n n 1 from which we obtain values a = 0, a = 0, a = 1, a = 2, a = 5, a = 10, a = 21, a = 42, 0 1 2 3 4 5 6 7 a = 85, a = 170, and a = 341 . 8 9 10