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 "2022 AMC 10B Problems/Problem 19"
 
(25 intermediate revisions by 9 users not shown)
Line 1: Line 1:
−
Each square in a <math>5 \times 5</math> grid is either filled or empty, and has up to eight adjacent neighboring squares, where neighboring squares share either a side or a corner. The grid is transformed by the following rules: Any filled square with two or three filled neighbors remains filled. Any empty square with exactly three filled neighbors becomes a filled square. All other squares remain empty or become empty. A sample transformation is shown in the figure below.
+
{{duplicate|[[2022 AMC 10B Problems/Problem 19|2022 AMC 10B #19]] and [[2022 AMC 12B Problems/Problem 18|2022 AMC 12B #18]]}}
  
−
<asy>        import geometry;        unitsize(0.6cm);         void ds(pair x) {            filldraw(x -- (1,0) + x -- (1,1) + x -- (0,1)+x -- cycle,gray+opacity(0.5),invisible);        }         ds((1,1));        ds((2,1));        ds((3,1));        ds((1,3));         for (int i = 0; i <= 5; ++i) {            draw((0,i)--(5,i));            draw((i,0)--(i,5));        }         label("Initial", (2.5,-1));        draw((6,2.5)--(8,2.5),Arrow);         ds((10,2));        ds((11,1));        ds((11,0));         for (int i = 0; i <= 5; ++i) {            draw((9,i)--(14,i));            draw((i+9,0)--(i+9,5));        }         label("Transformed", (11.5,-1)); </asy>
+
== Problem ==
−
Suppose the <math>5 \times 5</math> grid has a border of empty squares surrounding a <math>3 \times 3</math> subgrid. How many initial configurations will lead to a transformed grid consisting of a single filled square in the center after a single transformation? (Rotations and reflections of the same configuration are considered different.)<asy>        import geometry;        unitsize(0.6cm);         void ds(pair x) {            filldraw(x -- (1,0) + x -- (1,1) + x -- (0,1)+x -- cycle,gray+opacity(0.5),invisible);        }         for (int i = 1; i < 4; ++ i) {            for (int j = 1; j < 4; ++j) {                label("?",(i + 0.5, j + 0.5));            }        }         for (int i = 0; i <= 5; ++i) {            draw((0,i)--(5,i));            draw((i,0)--(i,5));        }         label("Initial", (2.5,-1));        draw((6,2.5)--(8,2.5),Arrow);         ds((11,2));         for (int i = 0; i <= 5; ++i) {            draw((9,i)--(14,i));            draw((i+9,0)--(i+9,5));        }         label("Transformed", (11.5,-1)); </asy>
+
Each square in a <math>5 \times 5</math> grid is either filled or empty, and has up to eight adjacent neighboring squares, where neighboring squares share either a side or a corner. The grid is transformed by the following rules:
 +
 
 +
* Any filled square with two or three filled neighbors remains filled.
 +
 
 +
* Any empty square with exactly three filled neighbors becomes a filled square.
 +
 
 +
* All other squares remain empty or become empty.
 +
 
 +
A sample transformation is shown in the figure below.
 +
<asy>
 +
         import geometry;
 +
         unitsize(0.6cm);
 +
 
 +
        void ds(pair x) {
 +
             filldraw(x -- (1,0) + x -- (1,1) + x -- (0,1)+x -- cycle,mediumgray,invisible);
 +
         }
 +
 
 +
        ds((1,1));
 +
         ds((2,1));
 +
         ds((3,1));
 +
         ds((1,3));
 +
 
 +
        for (int i = 0; i <= 5; ++i) {
 +
             draw((0,i)--(5,i));
 +
             draw((i,0)--(i,5));
 +
         }
 +
 
 +
        label("Initial", (2.5,-1));
 +
         draw((6,2.5)--(8,2.5),Arrow);
 +
 
 +
        ds((10,2));
 +
         ds((11,1));
 +
         ds((11,0));
 +
 
 +
        for (int i = 0; i <= 5; ++i) {
 +
             draw((9,i)--(14,i));
 +
             draw((i+9,0)--(i+9,5));
 +
         }
 +
 
 +
        label("Transformed", (11.5,-1));
 +
</asy>
 +
Suppose the <math>5 \times 5</math> grid has a border of empty squares surrounding a <math>3 \times 3</math> subgrid. How many initial configurations will lead to a transformed grid consisting of a single filled square in the center after a single transformation? (Rotations and reflections of the same configuration are considered different.)
 +
<asy>
 +
         import geometry;
 +
         unitsize(0.6cm);
 +
 
 +
        void ds(pair x) {
 +
             filldraw(x -- (1,0) + x -- (1,1) + x -- (0,1)+x -- cycle,mediumgray,invisible);
 +
         }
 +
 
 +
        for (int i = 1; i < 4; ++ i) {
 +
             for (int j = 1; j < 4; ++j) {
 +
                 label("?",(i + 0.5, j + 0.5));
 +
             }
 +
         }
 +
 
 +
        for (int i = 0; i <= 5; ++i) {
 +
             draw((0,i)--(5,i));
 +
             draw((i,0)--(i,5));
 +
         }
 +
 
 +
        label("Initial", (2.5,-1));
 +
         draw((6,2.5)--(8,2.5),Arrow);
 +
 
 +
        ds((11,2));
 +
 
 +
        for (int i = 0; i <= 5; ++i) {
 +
             draw((9,i)--(14,i));
 +
             draw((i+9,0)--(i+9,5));
 +
         }
 +
 
 +
        label("Transformed", (11.5,-1));
 +
</asy>
 
<math>\textbf{(A)}\ 14 \qquad\textbf{(B)}\ 18 \qquad\textbf{(C)}\ 22 \qquad\textbf{(D)}\ 26 \qquad\textbf{(E)}\ 30</math>
 
<math>\textbf{(A)}\ 14 \qquad\textbf{(B)}\ 18 \qquad\textbf{(C)}\ 22 \qquad\textbf{(D)}\ 26 \qquad\textbf{(E)}\ 30</math>
  
 
==Solution==
 
==Solution==
−
There are two cases:
+
There are two cases for the initial configuration:
−
<math>\textbf{Case 1:} The center is filled in the initial configuration
+
<ol style="margin-left: 1.5em;">
−
In this case, one or two more squares must be filled in the initial configuration. It is easy to show that the only configuration that results in additional squares for the next turn is the configuration with all squares along the diagonal. This case yields </math>2<math> possibilities.
+
  <li>The center square is filled. </li><p>
−
</math>\textbf{Case 2:} The center is not filled
+
Exactly two of the eight adjacent neighboring squares of the center are filled. Clearly, the only possibility is that the squares along one diagonal are filled, as shown below:<p>
−
In this case, exactly three squares outside the center must be filled. Additionally, these three squares must all be adjacent to only one square, the center square.
+
<asy>
−
<math>\textbf{Subcase 1:} A corner is filled
+
import geometry;
−
In this case, it can be shown that there are </math>3<math> possibilities (excluding rotations and reflections). Two of them yield four cases, one yields eight, for a total of </math>16<math>.
+
unitsize(0.6cm);
−
</math>\textbf{Subcase 2:} No corners are filled
+
 
−
In this case, there is only one way to do it (excluding rotations and reflections). There are a total of four ways to rotate this permutation, so this case has a count of <math>4</math>.
+
void ds(pair x) {
−
Our final answer is thus $2 + 16 + 4 = \boxed{\textbf{(C)}\ 22}
+
filldraw(x -- (1,0) + x -- (1,1) + x -- (0,1)+x -- cycle,mediumgray,invisible);
−
~mathboy100
+
}
 +
 
 +
ds((1,3));
 +
ds((2,2));
 +
ds((3,1));
 +
 
 +
for (int i = 0; i <= 5; ++i) {
 +
draw((0,i)--(5,i));
 +
    draw((i,0)--(i,5));
 +
    }
 +
 
 +
label("$2$ Configurations", (2.5,-1));
 +
</asy>
 +
In this case, there are <math>2</math> possible initial configurations. All rotations and reflections are considered.<p>
 +
  <li>The center square is empty.</li><p>
 +
Exactly three of the eight adjacent neighboring squares of the center are filled. The possibilities are shown below:<p>
 +
<asy>
 +
import geometry;
 +
unitsize(0.6cm);
 +
 
 +
void ds(pair x) {
 +
filldraw(x -- (1,0) + x -- (1,1) + x -- (0,1)+x -- cycle,mediumgray,invisible);
 +
}
 +
 
 +
ds((1,3));
 +
ds((3,3));
 +
ds((1,1));
 +
 
 +
for (int i = 0; i <= 5; ++i) {
 +
draw((0,i)--(5,i));
 +
    draw((i,0)--(i,5));
 +
    }
 +
 
 +
ds((10,3));
 +
ds((12,3));
 +
ds((11,1));
 +
 
 +
for (int i = 0; i <= 5; ++i) {
 +
    draw((9,i)--(14,i));
 +
    draw((i+9,0)--(i+9,5));
 +
    }
 +
 
 +
ds((19,3));
 +
ds((20,1));
 +
ds((21,2));
 +
 
 +
for (int i = 0; i <= 5; ++i) {
 +
    draw((18,i)--(23,i));
 +
    draw((i+18,0)--(i+18,5));
 +
    }
 +
 
 +
ds((28,3));
 +
ds((29,1));
 +
ds((30,1));
 +
 
 +
for (int i = 0; i <= 5; ++i) {
 +
    draw((27,i)--(32,i));
 +
    draw((i+27,0)--(i+27,5));
 +
    }
 +
   
 +
label("$4$ Configurations", (2.5,-1));
 +
label("$4$ Configurations", (11.5,-1));
 +
label("$4$ Configurations", (20.5,-1));
 +
label("$8$ Configurations", (29.5,-1));
 +
</asy>
 +
In this case, there are <math>4+4+4+8=20</math> possible initial configurations. All rotations and reflections are considered.<p>
 +
</ol>
 +
Together, the answer is <math>2+20=\boxed{\textbf{(C)}\ 22}.</math>
 +
 
 +
~mathboy100 ~MRENTHUSIASM
 +
 
 +
== Video Solution by OmegaLearn (Using Logic and Casework) ==
 +
https://youtu.be/UYTiP3u5qE4
 +
 
 +
~ pi_is_3.14
 +
 
 +
== Video Solution==
 +
 
 +
https://youtu.be/CL_xjeRR02U
 +
 
 +
~MathProblemSolvingSkills.com
 +
 
 +
==Video Solution==
 +
https://youtu.be/JVDlHCSPF6k
 +
 
 +
~Hayabusa1
 +
==Video Solution by Interstigation==
 +
https://youtu.be/gsaD0wQPVgY
 +
 
 +
~Interstigation
 +
 
 +
== See Also ==
 +
 
 +
{{AMC10 box|year=2022|ab=B|num-b=18|num-a=20}}
 +
{{AMC12 box|year=2022|ab=B|num-b=17|num-a=19}}
 +
{{MAA Notice}}

Latest revision as of 02:22, 7 July 2023

The following problem is from both the 2022 AMC 10B #19 and 2022 AMC 12B #18, so both problems redirect to this page.

Problem

Each square in a $5 \times 5$ grid is either filled or empty, and has up to eight adjacent neighboring squares, where neighboring squares share either a side or a corner. The grid is transformed by the following rules:

  • Any filled square with two or three filled neighbors remains filled.
  • Any empty square with exactly three filled neighbors becomes a filled square.
  • All other squares remain empty or become empty.

A sample transformation is shown in the figure below. [asy] import geometry; unitsize(0.6cm); void ds(pair x) { filldraw(x -- (1,0) + x -- (1,1) + x -- (0,1)+x -- cycle,mediumgray,invisible); } ds((1,1)); ds((2,1)); ds((3,1)); ds((1,3)); for (int i = 0; i <= 5; ++i) { draw((0,i)--(5,i)); draw((i,0)--(i,5)); } label("Initial", (2.5,-1)); draw((6,2.5)--(8,2.5),Arrow); ds((10,2)); ds((11,1)); ds((11,0)); for (int i = 0; i <= 5; ++i) { draw((9,i)--(14,i)); draw((i+9,0)--(i+9,5)); } label("Transformed", (11.5,-1)); [/asy] Suppose the $5 \times 5$ grid has a border of empty squares surrounding a $3 \times 3$ subgrid. How many initial configurations will lead to a transformed grid consisting of a single filled square in the center after a single transformation? (Rotations and reflections of the same configuration are considered different.) [asy] import geometry; unitsize(0.6cm); void ds(pair x) { filldraw(x -- (1,0) + x -- (1,1) + x -- (0,1)+x -- cycle,mediumgray,invisible); } for (int i = 1; i < 4; ++ i) { for (int j = 1; j < 4; ++j) { label("?",(i + 0.5, j + 0.5)); } } for (int i = 0; i <= 5; ++i) { draw((0,i)--(5,i)); draw((i,0)--(i,5)); } label("Initial", (2.5,-1)); draw((6,2.5)--(8,2.5),Arrow); ds((11,2)); for (int i = 0; i <= 5; ++i) { draw((9,i)--(14,i)); draw((i+9,0)--(i+9,5)); } label("Transformed", (11.5,-1)); [/asy] $\textbf{(A)}\ 14 \qquad\textbf{(B)}\ 18 \qquad\textbf{(C)}\ 22 \qquad\textbf{(D)}\ 26 \qquad\textbf{(E)}\ 30$

Solution

There are two cases for the initial configuration:

  1. The center square is filled.

    2. Exactly two of the eight adjacent neighboring squares of the center are filled. Clearly, the only possibility is that the squares along one diagonal are filled, as shown below:

    [asy] import geometry; unitsize(0.6cm); void ds(pair x) { filldraw(x -- (1,0) + x -- (1,1) + x -- (0,1)+x -- cycle,mediumgray,invisible); } ds((1,3)); ds((2,2)); ds((3,1)); for (int i = 0; i <= 5; ++i) { draw((0,i)--(5,i)); draw((i,0)--(i,5)); } label("$2$ Configurations", (2.5,-1)); [/asy] In this case, there are $2$ possible initial configurations. All rotations and reflections are considered.

  2. The center square is empty.

    3. Exactly three of the eight adjacent neighboring squares of the center are filled. The possibilities are shown below:

    [asy] import geometry; unitsize(0.6cm); void ds(pair x) { filldraw(x -- (1,0) + x -- (1,1) + x -- (0,1)+x -- cycle,mediumgray,invisible); } ds((1,3)); ds((3,3)); ds((1,1)); for (int i = 0; i <= 5; ++i) { draw((0,i)--(5,i)); draw((i,0)--(i,5)); } ds((10,3)); ds((12,3)); ds((11,1)); for (int i = 0; i <= 5; ++i) { draw((9,i)--(14,i)); draw((i+9,0)--(i+9,5)); } ds((19,3)); ds((20,1)); ds((21,2)); for (int i = 0; i <= 5; ++i) { draw((18,i)--(23,i)); draw((i+18,0)--(i+18,5)); } ds((28,3)); ds((29,1)); ds((30,1)); for (int i = 0; i <= 5; ++i) { draw((27,i)--(32,i)); draw((i+27,0)--(i+27,5)); } label("$4$ Configurations", (2.5,-1)); label("$4$ Configurations", (11.5,-1)); label("$4$ Configurations", (20.5,-1)); label("$8$ Configurations", (29.5,-1)); [/asy] In this case, there are $4+4+4+8=20$ possible initial configurations. All rotations and reflections are considered.

Together, the answer is $2+20=\boxed{\textbf{(C)}\ 22}.$

~mathboy100 ~MRENTHUSIASM

Video Solution by OmegaLearn (Using Logic and Casework)

https://youtu.be/UYTiP3u5qE4

~ pi_is_3.14

Video Solution

https://youtu.be/CL_xjeRR02U

~MathProblemSolvingSkills.com

Video Solution

https://youtu.be/JVDlHCSPF6k

~Hayabusa1

Video Solution by Interstigation

https://youtu.be/gsaD0wQPVgY

~Interstigation

See Also

2022 AMC 10B (Problems • Answer Key • Resources)
Preceded by
Problem 18 		Followed by
Problem 20
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
2022 AMC 12B (Problems • Answer Key • Resources)
Preceded by
Problem 17 		Followed by
Problem 19
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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2022_AMC_10B_Problems/Problem_19&oldid=195368"