Competition problem — Combinatorics

Library / /443 of 860

Combinatorics Difficulty 5.2 AIME, harder Find the answer

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^{\prime}$ , by the following rule: the pair $(n, m)$ is in $S^{\prime}$ 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. Spacing and $ signs are ignored.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.