HMMT 二月 2009 · 冲刺赛 · 第 12 题
HMMT February 2009 — Guts Round — Problem 12
题目详情
- [ 7 ] Bob is writing a sequence of letters of the alphabet, each of which can be either uppercase or lowercase, according to the following two rules: • If he had just written an uppercase letter, he can either write the same letter in lowercase after it, 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 after it, or the preceding letter of the alphabet in lowercase . For instance, one such sequence is aAaABCDdcbBC . How many sequences of 32 letters can he write that start at (lowercase) a and end at (lowercase) z ? (The alphabet contains 26 letters from a to z , without wrapping around, so that z does not precede a .) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . th 12 HARVARD-MIT MATHEMATICS TOURNAMENT, 21 FEBRUARY 2009 — GUTS ROUND
解析
- [ 7 ] Bob is writing a sequence of letters of the alphabet, each of which can be either uppercase or lowercase, according to the following two rules: • If he had just written an uppercase letter, he can either write the same letter in lowercase after it, 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 after it, or the preceding letter of the alphabet in lowercase . For instance, one such sequence is aAaABCDdcbBC . How many sequences of 32 letters can he write that 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 aABCD . . . Zz , which has 28 letters. To insert 4 more letters, we can either switch two (not necessarily distinct) letters to lowercase and back again (as in aABCcCDEF f F GH . . . Zz ), or we can insert a lowercase letter after its corresponding uppercase letter, insert the previous letter of the alphabet, switch back to uppercase, and continue the ( ) 27 sequence (as in aABCcbBCDE . . . Zz ). There are = 13 · 27 sequences of the former type and 25 2 of the latter, for a total of 376 such sequences. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . th 12 HARVARD-MIT MATHEMATICS TOURNAMENT, 21 FEBRUARY 2009 — GUTS ROUND