Competition problem — Combinatorics

Library / /286 of 377

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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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