In how many ways can you spell the word ROOM in the grid below? You can start on any letter R, then on each step you can step one letter in any direction (up, down, left, right, or diagonal).
\[\begin{array}{ccccc}
R&R&R&R&R\\
M&O&O&O&M\\
M&O&O&O&M\\
M&O&O&O&M\\
R&R&R&R&R
\end{array}\]
Let's focus on the letter O's. First note that the middle O cannot participate in any valid ROOM path, so we may as well get rid of it. Now create a graph by letting each letter O be a vertex, and joining two neighboring vertices if we can go from one O to another by taking one step in any direction (up, down, left, right, or diagonal).
Here is the picture of the graph where each o is a vertex. The edges are represented by the sequence of dashes or vertical line. We also name the edges by the letters from A to H.
A B
o-----o-----o
C | | D
o o
E | | F
o-----o-----o
G H
Now, to each vertex let's write down the number of the letters R and M it can go to in one step. For example, entry 3r,2m means the vertex at that position can go to 3 different R's in one step, and 2 different M's in one step, etc.
3r,2m 3r,0m 3r,2m
0r,3m 0r,3m
3r,2m 3r,0m 3r,2m
Now, to each edge we count how many ways it can be part of a ROOM path. It is part of a ROOM path iff one end vertex is connected to R and the other end vertex is connected to M. We show the calculation below.
A: 3 * 2 = 6
B: 3 * 2 = 6
C: 3 * 3 = 9
D: 3 * 3 = 9
E: 3 * 3 = 9
F: 3 * 3 = 9
G: 3 * 2 = 6
H: 3 * 2 = 6
So the total number of ways equals $6+6+9+9+9+9+6+6 = 60$.
Let's focus on the letter O's. First note that the middle O cannot participate in any valid ROOM path, so we may as well get rid of it. Now create a graph by letting each letter O be a vertex, and joining two neighboring vertices if we can go from one O to another by taking one step in any direction (up, down, left, right, or diagonal).
Here is the picture of the graph where each o is a vertex. The edges are represented by the sequence of dashes or vertical line. We also name the edges by the letters from A to H.
A B
o-----o-----o
C | | D
o o
E | | F
o-----o-----o
G H
Now, to each vertex let's write down the number of the letters R and M it can go to in one step. For example, entry 3r,2m means the vertex at that position can go to 3 different R's in one step, and 2 different M's in one step, etc.
3r,2m 3r,0m 3r,2m
0r,3m 0r,3m
3r,2m 3r,0m 3r,2m
Now, to each edge we count how many ways it can be part of a ROOM path. It is part of a ROOM path iff one end vertex is connected to R and the other end vertex is connected to M. We show the calculation below.
A: 3 * 2 = 6
B: 3 * 2 = 6
C: 3 * 3 = 9
D: 3 * 3 = 9
E: 3 * 3 = 9
F: 3 * 3 = 9
G: 3 * 2 = 6
H: 3 * 2 = 6
So the total number of ways equals $6+6+9+9+9+9+6+6 = 60$.