5
$\begingroup$

There are $X$ stones in the river.The stones are placed in such a way that a person can jump from one stone to the next one, or skip one and jump to the one after that. Find the number of ways in which one can jump across the stones from one river bank to another.

Note: We are always standing at the farther stone from the bank

For example:

  • If there is one stone, we can jump directly to the bank of the river i.e. only 1 way.
  • If there are 2 stones, we can jump from 1st to 2nd and then 2nd to bank or we can jump from 1st to bank skipping one stone(as mentioned in the question).
  • Similarly for 3 stones no. of ways are 3.
  • Similarly for 5 stones no. of ways are 8.

Is there any general technique to calculate the number of ways of crossing the river with $X$ stones?

$\endgroup$
10
$\begingroup$

Given n stones, the only option one has for the first jump is to go to stone n-1 or n-2. From that point on the options are the same as for stone n-1 or n-2, hence for any n, the number of options equals the sum of the options of n-1 and n-2. This generalises to the Fibonacci sequence (Fibonacci+1 to be exact). Hence the generalised technique to calculate this for n stones is Jumps=Fibonacci(n+1)

$\endgroup$
  • $\begingroup$ Thanx..got it.. $\endgroup$ – toadalskiii May 18 '15 at 9:36
7
$\begingroup$

Isn't this just the Fibonacci sequence: 1, 2, 3, 5, 8, 13, 21, ...

Explanation:

If you number the stones starting at the target bank: From $stone_{n}$ you can initially jump to either $stone_{n-1}$ or $stone_{n-2}$. This makes the number of ways from $stone_{n}$ to the target bank equal to $stone_{n-1} + stone_{n-2}$.

$\endgroup$
  • $\begingroup$ Thanx...now I got it $\endgroup$ – toadalskiii May 18 '15 at 9:35
  • $\begingroup$ Wow ... ninja'd by 10 seconds ... $\endgroup$ – Rand al'Thor May 18 '15 at 9:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.