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 "Block walking"

(→‎Solution)
Line 1: Line 1:
−
= Example Problem =
+
= Example problem =
 
If you can move only down or right, and you cannot go outside the boundaries of the lines, what is the number of ways you can get from <math>X</math> to <math>Y</math>?  
 
If you can move only down or right, and you cannot go outside the boundaries of the lines, what is the number of ways you can get from <math>X</math> to <math>Y</math>?  
  

Revision as of 12:17, 14 April 2020

Example problem

If you can move only down or right, and you cannot go outside the boundaries of the lines, what is the number of ways you can get from $X$ to $Y$?

Solution

[asy] label("X", (0,3), NW); label("Y", (3,0), SE); Draw((0,0) -- (3,0) -- (3,1) -- (3,3) -- (1,3) -- (0,3) -- cycle, linewidth(1)); Draw((1,0)--(1,3), linewidth(1)); Draw((2,0)--(2,3), linewidth(1)); Draw((3,0)--(3,3), linewidth(1)); Draw((0,1)--(3,1), linewidth(1)); Draw((0,2)--(3,2), linewidth(1)); Draw((0,3)--(3,3), linewidth(1)); [/asy]

We are going to move either right or down. We start off with some easier means of this problem from A to B by labeling closer distances. Let's label these points with letters.

[asy] label("X", (0,3), NW); label("Y", (3,0), SE); label("C", (2,0), SE); label("D", (1,0), SW); label("E", (0,0), SW); label("F", (0,1), SW); label("G", (0,2), NW); label("H", (1,1), SW); label("I", (2,1), SE); label("J", (3,1), SE); label("K", (3,2), NE); label("L", (3,3), NE); label("M", (2,2), NE); label("N", (2,3), NE); label("O", (1,3), NW); label("P", (1,2), NW); Draw((0,0) -- (3,0) -- (3,1) -- (3,3) -- (1,3) -- (0,3) -- cycle, linewidth(1)); Draw((1,0)--(1,3), linewidth(1)); Draw((2,0)--(2,3), linewidth(1)); Draw((3,0)--(3,3), linewidth(1)); Draw((0,1)--(3,1), linewidth(1)); Draw((0,2)--(3,2), linewidth(1)); Draw((0,3)--(3,3), linewidth(1)); [/asy]

We first find that $\overline{YJ}$ and $\overline{YC}$ which is 1 for both of them "for $\overline{YJ}$ we have to move down, and for $\overline{YC}$ we move right 1".

[asy] label("X", (0,3), NW); label("Y", (3,0), SE); label("1", (2,0), SE); label("D", (1,0), SW); label("E", (0,0), SW); label("F", (0,1), SW); label("G", (0,2), NW); label("H", (1,1), SW); label("I", (2,1), SE); label("1", (3,1), SE); label("K", (3,2), NE); label("L", (3,3), NE); label("M", (2,2), NE); label("N", (2,3), NE); label("O", (1,3), NW); label("P", (1,2), NW); Draw((0,0) -- (3,0) -- (3,1) -- (3,3) -- (1,3) -- (0,3) -- cycle, linewidth(1)); Draw((1,0)--(1,3), linewidth(1)); Draw((2,0)--(2,3), linewidth(1)); Draw((3,0)--(3,3), linewidth(1)); Draw((0,1)--(3,1), linewidth(1)); Draw((0,2)--(3,2), linewidth(1)); Draw((0,3)--(3,3), linewidth(1)); [/asy]

For $YI$ she is going to have to either go right or down to start off with when we go right, we already know how many ways we have, which would be 1. For down, we again know how many ways we have, which is 1. Therefore for $YI$ we have 2 total ways.


