# Lattice Paths from $(1, 1) \to (x, y)$

Moderator Note: This is a current contest question on Brilliant.org.

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$?

-
A bijection can be formulated. Consider an upward motion by a 0 and a rightward motion by a 1. Now each path is a unique binary number. Enumerate now. –  Torsten Hĕrculĕ Cärlemän Jul 25 '13 at 16:32
This is reportedly an active question at Brilliant.org. –  robjohn Jul 28 '13 at 14:32

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.

-

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?

-
That is incorrect. All steps make $(x+y)$ either stay the same or increase. Hence if you want to go to $(a,b)$, there are only finitely many lattice points $(x,y)$ in the first quadrant such that $x+y\le a+b$. –  vadim123 Jul 26 '13 at 18:46