9
$\begingroup$

Problem: In $\mathbb{Z}^3$ starting from $(0,0,0)$ we try to reach $(p,q,r)$ with a sequence of moves. In each step we make a move from a point to another point under following conditions:

  • You can only move to a point with integer coordinates.
  • You can only move to a point $(a,b,c)$ such that $0\leq a \leq p, \ 0 \leq b \leq q,\ 0 \leq c \leq r$. i.e. you have to stay in the "$p,q,r$" prism.
  • You can't move to a point that you have already moved.
  • From a point $(a,b,c)$ you can move to one of the points $(a+1,b,c),(a-1,b,c),(a,b+1,c),(a,b-1,c),(a,b,c+1),(a,b,c-1)$ which satisfy above conditions i.e. you can move 1 unit step in one of the three coordinates.

We denote $f(p,q,r)$ as different ways of reaching $(p,q,r)$ from $(0,0,0)$ as described above. Is there a closed formula or a recurrence relation for $f(p,q,r)$?

Ideas:

  • I know that if we change the 4th restriction with "you can only move in the positive directions" then the answer is $\frac{(p+q+r)!}{p!q!r!}$. So $f(p,q,r)$ is larger than this number.
  • Second condition makes it very difficult to use induction or recurrence relation.
  • Working on two dimensional version of the problem doesn't make it simple.

I believe this problem must have appeared somewhere. Any references, hints are welcomed. Thank you for reading the entire entry.

$\endgroup$
4
  • 2
    $\begingroup$ In general, counting the number of simple (non-self-intersecting) paths connecting two nodes in a graph is computationally hard ($\mathsf{\#P}$-complete). Though this special case may have some special properties that make it easier than that, I doubt it… there is probably no closed-form or recurrence relation. $\endgroup$
    – mjqxxxx
    Nov 6, 2014 at 15:09
  • 1
    $\begingroup$ The results for the two-dimensional version on a square grid are in the OEIS: oeis.org/A007764 $\endgroup$
    – mjqxxxx
    Nov 6, 2014 at 17:21
  • 1
    $\begingroup$ You are trying to count the number of self-avoiding walks on the 3D integer lattice from the origin to $(p,q,r)$, such that they don't step outside of the boundaries of the box formed by the latter coordinate and the coordinate planes. Your step set is the 3D cardinal directions. Counting self-avoiding walks is usually a difficult task. The 2D unrestricted problem is still quite open. $\endgroup$
    – Alexander Vlasev
    Nov 8, 2014 at 9:59
  • $\begingroup$ So you are saying playing snake 3d is difficult? $\endgroup$
    – flawr
    Nov 8, 2014 at 23:37

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.