Frog crossing

Number Theory Level 4

A frog wants to cross a river that is 11 feet across.

There are 10 stones in a line leading across the river, separated by 1 foot. He can either jump to the next stone or jump over a stone, but always moving forward (toward the other side of the river).

How many different ways can he cross the river? Remember, just getting to the 10th rock won't be quite enough, he would need to make one final jump to get across.

For example, one way to cross would be (where 1 means he goes to the next rock and 2 means he skips one):

1,2,2,1,1,2,1,1

The answer is 144.

2 solutions

David Pilling
May 15, 2016

To get to the $(n+2)$ th stone, he could either come from the $(n+1)$ th stone or the $n$ th stone.

So, the number of ways to get to the $n$ th stone is $a_n = a_{n-1} + a_{n-2}$ or the famous Fibonacci numbers.

So $a_{11} = \boxed{144}$

Ayush Jain
May 16, 2016

Frog can go without any leap i.e.1111 _ up to 11times or it can go by taking one leap and other single steps . it is same as arranging one two and 9 ones =10C1

Going this way we get no of ways as 1+ 10C1+9C2+8C3+7C4+6C5=144

WE STOPPED AT 6C5 BECAUSE MAXIMUM 5 LEAPS CAN BE TAKEN ie 5 TWO AND ONE 1

Nice solution, Ayush!

Geoff Pilling - 5 years, 1 month ago

Frog crossing

The answer is 144.

2 solutions

0 pending reports