Sliding token

The idea is to work backward from the final move. After move 15, the token must be in the rightmost square, so after move 14, the token must be in the third square (from the left). Similarly, after move 13, the token can be in the second square or the fourth square. Let us use the notation $f(n) = (a,b,c,d)$ to represent the number of ways for the token to arrive at the desired square after the $n^{\rm th}$ move if it is in the square corresponding to the respective position in the list (so for example, $f(13) = (0,1,0,1)$ states that there is 1 way for the token to be moved from the second square and fourth square each, so that it is in the rightmost square after move 15). Then we must have $f(12) = (1,0,2,0)$ and $f(11) = (0,3,0,2)$ , and it becomes clear that for each previous state, the value in the $k^{\rm th}$ square is the sum of the values in its adjacent squares in the present state. Hence at the initial state ( $n = 0$ ), we want the value contained in the first square. Since $f(0) = (377,0,610,0)$ , this is simply $F_{14} = \boxed{377}$ , the 14th Fibonacci number.

Used graph theory for this one. Any graph can be expressed using an adjacency matrix $A[m, n]$ , where in this case $m=n=4$ since we have 4 squares. Adjacent nodes are given a 1, otherwise 0. For example, $A[a,b]$ is 1 since you can go from a to b, but $A[b, d]$ is 0 since you cannot go from b to d in one move. This relationship yields the following matrix:

. | a b c d
-----------
a | 0 1 0 0
b | 1 0 1 0
c | 0 1 0 1
d | 0 0 1 0

Now, to find the number of paths of length k from a to d , you first calculate the matrix $A^{k}$ . The number of paths from A to D can then be given by $A^{k}[a,d]$ .

 0   610  0   377
610  0   987  0
 0   987  0   610
377  0   610  0

So, $A^{k}[a,d]$ = 377 paths between a and d .

Let $a_n$ , $b_n$ , $c_n$ , $d_n$ is the number of ways to move the token to the 1st, 2nd, 3rd and 4th square (called A, B, C, D respectively) after n moves.

If n is odd, the token must be moved to B or D, otherwise, it is moved to A or C. If the token is moved to A or D, it only have a way to move (to B and C, respectively). If the token is moved to B or C, it have 2 ways to move (B to A or C, C to B or D). We can represent it as follow:

$a_n = b_{n-1}$

$b_n = a_{n-1} + c_{n-1}$

$c_n = b_{n-1} + d_{n-1}$

$d_n = c_{n-1}$

We can further analyse them:

$b_n = c_{n-1} + b_{n-2}$

$c_{n+1} = b_{n} + c_{n-1}$

Initially, $a_0 = 1$ , $b_0 = 0$ , $c_0 = 0$ , $d_0 = 0$

After 1 move, $b_1 = 1$ , $c_1 = 0$

After 2 moves, $b_2 = 0$ , $c_2 = 1$

After 3 moves, $b_3 = 2$ , $c_3 = 0$

As we could see, with n odd, $b_n$ and $c_{n+1}$ share the Fibonacci sequence, $b_n = F_n$ and $c_{n+1} = F_{n+1}$ . So $d_{15} = c_{14} = F_{14} = 377$ , it's also the solution of the problem.

If necessary, we can draw 15 strips of 4 squares as described in the problem. On the first turn, the token must be on the 2nd square. On the 2nd turn, the token must be either on the 1st square or the 3rd square. On the 3rd turn, the token must be either on the 2nd square or the 4th square, and so forth. On the 14th turn, the token must be on the 3rd square. Using this pattern, we can find the number of ways to get to the 4th square in 15 turns by finding the number of ways to get to the squares on the previous turns.

On the first turn, the only way we can get to the second square is by moving right, so there is one way to get to the 2nd square on the first turn.

On the second move, there is one way to get to the 1st square -- moving left -- and there is one way to get to the 3rd square -- moving right.

On the third move, if the token was on the 1st square on the previous move then it can only go to the 2nd square. However, if the token was on the 3rd square on the previous move then it can go to the 2nd square or the 4th square. Thus, there are 2 ways to get to the 2nd square on the 3rd move and 1 way to get to the 4th square.

On the 4th move, to get to the 1st square the token must've been on the 2nd square the previous turn, and since there were 2 ways to get to that square previously, there are 2 ways to get to here as well. To get to the 3rd square, the token could have been on the 2nd or 4th square on the previous turn, so there are $2 + 1 = 3$ ways to get to the 3rd square on this turn.

Continuing this pattern until the 13th turn, we get that there are 233 ways to get to the 2nd square and 144 ways to get to the 4th square on this turn. Since the token must be on the 3rd square on the 14th move (and on the 4th square on the 15th move), we simply add 233 and 144 together to get $377$ , the total number of ways the token can be moved that satisfy the problem.

Let $T_k(n)$ denote the number of ways the token can be moved from the first to the $k$ -th square of the strip (counted from the left) in exactly $n$ moves. We claim that for any positive odd integer $n$ ,

$T_2(n) = F_n \text{ and } T_4(n) = F_{n-1},$

