跳蚤路径计数

How many different paths can the flea travel by?

专题: Brainteaser / 脑筋急转弯
难度: L4
来源: QuantQuestion

个人笔记

题目详情

一只跳蚤要从两点之间前进，总距离 100 英寸。它每次只能朝同一方向跳 1 英寸或 2 英寸。

问：它一共有多少种不同的跳法（路径）能恰好走完 100 英寸？

英文原题

A flea is going between two points which are 100 inches apart by jumping (always in the same direction) either one inch or two inches at a time. How many different paths can the flea travel by?

解析

设 $a_n$ 为走完 $n$ 英寸的跳法数。

最后一步若跳 1 英寸，则前面是走完 $n-1$ 的任意跳法；若跳 2 英寸，则前面是走完 $n-2$ 的任意跳法，因此

a_n=a_{n-1}+a_{n-2},\quad a_0=1,\ a_1=1.

所以 $a_n$ 是斐波那契数列，且 $a_n=F_{n+1}$ 。

所求为 $\boxed{a_{100}=F_{101}}$ 。

英文解析

Let $a_n$ be the number of ways to complete a jump of $n$ inches.

If the final jump is 1 inch, then the preceding part is any way to complete a jump of $n-1$ inches; if the final jump is 2 inches, then the preceding part is any way to complete a jump of $n-2$ inches. Therefore,

a_n=a_{n-1}+a_{n-2},\quad a_0=1,\ a_1=1.

Thus, $a_n$ is the Fibonacci sequence, and $a_n=F_{n+1}$ .

The required value is $\boxed{a_{100}=F_{101}}$ .