Library / Harvard-MIT Mathematics Tournament /264 of 352

Harvard-MIT Mathematics Tournament

Combinatorics Difficulty 5.5 AIME, harder Prove it United States

Problem:

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?

Solutions — 2

Solution 1

Solution:

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 \leq y \leq 100$ and $|x| \leq 100 - |y|$ , so $x$ can take on the values $-100 + |y|, -98 + |y|, \ldots, 100 - |y|$ . There are $101 - |y|$ such values, so the total number of such locations is
$\sum_{y=-100}^{100} 101 - |y| = 201 \cdot 101 - 2 \cdot \frac{100(100+1)}{2} = 101^2 = 10201$

Solution 2

Solution:

Answer: 10201 Same as Combinatorics Test problem 4.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.