HMMT 二月 2017 · COMB 赛 · 第 4 题

英文解析

4. Sam spends his days walking around the following 2 × 2 grid of squares.
   1 2
   4 3
   Say that two squares are adjacent if they share a side. He starts at the square labeled 1 and everysecond walks to an adjacent square. How many paths can Sam take so that the sum of the numberson every square he visits in his path is equal to 20 (not counting the square he started on)?
   Proposed by: Sam Korsky
   Answer: 167
   Note that on the first step, Sam can either step on 2 or 4. On the second step, Sam can either stepon 1 or 3, regardless of whether he is on 2 or 4. Now, for example, say that Sam takes 8 steps. Histotal sum will be 2 + 1 + 2 + 1 + 2 + 1 + 2 + 1 + 2 a , where a is the number of times that he decides tostep on the larger number of his two choices. Solving gives a = 4 . As he took 8 steps, this gives him
   ( ) = 70 ways in this case.8
   We can follow a similar approach by doing casework on the number of steps he takes. I will simply list 4
   ( ) ( )
   8 9
   them out here for brevity. For 8 steps, we get = 70 . For 9 steps, we get = 84 . For 12 steps, we
   4 3
   ( ) ( )
   12 13
   get a contribution on = 12 . For 13 steps, we get a contribution of = 1 . Therefore, the final
   1 0
   answer is 70 + 84 + 12 + 1 = 167 .