where $F_n$ denotes the $n$ -th number in the Fibonacci sequence. We will prove this by induction. First, We will show that it holds for our base cases $n=1$ and $n=3$ . There's only one way to move the token to the second square in one move (and $F_1=1$ ), there's also just one way to move the token to the fourth square in three moves (and $F_{3-1}=F_2=1$ ), and there are two ways to move the token to the second square in three moves (and $F_3=2$ ).

Now, let's assume that

$T_2(k-2) = F_{k-2} \text{ and } T_4(k-2) = F_{k-3}$

for some positive odd integer $k \geq 5$ . We know that

$T_2(k) = 2T_2(k-2) + T_4(k-2),$

because there are two ways to go from the second square to the second square in two moves, and there is one way to go from the fourth square to the second square in two moves. Similarly,

$T_4(k) = T_2(k-2) + T_4(k-2),$

because from both the second and the fourth square, there is just one way to go to the fourth square in two moves. Now, if we plug in our induction hypothesis in these two equations, we get

$T_2(k) = 2F_{k-2} + F_{k-3} \text{ and } T_4(k) = F_{k-2} + F_{k-3}.$

By definition,

$F_n = F_{n-1} + F_{n-2}$

for any positive integer $n \geq 3$ . Using this, we obtain

$T_2(k) = 2F_{k-2} + F_{k-3} = \left( F_{k-2}+F_{k-3} \right) + F_{k-2} = F_{k-1} + F_{k-2} = F_k,$

and

$T_4(k) = F_{k-2} + F_{k-3} = F_{k-1}.$

So,

$T_2(k) = F_k \text{ and } T_4(k) = F_{k-1}$

for any odd integer $k$ , which is what we wanted to prove. So, the number of ways the token can be moved such that after $15$ moves, it is in the rightmost square of the strip is $T_4(15) = F_{14} = \boxed{377}$ .

Describe the problem in matrix form: $A = \begin{bmatrix} 0 & 1 & 0 & 0\\ 1 & 0 & 1 &0 \\ 0& 1 & 0 &1 \\ 0 & 0 & 1 & 0 \end{bmatrix}$

$(A^t)[i][j]$ indicates the number of ways of moving from $i^{th}$ square to $j^{th}$ square during $t^{th}$ step.

Answer is $(A^{15})[1][4]$

consider a sequence of 4-tuples $a_n=(a_{1,n}, .., a_{4,n})$ where $a_{i,n}$ is the number of ways you can end on the $i^{th}$ spot after the $n^{th}$ move.

$a_0=(1,0,0,0)$ and $a_{i,n+1}=a_{i-1,n}+a_{i+1,n}$ where $a_{i,n}=0$ if $i$ is out of range.

With this set-up it is easy to prove by induction that the terms $a_{4,2n+1}$ follow odd terms of the Fibonacci sequence.

Let $f_n(x)$ be the number of ways the token can be moved $n$ times and end in square $x$ (1-4). We have $f_0(1)=1$ From here on, it is simple to draw a 16x4 grid, and $f_n(x)=f_{n-1}(x-1)+f_{n-1}(x+1)$ It is easy to list out values, and Fibonacci numbers appear. The answer is $\boxed{377}$ .

Call the squares 1,2,3,4 in order from leftmost. Let $a(n), b(n), c(n), d(n)$ be the number of ways the coin can be on squares 1,2,3,4 respectively after $n$ moves. We know $a(0) = 1, b(0) = c(0) = d(0) = 0$ from the initial condition and we want to find $d(15)$ .

Note that $a(n+1) = b(n), d(n+1) = c(n)$ ; the only way we can reach square 1 is if we come from square 2, and the only way we can reach square 4 is if we come from square 3.

Also, $b(n+1) = a(n) + c(n), c(n+1) = b(n) + d(n)$ ; we can reach square 2 if we come from squares 1 or 3, and we can reach square 4 if we come from squares 2 or 4.

So, simplifying, we get $b(n+2) = a(n+1) + c(n+1) = b(n) + c(n+1)$ and $c(n+2) = b(n+1) + d(n+1) = b(n+1) + c(n)$ . Also, $b(1) = a(0) + c(0) = 1+0 = 1$ , and we want to find $d(15) = c(14)$ .

Finally, let a new sequence $x(n)$ to be equal to $b(n)$ when $n$ is odd, and $c(n)$ when $n$ is even. Then when $n$ is odd,

$x(n+2) = b(n+2) = b(n) + c(n+1) = x(n) + x(n+1)$

and when $n$ is even,

$x(n+2) = c(n+2) = c(n) + b(n+1) = x(n) + x(n+1)$

Thus we have $x(n+2) = x(n+1) + x(n)$ for all $n$ . Since $x(0) = c(0) = 0, x(1) = b(1) = 1$ , $x$ is precisely the Fibonacci sequence. We have $x(14) = 377$ (well-known; either do a brute force or just pull some list of Fibonacci numbers ), and since $d(15) = c(14) = x(14)$ , we have $d(15) = \boxed{377}$ .