[asy] label("X", (0,3), NW); label("Y", (3,0), SE); label("1", (2,0), SE); label("D", (1,0), SW); label("E", (0,0), SW); label("F", (0,1), SW); label("G", (0,2), NW); label("H", (1,1), SW); label("2", (2,1), SE); label("1", (3,1), SE); label("K", (3,2), NE); label("L", (3,3), NE); label("M", (2,2), NE); label("N", (2,3), NE); label("O", (1,3), NW); label("P", (1,2), NW); Draw((0,0) -- (3,0) -- (3,1) -- (3,3) -- (1,3) -- (0,3) -- cycle, linewidth(1)); Draw((1,0)--(1,3), linewidth(1)); Draw((2,0)--(2,3), linewidth(1)); Draw((3,0)--(3,3), linewidth(1)); Draw((0,1)--(3,1), linewidth(1)); Draw((0,2)--(3,2), linewidth(1)); Draw((0,3)--(3,3), linewidth(1)); [/asy]

We also know for $KY, LY, DY, EY$ we are going to have to go 2 or 3 down/right in both cases, which is a total of 1.

[asy] label("X", (0,3), NW); label("Y", (3,0), SE); label("1", (2,0), SE); label("1", (1,0), SW); label("1", (0,0), SW); label("F", (0,1), SW); label("G", (0,2), NW); label("H", (1,1), SW); label("2", (2,1), SE); label("1", (3,1), SE); label("1", (3,2), NE); label("1", (3,3), NE); label("M", (2,2), NE); label("N", (2,3), NE); label("O", (1,3), NW); label("P", (1,2), NW); Draw((0,0) -- (3,0) -- (3,1) -- (3,3) -- (1,3) -- (0,3) -- cycle, linewidth(1)); Draw((1,0)--(1,3), linewidth(1)); Draw((2,0)--(2,3), linewidth(1)); Draw((3,0)--(3,3), linewidth(1)); Draw((0,1)--(3,1), linewidth(1)); Draw((0,2)--(3,2), linewidth(1)); Draw((0,3)--(3,3), linewidth(1)); [/asy]

Using this same process, we find for $MY$ and $HY$ we are going to have to go down or right. From there, we already have the numbers filled in. For $MY$ it is $1+2$, and for $HY$ is it $2+1$ which in both cases is 3.

[asy] label("X", (0,3), NW); label("Y", (3,0), SE); label("1", (2,0), SE); label("1", (1,0), SW); label("1", (0,0), SW); label("F", (0,1), SW); label("G", (0,2), NW); label("3", (1,1), SW); label("2", (2,1), SE); label("1", (3,1), SE); label("1", (3,2), NE); label("1", (3,3), NE); label("3", (2,2), NE); label("N", (2,3), NE); label("O", (1,3), NW); label("P", (1,2), NW); Draw((0,0) -- (3,0) -- (3,1) -- (3,3) -- (1,3) -- (0,3) -- cycle, linewidth(1)); Draw((1,0)--(1,3), linewidth(1)); Draw((2,0)--(2,3), linewidth(1)); Draw((3,0)--(3,3), linewidth(1)); Draw((0,1)--(3,1), linewidth(1)); Draw((0,2)--(3,2), linewidth(1)); Draw((0,3)--(3,3), linewidth(1)); [/asy]

For $NY$ and $FY$ we have to move down or right, and find we have $3+1=4$ total ways once we move down/right.

[asy] label("X", (0,3), NW); label("Y", (3,0), SE); label("1", (2,0), SE); label("1", (1,0), SW); label("1", (0,0), SW); label("4", (0,1), SW); label("G", (0,2), NW); label("3", (1,1), SW); label("2", (2,1), SE); label("1", (3,1), SE); label("1", (3,2), NE); label("1", (3,3), NE); label("3", (2,2), NE); label("4", (2,3), NE); label("O", (1,3), NW); label("P", (1,2), NW); Draw((0,0) -- (3,0) -- (3,1) -- (3,3) -- (1,3) -- (0,3) -- cycle, linewidth(1)); Draw((1,0)--(1,3), linewidth(1)); Draw((2,0)--(2,3), linewidth(1)); Draw((3,0)--(3,3), linewidth(1)); Draw((0,1)--(3,1), linewidth(1)); Draw((0,2)--(3,2), linewidth(1)); Draw((0,3)--(3,3), linewidth(1)); [/asy]

$YP$ is going to have the two cases of going down/right again, which is going to give us $3+3=6$

