In how many different ways can the word banana be read from the following table by moving from one cell to another cell, with which it shares an edge? Cells may be visited more than once. So this is a pretty involved question, and it's a counting question, so a very powerful strategy that we can use for counting questions is casework. So let's do casework by the first N that we reach. Obviously, we'll start with B, and then we'll visit some A, and then we always reach some N. So we'll do casework on the first N that we reach. Notice that the first N we reach can be the first row, third column, the second row, second column, or the third row, first column. The one, the N on the bottom right, we can't reach as the first N, and therefore it won't be one of our cases. So our first case will be the N in the first row, third column. So, in this case, let's consider the second N that we reach. If the second N is also the same first row, third column N, then there are 2 times 2 equals 4 possibilities. How we reach this is, in order to reach the first row, third column N, the only possible way to reach this the first time is to go B, A, N, all in the top row. Then, to reach that same N again, we can go to either of the A's that are around it, so the first row, second column A, which is right here, or this one right here. Then, there's 2 ways to reach the second N, and then after we reach the second N, we can go to another A, and we can go again to this A or this A, so we get 4 possibilities. Now, if the second N, after reaching this N first, is this one, then we have 2 times 4, which is 8 possibilities. We get 2 times 4 because after we reach B, A, N in the same way as previous, then reaching this N, we can either go A, N like this, which is 1, or A, N like this, which is 2. Then, N right here borders 4 A's, so the final A can be any of these 4. So, we have 2 times 4, which is 8 possibilities. Finally, if the second N is the third row, third column N, which is right here, then there are 2 possibilities, because we must follow B, A, N, and then to reach that N that we just highlighted, then we must go down A, N. So far, there's only been exactly 1 way to get to this place, and then we can go to any final A, and it's either here or here, which is 2 possibilities. Note that if this is our first N, the N right here cannot be our second, because there's no possible way that we get there. So then, in total, we have 4 plus 8 plus 2, which is 14 possibilities. Next, if the first N is in the second row, second column, we'll consider the second N. If the second N is again the same second row, second column, then to reach this N again, we can go to any of these 4, and then after the second N, we can go to any of these 4 as our second A, which is 16 possibilities. If the second N is any of the other 3 Ns, then there's 2 ways to reach that second N. So, for example, to get here, we can go up and then over, or over and then up. Same with the other Ns. And then we have 4 possibilities, because after we reach that N, that can go to this one or this one as our final A. Then there's a total of 4 possibilities for each of the 3 Ns. Therefore, we have 16 plus 3 times 4 possibilities, which is 28, but there are 2 ways to reach this first N, which we can go here or here. So we have 2 times 28, which is 56 possibilities from the second row, second column N. Now, note that this third case, the N in the first row, third column, is exactly symmetric to the N right here, and therefore, we again have 14 possibilities. Adding up all of our cases, we have 14 plus 56 plus 14, which is D, 84 possibilities, and therefore, our answer is D.

grid

banana

casework

combinatorics

pathfinding