Skip to main content

2009 AMC 12B Problem 25

Problem 25 of 25HarderGeometryCounting & Probability

The set GG is defined by the points (x,y)(x, y) with integer coordinates, 3x7,3 \le |x| \le 7, and 3y7.3 \le |y| \le 7. How many squares of side at least 66 have their four vertices in G?G?

Answer choices

Show solution

Solution

GG consists of four 5×55 \times 5 blocks G1,,G4,G_1, \ldots, G_4, one in each quadrant. Any square of side 6\ge 6 uses exactly one vertex in each block, since two points in one block are less than 66 apart while points in different blocks are at least 66 apart. Sliding each block inward by (±5,±5)(\pm 5, \pm 5) superimposes them on one 5×55 \times 5 grid GG' (points with x,y2|x|, |y| \le 2). Each such square maps to either a single point of GG' or a square in G.G'. So the count equals the number of points of GG' plus 44 times the number of squares with vertices in G.G'. The grid has 42+32+22+12=304^2+3^2+2^2+1^2=30 axis-parallel squares. For a tilted square, let one side move aa units horizontally and bb units vertically, where a,b>0a,b\gt0 and a+b4.a+b\le4. For each ordered pair (a,b),(a,b), there are (5ab)2(5-a-b)^2 placements. The totals for a+b=2,3,4a+b=2,3,4 are 9,8,3,9,8,3, respectively, giving 2020 tilted squares and 5050 squares altogether. Therefore the required count is 25+450=225.25+4\cdot50=225. Thus, the correct answer is E.

More practice

Concepts: lattice point · bijection · counting shapes in figures

Problem text and solution from the LIVE past-contest archive. See also the AoPS wiki page for community solutions.