, 2023

Solution:

Let $c_{i, j}$ denote the cell in the $i$-th row from the bottom and the $j$-th column from the left, so Sam starts at $c_{1,1}$ and is traveling to $c_{5,5}$. The key observation (from, say, trying small cases) is that

Claim. For $1 \leq i, j < 5$, the cells $c_{i+1, j}$ and $c_{i, j+1}$ must be the same color.

Proof. Choose a path $P$ from $c_{1,1}$ to $c_{i, j}$, and a path $Q$ from $c_{i+1, j+1}$ to $c_{5,5}$. Then consider the two paths $P \rightarrow c_{i+1, j} \rightarrow Q$ and $P \rightarrow c_{i, j+1} \rightarrow Q$. These both must have 3 cells of each color, but they only differ at cells $c_{i+1, j}$ and $c_{i, j+1}$. So these cells must be the same color.

Hence, every diagonal $D_{k} = \left\{ c_{a, b} : a + b = k \right\}$ must consist of cells of the same color. Moreover, any path that goes from $c_{1,1}$ to $c_{5,5}$ contains exactly one cell in $D_{k}$ for $k = 2, 3, \ldots, 10$. So we simply need to color the diagonals $D_{2}, \ldots, D_{10}$ such that there are 3 diagonals of each color. The number of ways to do this is $\binom{9}{3,3,3} = 1680$.