PUMaC 2023 · 组合（A 组） · 第 8 题
PUMaC 2023 — Combinatorics (Division A) — Problem 8
题目详情
- A spider is walking on the boundary of equilateral triangle △ ABC (vertices labelled in coun- terclockwise order), starting at vertex A . Each second, she moves to one of her two adjacent vertices with equal probability. The windiness of a path that starts and ends at A is the net number of counterclockwise revolutions made. For example, the windiness of the path ABCA is 1, and the windiness of the path ABCACBACBA is − 1. What is the remainder modulo 1000 of the sum of the squares of the windiness values taken over all possible paths that end back at vertex A after 2025 seconds? Name: Team: Write answers in table below: Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 2
解析
- A spider is walking on the boundary of equilateral triangle △ ABC (vertices labelled in coun- terclockwise order), starting at vertex A . Each second, she moves to one of her two adjacent vertices with equal probability. The windiness of a path that starts and ends at A is the net number of counterclockwise revolutions made. For example, the windiness of the path ABCA is 1, and the windiness of the path ABCACBACBA is − 1. What is the remainder modulo 1000 of the sum of the squares of the windiness values taken over all possible paths that end back at vertex A after 2025 seconds? Proposed by Atharva Pathak Answer: 50 P n 3 n 2 Let 3 n = 2025. We seek S = (2 k − n ) . Expanding, this equals k =0 3 k n X 3 n 2 2 S = (4 k − 4 nk + n ) (1) 3 k k =0 P 3 n 3 n 3 n ℓ ′ 3 n − 1 Let p ( x ) = (1 + x ) . Note that p ( x ) = x . Note that xp ( x ) = (3 n ) x (1 + x ) = ℓ =0 ℓ P P 3 n 3 n 3 n 3 n ℓ 2 ′′ 2 3 n − 2 ℓ ℓx . Note that x p ( x ) = (3 n )(3 n − 1) x (1 + x ) = ℓ ( ℓ − 1) x . (Here, ℓ =0 ℓ ℓ =0 ℓ ′ ′ a − 1 a q ( x ) denotes the formal derivative of the polynomial q , defined by q ( x ) = ax for q ( x ) = x and extended linearly.) 1 1 4 4 n 2 2 2 2 2 Note that 4 · [ ℓ ( ℓ − 1)+ ℓ ] − 4 n · ℓ + n = ℓ − ℓ + n . For ℓ = 3 k , this equals 4 k − 4 nk + n . 9 3 9 3 Let ζ = exp(2 πi/ 3). We apply the roots of unity filter to obtain 2 X 1 4 4 n 2 ′′ ′ ′ 2 j S = [ ( x p ( x ) − xp ( x )) − xp ( x ) + n p ( x )]( ζ ) (2) 3 9 3 j =0 j where we evaluate the summand at x = ζ . The summand simplifies to the expression 1 3 n − 2 2 n (1 + x ) (3 n ( x − 1) + 4 x ) (3) 3 1 3 n − 2 1 n For x = 1, the summand is clearly n 2 · 4 = n 8 . For x = ζ , the summand is 3 3 1 1 3 n − 2 2 n n (1 + ζ ) (3 n ( ζ − 1) + 4 ζ ) = n ( − 1) ( − 9 n + 4) (4) 3 3 2 2 2 using the fact that 1 + ζ = − ζ and ( ζ − 1) = − 3 ζ . By symmetry the same holds for x = ζ . It follows that the sum is given by 1 1 2 1 2 n n 2 n n S = [ n 8 + ( − 1) ( − 9 n + 4 n )] = n 8 + ( − 1) n (4 − 9 n ) 3 3 3 9 9 We set n = 2025 / 3 = 675 and compute mod 1000 to obtain the desired answer. 5