When is the number of lattice paths from $(1, 1) \to (x, y)$ divisible by $3$?

Question

Let $S$ be the set of $\{(1,1), (1,−1), (−1,1), (1,0), (0,1)\}$-lattice paths which begin at $(1,1),$ do not use the same vertex twice, and never touch either the $x$-axis or the $y$-axis. Let $S_{x,y}$ be the set of paths in $S$ which end at $(x,y).$ For how many ordered pairs $(x,y)$ subject to $1\leq x,y \leq 31$, is $|S_{x,y}|$ a multiple of $3$?

---

This is an old contest question from Brilliant.org.

Answer 1

Isn't $|S_{x,y}| = \infty$?

The set of steps allow you to go arbitrarily far and come back, without repeating vertices, or touching the axes.

Perhaps you are missing something from the problem statement?

For instance, are the paths restricted to stay within the square $1 \le x,y, \le 31$ and not just end there?

Answer 2

This is a cute problem.

Let $D_n$ be the diagonal which contains $(n,1)$ and $(1,n)$

For any two points $P$ and $Q$ on $D_n$, we must have that $|S_P| = |S_Q| = T_n (\text{say})$. (Can be easily shown, I will omit it).

Then we get the recurrence

$$T_{n+1} = 2nT_n + (n-1)T_{n-1}$$

with $T_1 = 1$, $T_2 = 2$.

You can compute your answer now. There are probably ways to simplify it further to ease the computation (so we can do it manually), but the above should be doable with a quick program.