A token is placed on the leftmost square in a strip of four squares. You are allowed to move the token left or right along the strip by sliding it a single square, provided that the token stays on the strip. How many ways can the token be moved such that after 15 moves, it is in the rightmost square of the strip?

716

it's correct!! how did you do alestair!! thanks alot

377 is the correct answer..not 716..

brilliant qn don't give any answer... Hint: fibonacci

To solve this problem, we can consider the possible positions of the token at each move and use a recursive approach to count the number of ways.

Let's break down the problem step by step:

1. Initially, the token is in the leftmost square of the strip.

2. At each move, the token can either move left or move right by a single square.

3. We want to count the number of ways the token can be moved such that after 15 moves, it is in the rightmost square.

To count the number of ways the token can be moved, we can use a recursive approach. Let's define a function f(n) that represents the number of ways the token can reach the rightmost square in n moves.

At each move, the token either moves left or moves right. Therefore, we have two possibilities for each move. We can express this as follows:

f(n) = f(n-1) + f(n+1)

This recursive equation tells us that the number of ways to reach the rightmost square in n moves is equal to the number of ways to reach the rightmost square in (n-1) moves, plus the number of ways to reach the rightmost square in (n+1) moves.

To start the recursion, we need some base cases:

f(0) = 1 (if the token is already in the rightmost square, we consider it as a valid move)
f(-1) = 0 (if the token moves beyond the leftmost square, it cannot reach the rightmost square)

Using this recursive equation, we can calculate f(15) to find the total number of ways the token can be moved to reach the rightmost square after 15 moves.