HMMT 二月 2008 · COMB 赛 · 第 4 题

英文解析

4. [ 4 ] Kermit the frog enjoys hopping around the infinite square grid in his backyard. It takes him 1 Jouleof energy to hop one step north or one step south, and 1 Joule of energy to hop one step east or onestep west. He wakes up one morning on the grid with 100 Joules of energy, and hops till he falls asleepwith 0 energy. How many different places could he have gone to sleep?
   Answer: 10201
   It is easy to see that the coordinates of the frog’s final position must have the same parity. Supposethat the frog went to sleep at ( x, y ). Then, we have that − 100 ≤ y ≤ 100 and | x | ≤ 100 − | y | , so xcan take on the values − 100 + | y | , − 98 + | y | , . . . , 100 − | y | . There are 101 − | y | such values, so the totalnumber of such locations is
   ∑100
   100(100 + 1)
   101 − | y | = 201 · 101 − 2 · = 101 = 10201 .2
   y = − 1002