Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2009 AMC 12B Problems/Problem 25"
(→‎Solution 2)
Line 141: Line 141:
 
== Solution 2==
 
== Solution 2==
  
−
This is based on a clever transformation given in [http://www.example.com this page].
+
This is based on a clever bijection given in [http://www.example.com this page].
  
 
Consider any square <math>ABCD</math> where all four vertices are in <math>G</math>, and the side length is at least <math>6</math>, so the four vertices must lie in distinct quadrants (Same proof as in solution 1). Without loss of generality, assume that <math>A,B,C,D</math> are in the first, second, third, fourth quadrant. Then we consider the following mapping:
 
Consider any square <math>ABCD</math> where all four vertices are in <math>G</math>, and the side length is at least <math>6</math>, so the four vertices must lie in distinct quadrants (Same proof as in solution 1). Without loss of generality, assume that <math>A,B,C,D</math> are in the first, second, third, fourth quadrant. Then we consider the following mapping:
Line 159: Line 159:
  
 
So the answer is <math>25+4\cdot 50 = 225</math>
 
So the answer is <math>25+4\cdot 50 = 225</math>
 +
 
== See Also ==
 
== See Also ==
  
 
{{AMC12 box|year=2009|ab=B|num-b=24|after=Last Question}}
 
{{AMC12 box|year=2009|ab=B|num-b=24|after=Last Question}}

Revision as of 17:19, 31 December 2012

Problem

The set $G$ is defined by the points $(x,y)$ with integer coordinates, $3\le|x|\le7$, $3\le|y|\le7$. How many squares of side at least $6$ have their four vertices in $G$?

[asy] defaultpen(black+0.75bp+fontsize(8pt)); size(5cm); path p = scale(.15)*unitcircle; draw((-8,0)--(8.5,0),Arrow(HookHead,1mm)); draw((0,-8)--(0,8.5),Arrow(HookHead,1mm)); int i,j; for (i=-7;i<8;++i) { for (j=-7;j<8;++j) { if (((-7 <= i) && (i <= -3)) || ((3 <= i) && (i<= 7))) { if (((-7 <= j) && (j <= -3)) || ((3 <= j) && (j<= 7))) { fill(shift(i,j)*p,black); }}}} draw((-7,-.2)--(-7,.2),black+0.5bp); draw((-3,-.2)--(-3,.2),black+0.5bp); draw((3,-.2)--(3,.2),black+0.5bp); draw((7,-.2)--(7,.2),black+0.5bp); draw((-.2,-7)--(.2,-7),black+0.5bp); draw((-.2,-3)--(.2,-3),black+0.5bp); draw((-.2,3)--(.2,3),black+0.5bp); draw((-.2,7)--(.2,7),black+0.5bp); label("$-7$",(-7,0),S); label("$-3$",(-3,0),S); label("$3$",(3,0),S); label("$7$",(7,0),S); label("$-7$",(0,-7),W); label("$-3$",(0,-3),W); label("$3$",(0,3),W); label("$7$",(0,7),W); [/asy]

$\textbf{(A)}\ 125\qquad \textbf{(B)}\ 150\qquad \textbf{(C)}\ 175\qquad \textbf{(D)}\ 200\qquad \textbf{(E)}\ 225$

Solution

We need to find a reasonably easy way to count the squares.

First, obviously the maximum distance between two points in the same quadrant is $4\sqrt 2 < 6$, hence each square has exactly one vertex in each quadrant.

Given any square, we can circumscribe another axes-parallel square around it. In the picture below, the original square is red and the circumscribed one is blue.

[asy] defaultpen(black+0.75bp+fontsize(8pt)); size(7.5cm); path p = scale(.15)*unitcircle; draw((-8,0)--(8.5,0),Arrow(HookHead,1mm)); draw((0,-8)--(0,8.5),Arrow(HookHead,1mm)); int i,j; for (i=-7;i<8;++i) { for (j=-7;j<8;++j) { if (((-7 <= i) && (i <= -3)) || ((3 <= i) && (i<= 7))) { if (((-7 <= j) && (j <= -3)) || ((3 <= j) && (j<= 7))) { fill(shift(i,j)*p,black); }}}} draw((-7,-.2)--(-7,.2),black+0.5bp); draw((-3,-.2)--(-3,.2),black+0.5bp); draw((3,-.2)--(3,.2),black+0.5bp); draw((7,-.2)--(7,.2),black+0.5bp); draw((-.2,-7)--(.2,-7),black+0.5bp); draw((-.2,-3)--(.2,-3),black+0.5bp); draw((-.2,3)--(.2,3),black+0.5bp); draw((-.2,7)--(.2,7),black+0.5bp); label("$-7$",(-7,0),S); label("$-3$",(-3,0),S); label("$3$",(3,0),S); label("$7$",(7,0),S); label("$-7$",(0,-7),W); label("$-3$",(0,-3),W); label("$3$",(0,3),W); label("$7$",(0,7),W); draw( (5,3) -- (-3,4) -- (-4,-4) -- (4,-5) -- cycle, red ); draw( (5,4) -- (-4,4) -- (-4,-5) -- (5,-5) -- cycle, dashed + blue ); [/asy]

Let's now consider the opposite direction. Assume that we picked the blue square, how many different red squares do share it?

Answering this question is not as simple as it may seem. Consider the picture below. It shows all three red squares that share the same blue square. In addition, the picture shows a green square that is not valid, as two of its vertices are in bad locations.

[asy] defaultpen(black+0.75bp+fontsize(8pt)); size(7.5cm); path p = scale(.15)*unitcircle; draw((-8,0)--(8.5,0),Arrow(HookHead,1mm)); draw((0,-8)--(0,8.5),Arrow(HookHead,1mm)); int i,j; for (i=-7;i<8;++i) { for (j=-7;j<8;++j) { if (((-7 <= i) && (i <= -3)) || ((3 <= i) && (i<= 7))) { if (((-7 <= j) && (j <= -3)) || ((3 <= j) && (j<= 7))) { fill(shift(i,j)*p,black); }}}} draw((-7,-.2)--(-7,.2),black+0.5bp); draw((-3,-.2)--(-3,.2),black+0.5bp); draw((3,-.2)--(3,.2),black+0.5bp); draw((7,-.2)--(7,.2),black+0.5bp); draw((-.2,-7)--(.2,-7),black+0.5bp); draw((-.2,-3)--(.2,-3),black+0.5bp); draw((-.2,3)--(.2,3),black+0.5bp); draw((-.2,7)--(.2,7),black+0.5bp); label("$-7$",(-7,0),S); label("$-3$",(-3,0),S); label("$3$",(3,0),S); label("$7$",(7,0),S); label("$-7$",(0,-7),W); label("$-3$",(0,-3),W); label("$3$",(0,3),W); label("$7$",(0,7),W); draw( (5,4) -- (-4,4) -- (-4,-5) -- (5,-5) -- cycle, red ); draw( (5,3) -- (-3,4) -- (-4,-4) -- (4,-5) -- cycle, red ); draw( (5,-3) -- (-2,-5) -- (-4,2) -- (3,4) -- cycle, dashed + green ); draw( (5,-4) -- (-3,-5) -- (-4,3) -- (4,4) -- cycle, red ); draw( scale(1.05)*((5,4) -- (-4,4) -- (-4,-5) -- (5,-5) -- cycle), dashed + blue ); [/asy]

The size of the blue square can range from $6\times 6$ to $14\times 14$, and for the intermediate sizes there is more than one valid placement. We will now examine the cases one after another. Also, we can use symmetry to reduce the number of cases. 

size  upper_right  solutions  symmetries  total
   6        (3,3)          1           1      1
 
   7        (3,3)          1           4      4
 
   8        (3,3)          1           4      4
   8        (3,4)          1           4      4
   8        (4,4)          3           1      3
 
   9        (3,3)          1           4      4
   9        (3,4)          1           8      8
   9        (4,4)          3           4     12
 
  10        (3,3)          1           4      4
  10        (3,4)          1           8      8
  10        (3,5)          1           4      4
  10        (4,4)          3           4     12
  10        (4,5)          3           4     12
  10        (5,5)          5           1      5
  
  11        (4,4)          3           4     12
  11        (4,5)          3           8     24
  11        (5,5)          5           4     20
  
  12        (5,5)          5           4     20
  12        (5,6)          5           4     20
  12        (6,6)          7           1      7
  
  13        (6,6)          7           4     28
  
  14        (7,7)          9           1      9

Summing the last column, we get that the answer is $\boxed{225}$.

Solution 2

This is based on a clever bijection given in this page.

Consider any square $ABCD$ where all four vertices are in $G$, and the side length is at least $6$, so the four vertices must lie in distinct quadrants (Same proof as in solution 1). Without loss of generality, assume that $A,B,C,D$ are in the first, second, third, fourth quadrant. Then we consider the following mapping:

\[A \to A' = A\] \[B \to B' = B + (0,10)\] \[C \to C' = C + (10,10)\] \[D \to D' = D + (10,0)\]

Then the new points $A'$, $B'$, $C'$, $D'$ are either being the same point or forming a square in $G_1 = G \cap \{ x>0, y>0 \}$, a 5x5 grid.

Conversely, for any point in $G_1$, it can be reversed to a square $ABCD$; however, for any square in $G_1$, there are four possible squares $ABCD$ that were mapped to them. Therefore the number of possible squares $ABCD$ is equal to $25 + 4N$, where $N$ is the number of squares inscribed in $G_1$.

Moreover by the same idea in solution 1, each square (with sides parallel or slanted to the axes) in a $G_1$ can be inscribed in a square in $G_1$, with sides parallel to one of the axes, call it "standard square". Noticing that each standard square of side length $a$ corresponds to $a$ inscribed squares, and that there are $(5-a)^2$ number of standard squares of side length $a$, we have

\[N = \sum_{a=1}^{4} a(5-a)^2 = 1\cdot 16 + 2\cdot 9 + 3 \cdot 4 + 4 \cdot 1 = 16+18+12+4=50\]

So the answer is $25+4\cdot 50 = 225$

See Also

2009 AMC 12B (Problems • Answer Key • Resources)
Preceded by
Problem 24 		Followed by
Last Question
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2009_AMC_12B_Problems/Problem_25&oldid=50415"