Difference between revisions of "2018 AMC 10A Problems/Problem 20"

(Solution 2: and Solution 3)
m (Solution 4)
 
(19 intermediate revisions by 11 users not shown)
Line 1: Line 1:
 +
{{duplicate|[[2018 AMC 12A Problems|2018 AMC 12A #15]] and [[2018 AMC 10A Problems|2018 AMC 10A #20]]}}
 +
 +
==Problem==
 +
 
A scanning code consists of a <math>7 \times 7</math> grid of squares, with some of its squares colored black and the rest colored white. There must be at least one square of each color in this grid of <math>49</math> squares. A scanning code is called <math>\textit{symmetric}</math> if its look does not change when the entire square is rotated by a multiple of <math>90 ^{\circ}</math> counterclockwise around its center, nor when it is reflected across a line joining opposite corners or a line joining midpoints of opposite sides. What is the total number of possible symmetric scanning codes?
 
A scanning code consists of a <math>7 \times 7</math> grid of squares, with some of its squares colored black and the rest colored white. There must be at least one square of each color in this grid of <math>49</math> squares. A scanning code is called <math>\textit{symmetric}</math> if its look does not change when the entire square is rotated by a multiple of <math>90 ^{\circ}</math> counterclockwise around its center, nor when it is reflected across a line joining opposite corners or a line joining midpoints of opposite sides. What is the total number of possible symmetric scanning codes?
  
 
<math>\textbf{(A)} \text{ 510} \qquad \textbf{(B)} \text{ 1022} \qquad \textbf{(C)} \text{ 8190} \qquad \textbf{(D)} \text{ 8192} \qquad \textbf{(E)} \text{ 65,534}</math>
 
<math>\textbf{(A)} \text{ 510} \qquad \textbf{(B)} \text{ 1022} \qquad \textbf{(C)} \text{ 8190} \qquad \textbf{(D)} \text{ 8192} \qquad \textbf{(E)} \text{ 65,534}</math>
 
 
==Solution 1==
 
==Solution 1==
  
 
Draw a <math>7 \times 7</math> square.
 
Draw a <math>7 \times 7</math> square.
  
<math> \begin{tabular}{|c|c|c|c|c|c|c|}
+
<cmath> \begin{tabular}{|c|c|c|c|c|c|c|}
 
\hline
 
\hline
 
K & J & H & G & H & J & K \\
 
K & J & H & G & H & J & K \\
Line 23: Line 26:
 
K & J & H & G & H & J & K \\
 
K & J & H & G & H & J & K \\
 
\hline
 
\hline
\end{tabular} </math>
+
\end{tabular} </cmath>
  
 
Start from the center and label all protruding cells symmetrically. (Note that "I" is left out of this labelling, so there are only 10 labels, not 11, as ending in K would suggest!)
 
Start from the center and label all protruding cells symmetrically. (Note that "I" is left out of this labelling, so there are only 10 labels, not 11, as ending in K would suggest!)
  
More specifically, since there are <math>4</math> given lines of symmetry (<math>2</math> diagonals, <math>1</math> vertical, <math>1</math> horizontal) and they split the plot into <math>8</math> equivalent sections, we can take just one-eighth and study it in particular. Each of these sections has <math>10</math> distinct sub-squares, whether partially or in full. So since each can be colored either white or black, we choose <math>2^{10}=1024</math> but then subtract the <math>2</math> cases where all are white or all are black. That leaves us with <math>\boxed{(B)}, 1022</math>.
+
More specifically, since there are <math>4</math> given lines of symmetry (<math>2</math> diagonals, <math>1</math> vertical, <math>1</math> horizontal) and they split the plot into <math>8</math> equivalent sections, we can take just one-eighth and study it in particular. Each of these sections has <math>10</math> distinct sub-squares, whether partially or in full. So since each can be colored either white or black, we choose <math>2^{10}=1024</math> but then subtract the <math>2</math> cases where all are white or all are black. That leaves us with <math>\fbox{\textbf{(B)} \text{ 1022}}</math>.
  
There are only ten squares we get to actually choose, and two independent choices for each, for a total of <math>2^{10} = 1024</math> codes. Two codes must be subtracted (due to the rule that there must be at least one square of each color) for an answer of <math>\fbox{\textbf{(B)} \text{ 1022}}</math>.
+
There are only ten squares we get to actually choose, and two independent choices for each, for a total of <math>2^{10} = 1024</math> codes. Two codes must be subtracted (due to the rule that there must be at least one square of each color) for an answer of <math>\fbox{\textbf{(B) }1022}</math>.
      ~Nosysnow
 
  
  
Note that this problem is very similar to the 1996 AIME Problem 7.
+
Note that this problem is very similar to the 1996 AIME Problem 7 https://artofproblemsolving.com/wiki/index.php/1996_AIME_Problems/Problem_7.
  
 
==Solution 2==
 
==Solution 2==
Line 53: Line 55:
  
 
==Solution 3==
 
==Solution 3==
This <math>7 \times 7</math> square drawn in <math>Solution 1</math> satisfies the conditions given in the problem. The number of ways of coloring it determines will solve the problem.
+
This <math>7 \times 7</math> square drawn in Solution 1 satisfies the conditions given in the problem. Calculating the number of ways of coloring it will solve the problem.
  
<math> \begin{tabular}{|c|c|c|c|c|c|c|}
+
<cmath> \begin{tabular}{|c|c|c|c|c|c|c|}
 
\hline
 
\hline
 
K & J & H & G & H & J & K \\
 
K & J & H & G & H & J & K \\
Line 71: Line 73:
 
K & J & H & G & H & J & K \\
 
K & J & H & G & H & J & K \\
 
\hline
 
\hline
\end{tabular} </math>
+
\end{tabular} </cmath>
  
 
In the grid, 10 letters are used: <math>A</math>, <math>B</math>, <math>C</math>, <math>D</math>, <math>E</math>, <math>F</math>, <math>G</math>, <math>H</math>, <math>J</math>, and <math>K</math>. Each of the letters must have its own color, either white or black. This means, for example, all <math>K</math>'s must have the same color for the grid to be symmetrical.
 
In the grid, 10 letters are used: <math>A</math>, <math>B</math>, <math>C</math>, <math>D</math>, <math>E</math>, <math>F</math>, <math>G</math>, <math>H</math>, <math>J</math>, and <math>K</math>. Each of the letters must have its own color, either white or black. This means, for example, all <math>K</math>'s must have the same color for the grid to be symmetrical.
Line 77: Line 79:
 
So there are <math>2^{10}</math> ways to color the grid, including a completely black grid and a completely white grid. Since the grid must contain at least one square with each color, the number of ways is <math>2^{10}-2=1024-2=</math> <math>\boxed{\textbf{(B) } 1022}</math>.
 
So there are <math>2^{10}</math> ways to color the grid, including a completely black grid and a completely white grid. Since the grid must contain at least one square with each color, the number of ways is <math>2^{10}-2=1024-2=</math> <math>\boxed{\textbf{(B) } 1022}</math>.
  
~OlutosinNGA
+
==Solution 4==
 +
 
 +
<cmath> \begin{tabular}{|c|c|c|c|c|c|c|}
 +
\hline
 +
T & T & T & X & T & T & T \\
 +
\hline
 +
T & T & T & Y& T & T & T \\
 +
\hline
 +
T & T & T & Z & T & T & T \\
 +
\hline
 +
X & Y & Z & W & Z & Y & X \\
 +
\hline
 +
T & T & T & Z & T & T & T \\
 +
\hline
 +
T & T & T & Y & T & T & T \\
 +
\hline
 +
T & T & T & X & T & T & T \\
 +
\hline
 +
\end{tabular} </cmath>
 +
 
 +
There are <math>3 \times 3</math> squares in the corners of this <math>7 \times 7</math> square, and there is a horizontal and vertical stripe through the middle. Because we need to have symmetry when the diagonals and midpoints of the large square is connected, we can create a table like this: (Different letters represent different color choices between black and white)
 +
 
 +
<cmath> \begin{tabular}{|c|c|c|}
 +
\hline
 +
A & B & C \\
 +
\hline
 +
B & D & E \\
 +
\hline
 +
C & E & F \\
 +
\hline
 +
\end{tabular}</cmath>
 +
(Note that coloring one <math>3 \times 3</math> square will also determine the colorings of the other <math>3</math> because the large <math>7 \times 7</math> square must look the same when it is rotated by <math>90^\circ</math>)
 +
 
 +
There are <math>6</math> different letters and <math>2</math> choices of color (black and white) for each letter, so there are <math>2^6=64</math> colorings of a proper <math>3 \times 3</math> square. Now, all that's left are the horizontal and vertical stripes. Using similar logic, we can see that there are <math>4</math> different letters, so there are <math>2^4=16</math> different colorings. Multiplying them together gives <math>16 \times 64 = 1024</math>. Going back to the question, we see that "there must be at least one square of each color in this grid of <math>49</math> squares." We must then eliminate <math>2</math> options: an all-black grid and an all-white grid. <math>1024-2= \boxed{\textbf{(B)} 1022} \\ \phantom{}</math>
 +
-hansenhe
 +
 
 +
==Video Solution==
 +
https://youtu.be/M22S82Am2zM
 +
 
  
 
== See Also ==
 
== See Also ==
  
 
{{AMC10 box|year=2018|ab=A|num-b=19|num-a=21}}
 
{{AMC10 box|year=2018|ab=A|num-b=19|num-a=21}}
{{AMC12 box|year=2018|ab=|num-b=14|num-a=16}}
+
{{AMC12 box|year=2018|ab=A|num-b=14|num-a=16}}
 
{{MAA Notice}}
 
{{MAA Notice}}
  
 
[[Category:Intermediate Combinatorics Problems]]
 
[[Category:Intermediate Combinatorics Problems]]

Latest revision as of 22:48, 2 August 2021

The following problem is from both the 2018 AMC 12A #15 and 2018 AMC 10A #20, so both problems redirect to this page.

Problem

A scanning code consists of a $7 \times 7$ grid of squares, with some of its squares colored black and the rest colored white. There must be at least one square of each color in this grid of $49$ squares. A scanning code is called $\textit{symmetric}$ if its look does not change when the entire square is rotated by a multiple of $90 ^{\circ}$ counterclockwise around its center, nor when it is reflected across a line joining opposite corners or a line joining midpoints of opposite sides. What is the total number of possible symmetric scanning codes?

$\textbf{(A)} \text{ 510} \qquad \textbf{(B)} \text{ 1022} \qquad \textbf{(C)} \text{ 8190} \qquad \textbf{(D)} \text{ 8192} \qquad \textbf{(E)} \text{ 65,534}$

Solution 1

Draw a $7 \times 7$ square.

\[\begin{tabular}{|c|c|c|c|c|c|c|} \hline K & J & H & G & H & J & K \\ \hline J & F & E & D & E & F & J \\ \hline H & E & C & B & C & E & H \\ \hline G & D & B & A & B & D & G \\ \hline H & E & C & B & C & E & H \\ \hline J & F & E & D & E & F & J \\ \hline K & J & H & G & H & J & K \\ \hline \end{tabular}\]

Start from the center and label all protruding cells symmetrically. (Note that "I" is left out of this labelling, so there are only 10 labels, not 11, as ending in K would suggest!)

More specifically, since there are $4$ given lines of symmetry ($2$ diagonals, $1$ vertical, $1$ horizontal) and they split the plot into $8$ equivalent sections, we can take just one-eighth and study it in particular. Each of these sections has $10$ distinct sub-squares, whether partially or in full. So since each can be colored either white or black, we choose $2^{10}=1024$ but then subtract the $2$ cases where all are white or all are black. That leaves us with $\fbox{\textbf{(B)} \text{ 1022}}$.

There are only ten squares we get to actually choose, and two independent choices for each, for a total of $2^{10} = 1024$ codes. Two codes must be subtracted (due to the rule that there must be at least one square of each color) for an answer of $\fbox{\textbf{(B) }1022}$.


Note that this problem is very similar to the 1996 AIME Problem 7 https://artofproblemsolving.com/wiki/index.php/1996_AIME_Problems/Problem_7.

Solution 2

[asy] size(100pt); draw((1,0)--(8,0),linewidth(0.5)); draw((1,2)--(6,2),linewidth(0.5)); draw((1,4)--(4,4),linewidth(0.5)); draw((1,6)--(2,6),linewidth(0.5)); draw((2,6)--(2,0),linewidth(0.5)); draw((4,4)--(4,0),linewidth(0.5)); draw((6,2)--(6,0),linewidth(0.5)); draw((1,0)--(1,7),dashed+linewidth(0.5)); draw((1,7)--(8,0),dashed+linewidth(0.5)); [/asy]

Imagine folding the scanning code along its lines of symmetry. There will be $10$ regions which you have control over coloring. Since we must subtract off $2$ cases for the all-black and all-white cases, the answer is $2^{10}-2=\boxed{\textbf{(B) } 1022.}$

Solution 3

This $7 \times 7$ square drawn in Solution 1 satisfies the conditions given in the problem. Calculating the number of ways of coloring it will solve the problem.

\[\begin{tabular}{|c|c|c|c|c|c|c|} \hline K & J & H & G & H & J & K \\ \hline J & F & E & D & E & F & J \\ \hline H & E & C & B & C & E & H \\ \hline G & D & B & A & B & D & G \\ \hline H & E & C & B & C & E & H \\ \hline J & F & E & D & E & F & J \\ \hline K & J & H & G & H & J & K \\ \hline \end{tabular}\]

In the grid, 10 letters are used: $A$, $B$, $C$, $D$, $E$, $F$, $G$, $H$, $J$, and $K$. Each of the letters must have its own color, either white or black. This means, for example, all $K$'s must have the same color for the grid to be symmetrical.

So there are $2^{10}$ ways to color the grid, including a completely black grid and a completely white grid. Since the grid must contain at least one square with each color, the number of ways is $2^{10}-2=1024-2=$ $\boxed{\textbf{(B) } 1022}$.

Solution 4

\[\begin{tabular}{|c|c|c|c|c|c|c|} \hline T & T & T & X & T & T & T \\ \hline T & T & T & Y& T & T & T \\ \hline T & T & T & Z & T & T & T \\ \hline X & Y & Z & W & Z & Y & X \\ \hline T & T & T & Z & T & T & T \\ \hline T & T & T & Y & T & T & T \\ \hline T & T & T & X & T & T & T \\ \hline \end{tabular}\]

There are $3 \times 3$ squares in the corners of this $7 \times 7$ square, and there is a horizontal and vertical stripe through the middle. Because we need to have symmetry when the diagonals and midpoints of the large square is connected, we can create a table like this: (Different letters represent different color choices between black and white)

\[\begin{tabular}{|c|c|c|} \hline A & B & C \\ \hline B & D & E \\ \hline C & E & F \\ \hline \end{tabular}\] (Note that coloring one $3 \times 3$ square will also determine the colorings of the other $3$ because the large $7 \times 7$ square must look the same when it is rotated by $90^\circ$)

There are $6$ different letters and $2$ choices of color (black and white) for each letter, so there are $2^6=64$ colorings of a proper $3 \times 3$ square. Now, all that's left are the horizontal and vertical stripes. Using similar logic, we can see that there are $4$ different letters, so there are $2^4=16$ different colorings. Multiplying them together gives $16 \times 64 = 1024$. Going back to the question, we see that "there must be at least one square of each color in this grid of $49$ squares." We must then eliminate $2$ options: an all-black grid and an all-white grid. $1024-2= \boxed{\textbf{(B)} 1022} \\ \phantom{}$ -hansenhe

Video Solution

https://youtu.be/M22S82Am2zM


See Also

2018 AMC 10A (ProblemsAnswer KeyResources)
Preceded by
Problem 19
Followed by
Problem 21
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 10 Problems and Solutions
2018 AMC 12A (ProblemsAnswer KeyResources)
Preceded by
Problem 14
Followed by
Problem 16
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

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

Invalid username
Login to AoPS