HMMT 二月 2012 · COMB 赛 · 第 5 题

HMMT February 2012 — COMB Round — Problem 5

Dizzy Daisy is standing on the point (0 , 0) on the xy -plane and is trying to get to the point (6 , 6). She starts facing rightward and takes a step 1 unit forward. On each subsequent second, she either takes a step 1 unit forward or turns 90 degrees counterclockwise then takes a step 1 unit forward. She may never go on a point outside the square defined by | x | ≤ 6 , | y | ≤ 6, nor may she ever go on the same point twice. How many different paths may Daisy take?

解析

Dizzy Daisy is standing on the point (0 , 0) on the xy -plane and is trying to get to the point (6 , 6). She starts facing rightward and takes a step 1 unit forward. On each subsequent second, she either takes a step 1 unit forward or turns 90 degrees counterclockwise then takes a step 1 unit forward. She may never go on a point outside the square defined by | x | ≤ 6 , | y | ≤ 6, nor may she ever go on the same point twice. How many different paths may Daisy take? Answer: 131922 Because Daisy can only turn in one direction and never goes to the same square twice, we see that she must travel in an increasing spiral about the origin. Clearly, she must arrive at (6 , 6) coming from below. To count her paths, it therefore suffices to consider the horizontal and vertical lines along which she travels (out of 5 choices to move upward, 6 choices leftward, 6 choices downward, and 6 choices rightward). Breaking up the cases by the number of complete rotations she performs, ( )( ) ( )( ) ( )( ) ( )( ) ( )( ) ( )( ) 3 3 3 3 3 3 5 6 5 6 5 6 5 6 5 6 5 6 the total is + + + + + = 131922 . 0 0 1 1 2 2 3 3 4 4 5 5