Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

2 Answers 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.

share|improve this answer

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?

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.