HMMT 十一月 2012 · 冲刺赛 · 第 30 题

HMMT November 2012 — Guts Round — Problem 30

[ 15 ] A monkey forms a string of letters by repeatedly choosing one of the letters a , b , or c to type at random. Find the probability that he first types the string aaa before he first types the string abc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT NOVEMBER 2012, 10 NOVEMBER 2012 — GUTS ROUND

解析

[ 15 ] 3 Answer: It suffices to assume that the monkey starts all over as soon as he has typed a string 7 that ends in no prefix of either abc or aaa . For instance, if the monkey gets to abb we can throw these out because there’s no way to finish one of those strings from this without starting all over. Now, we draw the tree of all possible intermediate stages under this assumption; there are not many possibilities. The paths from the root ”a” are: a- aa- aaa a- aa- aab- aabc a- ab- abc The first and last possibilities have probability 1 / 27 each and the middle one has probability 1 / 81, so 1 / 27 3 in total the probability of getting the first before the second or the third is = . 1 / 27+1 / 81+1 / 27 7 Guts Round