Difference between revisions of "2020 AMC 8 Problems/Problem 21"

(Solution 2)
(Video Solution by North America Math Contest Go Go Go)
(38 intermediate revisions by 18 users not shown)
Line 1: Line 1:
==Problem 21==
+
==Problem==
 
A game board consists of <math>64</math> squares that alternate in color between black and white. The figure below shows square <math>P</math> in the bottom row and square <math>Q</math> in the top row. A marker is placed at <math>P.</math> A step consists of moving the marker onto one of the adjoining white squares in the row above. How many <math>7</math>-step paths are there from <math>P</math> to <math>Q?</math> (The figure shows a sample path.)
 
A game board consists of <math>64</math> squares that alternate in color between black and white. The figure below shows square <math>P</math> in the bottom row and square <math>Q</math> in the top row. A marker is placed at <math>P.</math> A step consists of moving the marker onto one of the adjoining white squares in the row above. How many <math>7</math>-step paths are there from <math>P</math> to <math>Q?</math> (The figure shows a sample path.)
  
Line 7: Line 7:
 
<math>\textbf{(A) }28 \qquad \textbf{(B) }30 \qquad \textbf{(C) }32 \qquad \textbf{(D) }33 \qquad \textbf{(E) }35</math>
 
<math>\textbf{(A) }28 \qquad \textbf{(B) }30 \qquad \textbf{(C) }32 \qquad \textbf{(D) }33 \qquad \textbf{(E) }35</math>
  
 +
==Solution 1==
 +
Notice that, in order to step onto any particular white square, the marker must have come from one of the <math>1</math> or <math>2</math> white squares immediately beneath it (since the marker can only move on white squares). This means that the number of ways to move from <math>P</math> to that square is the sum of the numbers of ways to move from <math>P</math> to each of the white squares immediately beneath it. To solve the problem, we can accordingly construct the following diagram, where each number in a square is calculated as the sum of the numbers on the white squares immediately beneath that square (and thus will represent the number of ways to remove from <math>P</math> to that square, as already stated).
  
==Solution==
 
We count paths. Noticing that we can only go along white squares, to get to a white square we can only go from the two whites beneath it. Here is a diagram:
 
 
<asy>
 
<asy>
 
int N = 7;
 
int N = 7;
Line 38: Line 38:
 
label("$28$", (6.5, 7.5));
 
label("$28$", (6.5, 7.5));
 
</asy>
 
</asy>
So the answer is <math>\boxed{\textbf{(A)}28}</math>
+
 
~yofro (Diagram credits to franzliszt)
+
The answer is therefore <math>\boxed{\textbf{(A) }28}</math>.
  
 
==Solution 2==
 
==Solution 2==
Suppose we "extend" the chessboard indefinitely to the right:
+
Suppose we "extend" the chessboard infinitely with <math>2</math> additional columns to the right, as shown below. The red line shows the right-hand edge of the original board.
  
 
<asy>
 
<asy>
Line 60: Line 60:
 
label("$Y$", (8.5,5.5));
 
label("$Y$", (8.5,5.5));
 
</asy>
 
</asy>
The total number of paths from <math>P</math> to <math>Q</math> (including invalid paths which cross over the red line) is <math>\binom{7}{3} = 35</math>. We subtract the number of invalid paths that pass through <math>X</math> or <math>Y</math>. The number of paths that pass through <math>X</math> is <math>\binom{3}{0}\binom{4}{3} = 4</math> and the number of paths that pass through <math>Y</math> is <math>\binom{5}{1}\binom{2}{2} = 5</math>. However, we overcounted the invalid paths which pass through both <math>X</math> and <math>Y</math>, of which there are 2 paths. Hence, the number of invalid paths is <math>4+5-2=7</math> and the number of valid paths from <math>P</math> to <math>Q</math> is <math>35-7 = \boxed{\textbf{(A)} 28}</math>. -scrabbler94
+
 
 +
