Difference between revisions of "1996 AIME Problems/Problem 7"

Revision as of 12:52, 13 August 2008

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

There are ${49 \choose 2}$ possible ways to select two squares to be painted green. There are four possible ways to rotate each board. Given an arbitrary pair of green 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(.4,.8,.4));fill(shift(4,5)*unitsquare,rgb(.4,.8,.4)); fill(shift(3,4)*unitsquare,rgb(.7,1,.7));fill(shift(1,4)*unitsquare,rgb(.7,1,.7)); fill(shift(2,3)*unitsquare,rgb(.7,1,.7));fill(shift(2,1)*unitsquare,rgb(.7,1,.7)); fill(shift(3,2)*unitsquare,rgb(.7,1,.7));fill(shift(5,2)*unitsquare,rgb(.7,1,.7)); 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(.4,.8,.4)); fill(shift(2,1)*unitsquare,rgb(.4,.8,.4)); fill(shift(1,4)*unitsquare,rgb(.7,1,.7)); fill(shift(5,2)*unitsquare,rgb(.7,1,.7)); 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 green squares will only yield $2$ distinct boards upon rotation iff the green 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.

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

Page

Toolbox

Search

Difference between revisions of "1996 AIME Problems/Problem 7"

Revision as of 12:52, 13 August 2008

Problem

Solution

See also

@@ Line 1: / Line 1: @@
 == 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}}
+There are <math>{49 \choose 2}</math> possible ways to select two squares to be painted green. There are four possible ways to rotate each board. Given an arbitrary pair of green 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(.4,.8,.4));fill(shift(4,5)*unitsquare,rgb(.4,.8,.4));
+fill(shift(3,4)*unitsquare,rgb(.7,1,.7));fill(shift(1,4)*unitsquare,rgb(.7,1,.7));
+fill(shift(2,3)*unitsquare,rgb(.7,1,.7));fill(shift(2,1)*unitsquare,rgb(.7,1,.7));
+fill(shift(3,2)*unitsquare,rgb(.7,1,.7));fill(shift(5,2)*unitsquare,rgb(.7,1,.7));
+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(.4,.8,.4));
+fill(shift(2,1)*unitsquare,rgb(.4,.8,.4));
+fill(shift(1,4)*unitsquare,rgb(.7,1,.7));
+fill(shift(5,2)*unitsquare,rgb(.7,1,.7));
+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 green squares will only yield <math>2</math> distinct boards upon rotation [[iff]] the green 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.
 == See also ==
-*[[1996 AIME Problems]]
+{{AIME box|year=1996|num-b=6|num-a=8}}
-{{AIME box|year=1996|num-b=6|num-a=8}}
+[[Category:Intermediate Combinatorics Problems]]