PUMaC 2013 · 团队赛 · 第 1 题
PUMaC 2013 — Team Round — Problem 1
题目详情
- A token is placed in the leftmost square in a strip of four squares. In each move, 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. In how many ways can the token be moved so that after exactly 15 moves, it is in the rightmost square of the strip?
解析
- A token is placed in the leftmost square in a strip of four squares. In each move, 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. In how many ways can the token be moved so that after exactly 15 moves, it is in the rightmost square of the strip? SOLUTION: Let a be the number of ways to move the token to the third square in n steps, n where n ∈ N . By induction, a = F for k ≥ 1, where F is the Fibonacci sequence. So 2 k +1 2 k n a = F = 377. 15 14 ANSWER: 377