Competition problem — Combinatorics

Library / /43 of 94

Combinatorics Difficulty 4.8 AIME Find the answer United States

Problem:

A lattice point in the plane is a point of the form $(n, m)$ , where $n$ and $m$ are integers. Consider a set $S$ of lattice points. We construct the transform of $S$ , denoted by $S'$ , by the following rule: the pair $(n, m)$ is in $S'$ if and only if any of $(n, m-1)$ , $(n, m+1)$ , $(n-1, m)$ , $(n+1, m)$ , and $(n, m)$ is in $S$ . How many elements are in the set obtained by successively transforming $\{(0,0)\}$ 14 times?

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:

Transforming it $k \geq 1$ times yields the "diamond" of points $(n, m)$ such that $|n| + |m| \leq k$ . The diamond contains $(k+1)^2 + k^2$ lattice points (this can be seen by rotating the plane 45 degrees and noticing the lattice points in the transforms form two squares, one of which is contained in the other), so the answer is $421$ .

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.