HMMT 二月 2008 · COMB 赛 · 第 4 题

HMMT February 2008 — COMB Round — Problem 4

[ 4 ] Kermit the frog enjoys hopping around the infinite square grid in his backyard. It takes him 1 Joule of energy to hop one step north or one step south, and 1 Joule of energy to hop one step east or one step west. He wakes up one morning on the grid with 100 Joules of energy, and hops till he falls asleep with 0 energy. How many different places could he have gone to sleep?

解析

[ 4 ] Kermit the frog enjoys hopping around the infinite square grid in his backyard. It takes him 1 Joule of energy to hop one step north or one step south, and 1 Joule of energy to hop one step east or one step west. He wakes up one morning on the grid with 100 Joules of energy, and hops till he falls asleep with 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. Suppose that the frog went to sleep at ( x, y ). Then, we have that − 100 ≤ y ≤ 100 and | x | ≤ 100 − | y | , so x can take on the values − 100 + | y | , − 98 + | y | , . . . , 100 − | y | . There are 101 − | y | such values, so the total number of such locations is 100 ∑ 100(100 + 1) 2 101 − | y | = 201 · 101 − 2 · = 101 = 10201 . 2 y = − 100