HMMT 二月 2017 · COMB 赛 · 第 4 题

HMMT February 2017 — COMB Round — Problem 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 every second walks to an adjacent square. How many paths can Sam take so that the sum of the numbers on every square he visits in his path is equal to 20 (not counting the square he started on)?

解析

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 every second walks to an adjacent square. How many paths can Sam take so that the sum of the numbers on 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 step on 1 or 3, regardless of whether he is on 2 or 4. Now, for example, say that Sam takes 8 steps. His total sum will be 2 + 1 + 2 + 1 + 2 + 1 + 2 + 1 + 2 a , where a is the number of times that he decides to step on the larger number of his two choices. Solving gives a = 4 . As he took 8 steps, this gives him ( ) 8 = 70 ways in this case. 4 We can follow a similar approach by doing casework on the number of steps he takes. I will simply list ( ) ( ) 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 .