PUMaC 2009 · 组合（B 组） · 第 1 题

PUMaC 2009 — Combinatorics (Division B) — Problem 1

Three people, John, Macky, and Rik, play a game of passing a basketball from one to another. Find the number of ways of passing the ball starting with Macky and reaching Macky again at the end of the seventh pass.

解析

Three people, John, Macky, and Rik, play a game of passing a basketball from one to another. Find the number of ways of passing the ball starting with Macky and reaching Macky again on the 7th pass. Solution. 42. Consider a graph with 3 verticies, corresponding to each player. Draw an edge between all pairs of people. Now, write down the adjacency matrix for this graph, and call it 7 7 M . We are interested in the upper left entry of M , and M can be computed using repeated squaring, to get 42 as the answer. Alternative Solution: We can rephrase the above solution in terms of recursions. Define the sequences a , b for n ≥ 0: a is the number of ways of passing the ball starting n n n from a player and reaching that same player again on the n -th pass, b is the number of ways n of passing the ball starting from a player and reaching a different player on the n -th pass. Then a = 0 , b = 1 and 0 1 a = 2 b n +1 n b = a + b n +1 n n since, for example: the ball can reach the same player on the n + 1-st pass if and only if it reached any of the two other players on the n -th pass. These recursions can be easily solved, or you can use them to compute the first few values of a . n