返回题库

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

HMMT November 2018 — Guts Round — Problem 10

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. [ 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
解析

英文解析

  1. [ 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