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 "1996 AIME Problems/Problem 7"

(→‎See also)
 
(11 intermediate revisions by 7 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
Two squares of a <math>7\times 7</math> checkerboard are painted yellow, and the rest are painted green. Two color schemes are equivalent if one can be obtained from the other by applying a rotation in the plane board. How many inequivalent color schemes are possible?
+
Two [[square]]s of a <math>7\times 7</math> checkerboard are painted yellow, and the rest are painted green. Two color schemes are equivalent if one can be obtained from the other by applying a [[rotation]] in the plane board. How many inequivalent color schemes are possible?
  
−
== Solution ==
+
== Solution 1 (Generalized)==
−
{{solution}}
+
There are <math>{49 \choose 2}</math> possible ways to select two squares to be painted yellow. There are four possible ways to rotate each board. Given an arbitrary pair of yellow squares, these four rotations will either yield two or four equivalent but distinct boards.
 +
 
 +
<center><table><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<asy>
 +
pathpen = black; pair O = (3.5,3.5); D(O);
 +
for(int i=0;i<7;++i)
 +
for(int j=0;j<7;++j)
 +
  D(shift(i,j)*unitsquare);
 +
fill(shift(4,3)*unitsquare,rgb(1,1,.4));fill(shift(4,5)*unitsquare,rgb(1,1,.4));
 +
fill(shift(3,4)*unitsquare,rgb(.8,.8,.5));fill(shift(1,4)*unitsquare,rgb(.8,.8,.5));
 +
fill(shift(2,3)*unitsquare,rgb(.8,.8,.5));fill(shift(2,1)*unitsquare,rgb(.8,.8,.5));
 +
fill(shift(3,2)*unitsquare,rgb(.8,.8,.5));fill(shift(5,2)*unitsquare,rgb(.8,.8,.5));
 +
 
 +
D(arc(O,1,280,350),EndArrow(4));
 +
D(arc(O,5^.5,-20,50),EndArrow(4));
 +
D(arc(O,1,10,80),EndArrow(4));
 +
D(arc(O,5^.5,70,140),EndArrow(4));
 +
D(arc(O,1,190,260),EndArrow(4));
 +
D(arc(O,5^.5,250,320),EndArrow(4));
 +
D(arc(O,1,100,170),EndArrow(4));
 +
D(arc(O,5^.5,160,230),EndArrow(4));
 +
</asy>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</td><td><asy>pathpen = black; pair O = (3.5,3.5); D(O);
 +
for(int i=0;i<7;++i)
 +
for(int j=0;j<7;++j)
 +
  D(shift(i,j)*unitsquare);
 +
fill(shift(4,5)*unitsquare,rgb(1,1,.4));
 +
fill(shift(2,1)*unitsquare,rgb(1,1,.4));
 +
fill(shift(1,4)*unitsquare,rgb(.8,.8,.5));
 +
fill(shift(5,2)*unitsquare,rgb(.8,.8,.5));
 +
 
 +
D(arc(O,5^.5,-20,50),EndArrow(4));
 +
D(arc(O,5^.5,70,140),EndArrow(4));
 +
D(arc(O,5^.5,250,320),EndArrow(4));
 +
D(arc(O,5^.5,160,230),EndArrow(4));
 +
</asy></td></tr><tr><td><font style="font-size:85%">For most pairs, there will be <br /> three other equivalent boards.</font></td><td><font style="font-size:85%">For those symmetric about the center, <br /> there is only one other.</font></td></tr></table></center>
 +
 
 +
Note that a pair of yellow squares will only yield <math>2</math> distinct boards upon rotation [[iff]] the yellow squares are rotationally symmetric about the center square; there are <math>\frac{49-1}{2}=24</math> such pairs. There are then <math>{49 \choose 2}-24</math> pairs that yield <math>4</math> distinct boards upon rotation; in other words, for each of the <math>{49 \choose 2}-24</math> pairs, there are three other pairs that yield an equivalent board.
 +
 
 +
Thus, the number of inequivalent boards is <math>\frac{{49 \choose 2} - 24}{4} + \frac{24}{2} = \boxed{300}</math>. For a <math>(2n+1) \times (2n+1)</math> board, this argument generalizes to <math>n(n+1)(2n^2+2n+1)</math> inequivalent configurations.
 +
 
 +
== Solution 2 (Casework) ==
 +
There are 4 cases:
 +
1. The center square is occupied, in which there are <math>12</math> cases.
 +
2. The center square isn't occupied and the two squares that are opposite to each other with respect to the center square, in which there are <math>12</math> cases.
 +
3. The center square isn't occupied and the two squares can rotate to each other with a <math>90^{\circ}</math> rotation with each other and with respect to the center square, in which case there are <math>12</math> cases.
 +
4. And finally, the two squares can't rotate to each other with respect to the center square in which case there are <math>\dbinom{12}{2} \cdot \frac{16}{4} = 264</math> cases.
 +
Add up all the values for each case to get <math>\boxed{300}</math> as your answer.
 +
 
 +
~First
 +
== Solution 3 (Burnside’s Lemma)==
 +
Consider the group <math>G=\mathbb{Z}/4\mathbb{Z}</math> with addition acting on set <math>X</math>, where <math>X</math> is the set of color schemes on the checkerboard. We now apply Burnside’s Lemma. Since <math>\mathbb{Z}/4\mathbb{Z}=\langle r \mid r^4=1\rangle</math>, we only need to consider 4 cases for <math>g</math> an element of <math>\mathbb{Z}/4\mathbb{Z}</math>.
 +
 
 +
1. <math>g=1</math>. There are clearly <math>{49 \choose 2}</math> cases.
 +
 
 +
2. <math>g=r</math>. Since this is a <math>90</math> degree rotation, there are no fixed points under this transformation.
 +
 
 +
3. <math>g=r^2</math>. There are <math>24</math> cases (which can be manually checked).
 +
 
 +
4. <math>g=r^3</math>. There are no cases since this is just Case <math>2</math> but with a <math>-90</math> degree rotation.
 +
 
 +
Therefore, by Burnside’s Lemma there are <math>\frac{1176+24+0+0}{|G|}=\frac{1200}{4}=\boxed{300}</math> inequivalent configurations (also known as orbits in group-theoretic terms).
  
 
== See also ==
 
== See also ==
−
*[[1996 AIME Problems]]
+
{{AIME box|year=1996|num-b=6|num-a=8}}
  
−
{{AIME box|year=1996|num-b=7|num-a=9}}
+
[[Category:Intermediate Combinatorics Problems]]
 +
{{MAA Notice}}

Latest revision as of 17:25, 31 August 2024

Problem

Two squares of a $7\times 7$ checkerboard are painted yellow, and the rest are painted green. Two color schemes are equivalent if one can be obtained from the other by applying a rotation in the plane board. How many inequivalent color schemes are possible?

Solution 1 (Generalized)

There are ${49 \choose 2}$ possible ways to select two squares to be painted yellow. There are four possible ways to rotate each board. Given an arbitrary pair of yellow squares, these four rotations will either yield two or four equivalent but distinct boards.

          [asy] pathpen = black; pair O = (3.5,3.5); D(O); for(int i=0;i<7;++i) for(int j=0;j<7;++j) D(shift(i,j)*unitsquare); fill(shift(4,3)*unitsquare,rgb(1,1,.4));fill(shift(4,5)*unitsquare,rgb(1,1,.4)); fill(shift(3,4)*unitsquare,rgb(.8,.8,.5));fill(shift(1,4)*unitsquare,rgb(.8,.8,.5)); fill(shift(2,3)*unitsquare,rgb(.8,.8,.5));fill(shift(2,1)*unitsquare,rgb(.8,.8,.5)); fill(shift(3,2)*unitsquare,rgb(.8,.8,.5));fill(shift(5,2)*unitsquare,rgb(.8,.8,.5)); D(arc(O,1,280,350),EndArrow(4)); D(arc(O,5^.5,-20,50),EndArrow(4)); D(arc(O,1,10,80),EndArrow(4)); D(arc(O,5^.5,70,140),EndArrow(4)); D(arc(O,1,190,260),EndArrow(4)); D(arc(O,5^.5,250,320),EndArrow(4)); D(arc(O,1,100,170),EndArrow(4)); D(arc(O,5^.5,160,230),EndArrow(4)); [/asy]          [asy]pathpen = black; pair O = (3.5,3.5); D(O); for(int i=0;i<7;++i) for(int j=0;j<7;++j) D(shift(i,j)*unitsquare); fill(shift(4,5)*unitsquare,rgb(1,1,.4)); fill(shift(2,1)*unitsquare,rgb(1,1,.4)); fill(shift(1,4)*unitsquare,rgb(.8,.8,.5)); fill(shift(5,2)*unitsquare,rgb(.8,.8,.5)); D(arc(O,5^.5,-20,50),EndArrow(4)); D(arc(O,5^.5,70,140),EndArrow(4)); D(arc(O,5^.5,250,320),EndArrow(4)); D(arc(O,5^.5,160,230),EndArrow(4)); [/asy]
For most pairs, there will be
three other equivalent boards.		For those symmetric about the center,
there is only one other.

Note that a pair of yellow squares will only yield $2$ distinct boards upon rotation iff the yellow squares are rotationally symmetric about the center square; there are $\frac{49-1}{2}=24$ such pairs. There are then ${49 \choose 2}-24$ pairs that yield $4$ distinct boards upon rotation; in other words, for each of the ${49 \choose 2}-24$ pairs, there are three other pairs that yield an equivalent board.

Thus, the number of inequivalent boards is $\frac{{49 \choose 2} - 24}{4} + \frac{24}{2} = \boxed{300}$. For a $(2n+1) \times (2n+1)$ board, this argument generalizes to $n(n+1)(2n^2+2n+1)$ inequivalent configurations.

Solution 2 (Casework)

There are 4 cases: 1. The center square is occupied, in which there are $12$ cases. 2. The center square isn't occupied and the two squares that are opposite to each other with respect to the center square, in which there are $12$ cases. 3. The center square isn't occupied and the two squares can rotate to each other with a $90^{\circ}$ rotation with each other and with respect to the center square, in which case there are $12$ cases. 4. And finally, the two squares can't rotate to each other with respect to the center square in which case there are $\dbinom{12}{2} \cdot \frac{16}{4} = 264$ cases. Add up all the values for each case to get $\boxed{300}$ as your answer.

~First

Solution 3 (Burnside’s Lemma)

Consider the group $G=\mathbb{Z}/4\mathbb{Z}$ with addition acting on set $X$, where $X$ is the set of color schemes on the checkerboard. We now apply Burnside’s Lemma. Since $\mathbb{Z}/4\mathbb{Z}=\langle r \mid r^4=1\rangle$, we only need to consider 4 cases for $g$ an element of $\mathbb{Z}/4\mathbb{Z}$.

1. $g=1$. There are clearly ${49 \choose 2}$ cases.

2. $g=r$. Since this is a $90$ degree rotation, there are no fixed points under this transformation.

3. $g=r^2$. There are $24$ cases (which can be manually checked).

4. $g=r^3$. There are no cases since this is just Case $2$ but with a $-90$ degree rotation.

Therefore, by Burnside’s Lemma there are $\frac{1176+24+0+0}{|G|}=\frac{1200}{4}=\boxed{300}$ inequivalent configurations (also known as orbits in group-theoretic terms).

See also

1996 AIME (Problems • Answer Key • Resources)
Preceded by
Problem 6 		Followed by
Problem 8
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1996_AIME_Problems/Problem_7&oldid=226120"