The total number of paths from <math>P</math> to <math>Q</math>, including invalid paths which cross over the red line, is then the number of paths which make <math>4</math> steps up-and-right and <math>3</math> steps up-and-left, which is <math>\binom{4+3}{3} = \binom{7}{3} = 35</math>. We need to subtract the number of invalid paths, i.e. the number of paths that pass through <math>X</math> or <math>Y</math>. To get to <math>X</math>, the marker has to make <math>3</math> up-and-right steps, after which it can proceed to <math>Q</math> with <math>3</math> steps up-and-left and <math>1</math> step up-and-right. Thus, the number of paths from <math>P</math> to <math>Q</math> that pass through <math>X</math> is <math>1 \cdot \binom{3+1}{3} = 4</math>. Similarly, the number of paths that pass through <math>Y</math> is <math>\binom{4+1}{1}\cdot 1 = 5</math>. However, we have now double-counted the invalid paths which pass through both <math>X</math> and <math>Y</math>; from the diagram, it is clear that there are only <math>2</math> of these (as the marker can get from <math>X</math> to <math>Y</math> by a step up-and-left and a step-up-and-right in either order). Hence the number of invalid paths is <math>4+5-2=7</math>, and the number of valid paths from <math>P</math> to <math>Q</math> is <math>35-7 = \boxed{\textbf{(A) }28}</math>.
  
 
==Solution 3==
 
==Solution 3==
 +
On any white square, we may choose to go left or right, as long as we do not cross over the border of the board. Call the moves <math>L</math> and <math>R</math> respectively. Every single legal path consists of <math>4</math> <math>R's</math> and <math>3</math> <math>L's</math>, so now all we have to find is the number of ways to order <math>4 R's</math> and <math>3 L's</math> in any way, which is <math>{7 \choose 3}=35</math>. However, we originally promised that we will not go over the border, and now we have to subtract the paths that do go over the border. The paths that go over the border are any paths that start with RRR(1 path), RR(5 paths) and LRRR(1 path) so our final number of paths is <math>35-7=\boxed{(A)=28}.</math>
 +
~PEKKA
 +
 +
==Solution 4: Intuitive Approach==
 +
 +
We label the rows starting from the bottom. At row 1, there is <math>1</math> way: at P. We draw all the possible ways to get to Q. There are two ways to choose for row 2, and another two ways to choose for row 3. However, you can go to the "edge" or the farthest possible square westward of Q, so you can't multiply by 2 again. Notice how, at the first step, we figured that the answer was even, so choice D and E are eliminated, and after the second row, we realized it must be a multiple of 4, so choice B is eliminated. When we get to the fourth row, we do not multiply by 2 again, since we have limited possibilities rather than multiplying by 2 again. Choice C implies that there are two possibilities per row; however, we know that if you go to the farthest possible, you only have one possibility, so it is not <math>2^5 = 32</math> so we know that the answer is choice <math>\boxed{\textbf{(A)}}</math>.
 +
~hh99754539
  
The easiest way to solve this problem is just writing out the steps to get to each square as follows:
 
  
<asy>
 
size(200);
 
int N = 7;
 
for (int i = 0; i < 8; ++i) {
 
for (int j = 0; j < 8; ++j) {
 
draw((i,j)--(i+1,j)--(i+1,j+1)--(i,j+1)--(i,j));
 
if ((i+j) % 2 == 0) {
 
filldraw((i,j)--(i+1,j)--(i+1,j+1)--(i,j+1)--(i,j)--cycle,black);
 
}
 
}
 
}
 
label("$1$", (5.5, .5));
 
label("$1$", (4.5, 1.5));
 
label("$1$", (6.5, 1.5));
 
label("$1$", (3.5, 2.5));
 
label("$1$", (7.5, 2.5));
 
label("$2$", (5.5, 2.5));
 
label("$1$", (2.5, 3.5));
 
label("$3$", (6.5, 3.5));
 
label("$3$", (4.5, 3.5));
 
label("$4$", (3.5, 4.5));
 
label("$3$", (7.5, 4.5));
 
label("$6$", (5.5, 4.5));
 
label("$10$", (4.5, 5.5));
 
label("$9$", (6.5, 5.5));
 
label("$19$", (5.5, 6.5));
 
label("$9$", (7.5, 6.5));
 
