HMMT 二月 2019 · COMB 赛 · 第 10 题

HMMT February 2019 — COMB Round — Problem 10

Fred the Four-Dimensional Fluffy Sheep is walking in 4-dimensional space. He starts at the origin. Each minute, he walks from his current position ( a , a , a , a ) to some position ( x , x , x , x ) with 1 2 3 4 1 2 3 4 integer coordinates satisfying 2 2 2 2 ( x − a ) +( x − a ) +( x − a ) +( x − a ) = 4 and | ( x + x + x + x ) − ( a + a + a + a ) | = 2 . 1 1 2 2 3 3 4 4 1 2 3 4 1 2 3 4 In how many ways can Fred reach (10 , 10 , 10 , 10) after exactly 40 minutes, if he is allowed to pass through this point during his walk?

解析

Fred the Four-Dimensional Fluffy Sheep is walking in 4-dimensional space. He starts at the origin. Each minute, he walks from his current position ( a , a , a , a ) to some position ( x , x , x , x ) with 1 2 3 4 1 2 3 4 integer coordinates satisfying 2 2 2 2 ( x − a ) +( x − a ) +( x − a ) +( x − a ) = 4 and | ( x + x + x + x ) − ( a + a + a + a ) | = 2 . 1 1 2 2 3 3 4 4 1 2 3 4 1 2 3 4 In how many ways can Fred reach (10 , 10 , 10 , 10) after exactly 40 minutes, if he is allowed to pass through this point during his walk? Proposed by: Brice Huang ( )( ) 3 40 40 Answer: 10 20 The possible moves correspond to the vectors ±〈 2 , 0 , 0 , 0 〉 , ±〈 1 , 1 , 1 , − 1 〉 , and their permutations. It’s not hard to see that these vectors form the vertices of a 4-dimensional hypercube, which motivates the change of coordinates ( ) x + x + x + x x + x − x − x x − x + x − x x − x − x + x 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 ( x , x , x , x ) ⇒ , , , . 1 2 3 4 2 2 2 2 Under this change of coordinates, Fred must travel from (0 , 0 , 0 , 0) to (20 , 0 , 0 , 0), and the possible moves correspond to the sixteen vectors 〈± 1 , ± 1 , ± 1 , ± 1 〉 . The new x -coordinate must increase 30 1 times and decrease 10 times during Fred’s walk, while the other coordinates must increase 20 times ( )( ) 3 40 40 and decrease 20 times. Therefore, there are possible walks. 10 20