HMMT 二月 2009 · 冲刺赛 · 第 12 题

英文解析

12. [ 7 ] Bob is writing a sequence of letters of the alphabet, each of which can be either uppercase orlowercase, according to the following two rules:
    • If he had just written an uppercase letter, he can either write the same letter in lowercase afterit, or the next letter of the alphabet in uppercase .
    • If he had just written a lowercase letter, he can either write the same letter in uppercase afterit, or the preceding letter of the alphabet in lowercase .
    For instance, one such sequence is a aa aBCDdcb bC . How many sequences of 32 letters can he writethat start at (lowercase) a and end at (lowercase) z ? (The alphabet contains 26 letters from a to z .)
    Answer: 376
    Solution: The smallest possible sequence from a to z is a aBCD . . . Zz , which has 28 letters. Toinsert 4 more letters, we can either switch two (not necessarily distinct) letters to lowercase and backagain (as in a aBCc cDEF f F GH . . . Zz ), or we can insert a lowercase letter after its correspondinguppercase letter, insert the previous letter of the alphabet, switch back to uppercase, and continue the
    ( )
    sequence (as in a aBCcb bCDE . . . Zz ). There are = 13 · 27 sequences of the former type and 2527
    of the latter, for a total of 376 such sequences.2
    12 HARVARD-MIT MATHEMATICS TOURNAMENT, 21 FEBRUARY 2009 — GUTS ROUNDth