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

put on hold as off-topic by Grigory M, studiosus, Alizter, Rick Decker, Sami Ben Romdhane 2 days ago

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Grigory M, studiosus, Alizter, Rick Decker, Sami Ben Romdhane
If this question can be reworded to fit the rules in the help center, please edit the 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

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

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