This is a math competition question I did. Essentially, starting at B, a move consists of moving to a non-diagonal adjacent square and noting the letter you land on (with the exception of the starting letter B). How many ways can you spell BANANA?
So I've attempted this problem multiple times (to an incorrect answer) and have eventually resorted to the most primitive method, which was just listing every possible combination which does give me the right answer of 84.
What I did was I labelled each square with a number from 1 to 9 and wrote down all the possible 'number combinations' assuming the first move is a rightwards move and then multiplied it by 2 because of the symmetry of the puzzle.
While this is not wrong, could anyone suggest possibly a better/more elegant solution?
I'm not really sure what tags to add to this so please give some suggestions and I'll edit this post later. There is a solution provided in Dutch but I'm just curious about other ways as well.
Here is the English translation.
If the first N of BANANA is in the blue box as well as the second N, then there are two possibilities for the second and the third A, so $2+2 = 4$ possibilities for BANANA.
For blue-green there are likewise $2 \cdot 4 = 8$ possibilities.
For blue-white there are $1 \cdot 2 = 2$ possibilities. In total there are therefore $4 + 8 + 2 = 14$ possibilities if the first N is in the blue box.
If the first N is in the yellow box, there are also $14$ possibilities in the same way.
For green-green we find $2 \cdot 4 \cdot 4 = 32$ possibilities.
For green-blue we find $2 \cdot 2 \cdot 2 = 8$ possibilities, likewise for green-yellow and for green-white.
So if the first N is in the green box, there are $32+ 8 + 8 + 8 = 56$ possibilities.
In total you can make BANANA in $14 + 14 + 56 = 84$ ways.
Best Answer
$\stackrel{\text{B}}{\begin{array}{|c|c|c|c|c|}\hline 1 & \ &\ \\ \hline & & \\\hline & & \\\hline \end{array}}$ $\to$ $\stackrel{\text{BA}}{\begin{array}{|c|c|c|c|c|}\hline \ & 1 & \ \\\hline 1& & \\\hline & & \\ \hline \end{array}}$ $\to$ $\stackrel{\text{BAN}}{\begin{array}{|c|c|c|c|c|}\hline \ & & 1 \\\hline &2 & \hline\\\hline 1& & \\\hline \end{array}}$ $\to$ $\stackrel{\text{BANA}}{\begin{array}{|c|c|c|c|c|}\hline \ & 3 & \\\hline 3& & 3\\\hline &3 &\\\hline \end{array}}$ $\to$ $\stackrel{\text{BANAN}}{\begin{array}{|c|c|c|c|c|}\hline \ & & 6 \\\hline & 12& \\\hline 6& &6\\\hline \end{array}}$ $\to$ $\stackrel{\text{BANANA}}{\begin{array}{|c|c|c|c|c|}\hline \ & 18 & \\\hline 18 & &24 \\\hline &24 &\\\hline \end{array}}$
$18 + 18 + 24 + 24 = 84$.
This method is called "dynamic programming".