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 ABand every occurrence of B with BA , hence creating a string that is twice as long. After 10 minutes,
there are 2 = 1024 letters on the board. How many adjacent pairs are the same letter?10
解析
英文解析
- [ 8 ] Abbot writes the letter A on the board. Every minute, he replaces every occurrence of A with ABand every occurrence of B with BA , hence creating a string that is twice as long. After 10 minutes,
there are 2 = 1024 letters on the board. How many adjacent pairs are the same letter?10
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 then nnumber 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 stagen 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 resultsin in the next minute,
AA ! ABAB
AB ! ABBA
BA ! BAAB
BB ! BABAwe see that our adjacent pair V W must have been AB or BA . The number of such pairs is preciselyb .
n 1
From the relation a + b = 2 1 for all n 0, we obtain the recurrence relationnn nn 1
a = 2 1 an 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