[asy] label("X", (0,3), NW); label("Y", (3,0), SE); label("1", (2,0), SE); label("1", (1,0), SW); label("1", (0,0), SW); label("4", (0,1), SW); label("G", (0,2), NW); label("3", (1,1), SW); label("2", (2,1), SE); label("1", (3,1), SE); label("1", (3,2), NE); label("1", (3,3), NE); label("3", (2,2), NE); label("4", (2,3), NE); label("O", (1,3), NW); label("6", (1,2), NW); Draw((0,0) -- (3,0) -- (3,1) -- (3,3) -- (1,3) -- (0,3) -- cycle, linewidth(1)); Draw((1,0)--(1,3), linewidth(1)); Draw((2,0)--(2,3), linewidth(1)); Draw((3,0)--(3,3), linewidth(1)); Draw((0,1)--(3,1), linewidth(1)); Draw((0,2)--(3,2), linewidth(1)); Draw((0,3)--(3,3), linewidth(1)); [/asy]

For $GY$ and $OY$ we are going to have 6+4=10 total ways (since we start going down and right, and the cases have already been done for the points from that location).

[asy] label("X", (0,3), NW); label("Y", (3,0), SE); label("1", (2,0), SE); label("1", (1,0), SW); label("1", (0,0), SW); label("4", (0,1), SW); label("10", (0,2), NW); label("3", (1,1), SW); label("2", (2,1), SE); label("1", (3,1), SE); label("1", (3,2), NE); label("1", (3,3), NE); label("3", (2,2), NE); label("4", (2,3), NE); label("10", (1,3), NW); label("6", (1,2), NW); Draw((0,0) -- (3,0) -- (3,1) -- (3,3) -- (1,3) -- (0,3) -- cycle, linewidth(1)); Draw((1,0)--(1,3), linewidth(1)); Draw((2,0)--(2,3), linewidth(1)); Draw((3,0)--(3,3), linewidth(1)); Draw((0,1)--(3,1), linewidth(1)); Draw((0,2)--(3,2), linewidth(1)); Draw((0,3)--(3,3), linewidth(1)); [/asy]

Now we evaluate $XY$. For $XY$, we have two cases. We can go down, or right. When we go right, we get O which has 10 possible ways from there. When we go down, we get G which has 10 possible ways. Therefore $XY$ has $\boxed{20}$ possibles ways when only going right or down.


[asy] label("20", (0,3), NW); label("Y", (3,0), SE); label("1", (2,0), SE); label("1", (1,0), SW); label("1", (0,0), SW); label("4", (0,1), SW); label("10", (0,2), NW); label("3", (1,1), SW); label("2", (2,1), SE); label("1", (3,1), SE); label("1", (3,2), NE); label("1", (3,3), NE); label("3", (2,2), NE); label("4", (2,3), NE); label("10", (1,3), NW); label("6", (1,2), NW); Draw((0,0) -- (3,0) -- (3,1) -- (3,3) -- (1,3) -- (0,3) -- cycle, linewidth(1)); Draw((1,0)--(1,3), linewidth(1)); Draw((2,0)--(2,3), linewidth(1)); Draw((3,0)--(3,3), linewidth(1)); Draw((0,1)--(3,1), linewidth(1)); Draw((0,2)--(3,2), linewidth(1)); Draw((0,3)--(3,3), linewidth(1)); [/asy]

How does block walking even work?

At this point, you may be wondering, how does block walking work? When you are restricted to certain boundaries of only moving two different directions, the first move from a certain spot is going to have to be one of those two directions. We start off at the beginning, where we know how to count the cases. From there, we can begin filling in more boxes, until we get to the final point. These boxes are filled out, knowing that we have to start by going one specific direction. Since we already have this information filled out, we can just find the sum of the two different directions. We continue doing this, until we get to the area that we want to find the amount of ways. We will already have the two different directions marked by this time, so we can just add these two points to get our final result.

Question to think about

  • What pattern do these numbers have? (Hint: try rotating your head 135 degrees) Can you explain this?
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Block_walking&oldid=120971"