1990 AIME 第 9 题

Question

将一枚均匀硬币抛掷

10

次。设从不连续两次出现正面的概率化为最简分数后是

\frac{i}{j}

。求

i+j

。

A fair coin is to be tossed

10

times. Let

\frac{i}{j},

in lowest terms, be the probability that heads never occur on consecutive tosses. Find

i+j.

答案

答案：73

知识点：递推计数斐波那契数列基本概率

难度评级：2000

小提示：

根据长度为

n

的抛掷序列以反面还是正面结尾，分别计算有效序列数

Count valid length-

n

toss strings according to whether they end in tails or heads

大提示：

所得递推式类似斐波那契数列，初始计数为

2

和

3

The resulting recurrence is Fibonacci-like, with initial counts

2

and

3

解答：

设

u_n

为不含连续正面的长度为

n

的抛掷序列数。任何有效的长度为

(n-1)

的序列后接

\mathrm{T}

，可得到以反面结尾的有效序列；任何有效的长度为

(n-2)

的序列后接

\mathrm{TH}

，可得到以正面结尾的有效序列。因此

u_n=u_{n-1}+u_{n-2}

，其中

u_1=2

，且

u_2=3

。由此

u_{10}=144

。所求概率为

\frac{144}{2^{10}}=\frac{9}{64}

，所以

i+j=9+64=73

。

Let

u_n

be the number of length-

n

toss strings with no consecutive heads. A valid string ending in tails is obtained by appending

\mathrm{T}

to any valid length-

(n-1)

string, while one ending in heads is obtained by appending

\mathrm{TH}

to any valid length-

(n-2)

string. Hence

u_n=u_{n-1}+u_{n-2},

with

u_1=2

and

u_2=3.

This gives

u_{10}=144.

The probability is

\frac{144}{2^{10}}=\frac{9}{64},

so

i+j=9+64=73.

1990 AIME 第 9 题

答案：73

难度评级：2000

小提示：

大提示：

解答：

其他年份的第 9 题