label("$28$", (6.5, 7.5));
 
</asy>
 
  
The answer is thus <math>\textbf{(A) }28</math>. Interestingly, the final answer is also <math>\binom 82...</math>
+
==Video Solution by MathisCool==
 +
 
 +
https://www.youtube.com/watch?v=LvpCYn8Ze6c
 +
 
 +
 
 +
==Video Solution by North America Math Contest Go Go Go==
 +
 
 +
https://www.youtube.com/watch?v=rWxhlItMAN0
 +
 
 +
~North America Math Contest Go Go Go
 +
 
 +
==Video Solution by WhyMath==
 +
https://youtu.be/YR3oghbziBA
 +
 
 +
~savannahsolver
 +
 
 +
==Video Solutions==
 +
https://youtu.be/hGCxt8G9g-s
 +
 
 +
==Video Solution by Interstigation==
 +
https://youtu.be/YnwkBZTv5Fw?t=1247
  
-franzliszt
+
~Interstigation
  
==See also==  
+
==See also==
 
{{AMC8 box|year=2020|num-b=20|num-a=22}}
 
{{AMC8 box|year=2020|num-b=20|num-a=22}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 19:17, 30 January 2022

Problem

A game board consists of $64$ squares that alternate in color between black and white. The figure below shows square $P$ in the bottom row and square $Q$ in the top row. A marker is placed at $P.$ A step consists of moving the marker onto one of the adjoining white squares in the row above. How many $7$-step paths are there from $P$ to $Q?$ (The figure shows a sample path.)

[asy]//diagram by SirCalcsALot size(200); int[] x = {6, 5, 4, 5, 6, 5, 6}; int[] y = {1, 2, 3, 4, 5, 6, 7}; int N = 7; for (int i = 0; i < 8; ++i) { for (int j = 0; j < 8; ++j) { draw((i,j)--(i+1,j)--(i+1,j+1)--(i,j+1)--(i,j)); if ((i+j) % 2 == 0) { filldraw((i,j)--(i+1,j)--(i+1,j+1)--(i,j+1)--(i,j)--cycle,black); } } } for (int i = 0; i < N; ++i) { draw(circle((x[i],y[i])+(0.5,0.5),0.35)); } label("$P$", (5.5, 0.5)); label("$Q$", (6.5, 7.5)); [/asy]

$\textbf{(A) }28 \qquad \textbf{(B) }30 \qquad \textbf{(C) }32 \qquad \textbf{(D) }33 \qquad \textbf{(E) }35$

Solution 1

Notice that, in order to step onto any particular white square, the marker must have come from one of the $1$ or $2$ white squares immediately beneath it (since the marker can only move on white squares). This means that the number of ways to move from $P$ to that square is the sum of the numbers of ways to move from $P$ to each of the white squares immediately beneath it. To solve the problem, we can accordingly construct the following diagram, where each number in a square is calculated as the sum of the numbers on the white squares immediately beneath that square (and thus will represent the number of ways to remove from $P$ to that square, as already stated).

[asy] int N = 7; for (int i = 0; i < 8; ++i) { for (int j = 0; j < 8; ++j) { draw((i,j)--(i+1,j)--(i+1,j+1)--(i,j+1)--(i,j)); if ((i+j) % 2 == 0) { filldraw((i,j)--(i+1,j)--(i+1,j+1)--(i,j+1)--(i,j)--cycle,black); } } } label("$1$", (5.5, .5)); label("$1$", (4.5, 1.5)); label("$1$", (6.5, 1.5)); label("$1$", (3.5, 2.5)); label("$1$", (7.5, 2.5)); label("$2$", (5.5, 2.5)); label("$1$", (2.5, 3.5)); label("$3$", (6.5, 3.5)); label("$3$", (4.5, 3.5)); label("$4$", (3.5, 4.5)); label("$3$", (7.5, 4.5)); label("$6$", (5.5, 4.5)); label("$10$", (4.5, 5.5)); label("$9$", (6.5, 5.5)); label("$19$", (5.5, 6.5)); label("$9$", (7.5, 6.5)); label("$28$", (6.5, 7.5)); [/asy]

The answer is therefore $\boxed{\textbf{(A) }28}$.

Solution 2

Suppose we "extend" the chessboard infinitely with $2$ additional columns to the right, as shown below. The red line shows the right-hand edge of the original board.

[asy] int N = 7; for (int i = 0; i < 10; ++i) { for (int j = 0; j < 8; ++j) { draw((i,j)--(i+1,j)--(i+1,j+1)--(i,j+1)--(i,j)); if ((i+j) % 2 == 0) { filldraw((i,j)--(i+1,j)--(i+1,j+1)--(i,j+1)--(i,j)--cycle,black); } } } draw((8,0) -- (8,8),red); label("$P$", (5.5,.5)); label("$Q$", (6.5,7.5)); label("$X$", (8.5,3.5)); label("$Y$", (8.5,5.5)); [/asy]

The total number of paths from $P$ to $Q$, including invalid paths which cross over the red line, is then the number of paths which make $4$ steps up-and-right and $3$ steps up-and-left, which is $\binom{4+3}{3} = \binom{7}{3} = 35$. We need to subtract the number of invalid paths, i.e. the number of paths that pass through $X$ or $Y$. To get to $X$, the marker has to make $3$ up-and-right steps, after which it can proceed to $Q$ with $3$ steps up-and-left and $1$ step up-and-right. Thus, the number of paths from $P$ to $Q$ that pass through $X$ is $1 \cdot \binom{3+1}{3} = 4$. Similarly, the number of paths that pass through $Y$ is $\binom{4+1}{1}\cdot 1 = 5$. However, we have now double-counted the invalid paths which pass through both $X$ and $Y$; from the diagram, it is clear that there are only $2$ of these (as the marker can get from $X$ to $Y$ by a step up-and-left and a step-up-and-right in either order). Hence the number of invalid paths is $4+5-2=7$, and the number of valid paths from $P$ to $Q$ is $35-7 = \boxed{\textbf{(A) }28}$.

Solution 3

On any white square, we may choose to go left or right, as long as we do not cross over the border of the board. Call the moves $L$ and $R$ respectively. Every single legal path consists of $4$ $R's$ and $3$ $L's$, so now all we have to find is the number of ways to order $4 R's$ and $3 L's$ in any way, which is ${7 \choose 3}=35$. However, we originally promised that we will not go over the border, and now we have to subtract the paths that do go over the border. The paths that go over the border are any paths that start with RRR(1 path), RR(5 paths) and LRRR(1 path) so our final number of paths is $35-7=\boxed{(A)=28}.$ ~PEKKA

Solution 4: Intuitive Approach

We label the rows starting from the bottom. At row 1, there is $1$ way: at P. We draw all the possible ways to get to Q. There are two ways to choose for row 2, and another two ways to choose for row 3. However, you can go to the "edge" or the farthest possible square westward of Q, so you can't multiply by 2 again. Notice how, at the first step, we figured that the answer was even, so choice D and E are eliminated, and after the second row, we realized it must be a multiple of 4, so choice B is eliminated. When we get to the fourth row, we do not multiply by 2 again, since we have limited possibilities rather than multiplying by 2 again. Choice C implies that there are two possibilities per row; however, we know that if you go to the farthest possible, you only have one possibility, so it is not $2^5 = 32$ so we know that the answer is choice $\boxed{\textbf{(A)}}$. ~hh99754539


Video Solution by MathisCool

https://www.youtube.com/watch?v=LvpCYn8Ze6c


Video Solution by North America Math Contest Go Go Go

https://www.youtube.com/watch?v=rWxhlItMAN0

~North America Math Contest Go Go Go

Video Solution by WhyMath

https://youtu.be/YR3oghbziBA

~savannahsolver

Video Solutions

https://youtu.be/hGCxt8G9g-s

Video Solution by Interstigation

https://youtu.be/YnwkBZTv5Fw?t=1247

~Interstigation

See also

2020 AMC 8 (ProblemsAnswer KeyResources)
Preceded by
Problem 20
Followed by
Problem 22
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 AJHSME/AMC 8 Problems and Solutions

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