Zig-zag through the maize

Let $Q_n$ be the set of points $(x,y)$ such that $x + y = 2n$ and it is legal to move to this point, i.e. $x,y \gt 0$ . Clearly $\vert Q_n \vert = 2n - 1$ .

The moves $(1, -1)$ and $(-1, 1)$ therefore take us from a point in some $Q_n$ to another point in the same $Q_n$ .

The move $(1,1)$ takes us from $Q_n$ to $Q_{n+1}$ . There are no other ways to change our $Q$ level.

So, a valid path must consist of exactly one $(1,1)$ move starting from a point in $Q_{k-1}$ and ending at a point in $Q_k$ , for all $2 \le k \lt 6$ , because $(4,8)$ is in $Q_6$ ; and some other moves which move "sideways" within a $Q$ set.

Further, making a selection of such points $Q_k$ defines a unique path. To see this, suppose that we choose $(x, 2n-x) \in Q_n$ and $(w, (2n+2)-w) \in Q_{n+1}$ as the endpoints of $(1,1)$ moves. The latter move must have started at the point $(w-1, 2n - (w-1))$ in $Q_n$ . But to move from one point in $Q_n$ to another point in $Q_n$ there is only one possible path, since the rules prohibit backtracking.

So we just need to count how many ways of selecting the points $Q_k$ where $k$ goes up to 5. We are selecting $(4,8)$ specifically in $Q_6$ . This is $\prod_{k=2}^5 \vert Q_k \vert$ , which is $3 \times 5 \times 7 \times 9 = \boxed{945}$ .

Drawing a diagram clears up the situation a lot. You are on (1,1), and you essentially can make unit diagonal moves NW, NE, and SE. You cannot touch the x and y axis. After drawing a grid for paths that you can take, you see that there are columns (which go SW to NE) and rows (which go SE to NW). We will handle this problem going row by row.

First, let's look at the very first row (call this row 0), which contain only the point (1,1). There is 1 way to get to this point: do nothing.

The next row (row 1) contains the points (1,3), (2,2), and (3,1). Each of these points have one way to arrive there from row 0.

Row 2 consists of (1,5), (2,4), (3,3), (4,2), (5,1). Each of these points have one way to get to there from each of the points on row 1: therefore, there are $1+1+1=3$ ways to get to each of these points.

Similarly, each point on row 3 has one way to get to there from each point on row 2. Therefore, there are $3+3+3+3+3=15$ ways to get to each point on row 3.

Continuing the pattern, there are $15+15+15+15+15+15+15=105$ ways to get to each point on row 4.

There are $105+105+105+105+105+105+105+105+105=945$ ways to get to each point on row 5. It happens that our goal point, (4,8), is on row 5, so our answer is $\boxed{945}$ .

To make sure there aren't any extra ways to get to (4,8) from row 6, we go on row 6 and try to backtrack to (4,8). But note that once you go up a row, it is impossible to go down a row, so there are no extra ways.

The problem simply asks for the number of lattice paths which, at each step, move along the directions $\nearrow, \searrow,$ and $\nwarrow$ , and don't touch the $x$ or $y$ axes. We call such a path a good path.

If the image doesn't load, go to: http://s28.postimg.org/d9xj6ylnh/Untitled.png

Let $q_{a, b}$ denote the number of good paths from $(1, 1)$ to the point $(a, b)$ , and let $n= a+b$ . The trick here is to consider all points on the line $x+y= n$ , not just $(a, b)$ . The picture above might help the reader visualize. The red and green colored lines are the lines of the form $x+y= k$ for some $k$ .

We claim that $q_{a, b}$ remains fixed as we move along the line $x+y= n$ . In other words, if $t_n$ denotes the number of good paths from $(1, 1)$ to the line $x+y= n$ , $q_{a, b}= t_n$ whenever $a+b=n$ . Let's say a good path touches the line $x+y= n$ at the point $(p, q)$ . Note that a unique series of $\searrow$ and $\nwarrow$ moves brings the point $(p, q)$ to $(a, b)$ if they both lie on the line $x+y= n$ . The bijection is obvious: each good lattice path to $(a, b)$ corresponds to some lattice path to the line $x+y=n$ . Conversely, any good lattice path to the line $x+y= n$ corresponds to a good lattice path to $(a, b)$ .

We shall now try to find a recursion on $t_n$ . Let's see how the line $x+y= n$ can be approached from the line $x+y= n-2$ . Note that it cannot be approached from the line $x+y= n-1$ . There are $n-3$ lattice points on the line $x+y= n-2$ which don't lie on either of the axes. There are $t_{n-2}$ ways to reach each of these points, and a single $\nearrow$ move brings each of these points to the line $x+y= n$ . This gives us the recursion $t_n= (n-3)t_{n-2}$ .

An easy check shows that $t_2= 1$ . We now apply this recursion successively to obtain: $t_4= 1, t_6 = 3, t_8= 15, t_{10}= 105, t_{12}= 945.$ Our desired answer is $t_{4+8}= t_{12}= \boxed{945}$ .

We call a lattice path good iff it passes through a lattice point at most once, its steps belong to the set $\{(1,1), (1,-1), (-1,1) \}$ , and it lies solely in the first quadrant or on the positive axes. We wish to find out the number of good lattice paths starting from the origin and ending at $(3,7)$ . Notice that each such lattice path can be obtained from another lattice path satisfying the conditions mentioned in the question by a $(1,1)$ translation of the axes. So if we are able to find the number of such lattice paths, we will be done.

Claim Any good lattice path starting from the origin and going to $(a,b)$ must lie within the region bounded by the positive axes and the line $x+y=a+b$ .
Proof From the imposed conditions it is clear that any good lattice path must lie within the region bounded by the positive axes (i.e the $1^{st}$ quadrant). On the contrary, assume a good lattice path exceeds the region bounded by the line $x+y=a+b$ . Consider any point $(m,n)$ on that lattice path, where $m+n= k>a+b$ . From here, we wish to determine a sequence of $\{(1,1), (-1,1), (1,-1) \}$ steps which will take us to a point line on the line $x+y=a+b$ . Note that a $(-1,1)$ step will translate the point parallel to that line, whereas the steps $(1,1)$ and $(1,-1)$ will take the point further from it. This is a contradiction. QED

Claim The number of good lattice paths from the origin to $(a,b)$ is equal to the number of good lattice paths from the origin to the line $x+y=a+b$ .
Proof Any such good lattice path must intersect the line $x+y=a+b$ at one point, say $(k, a+b-k)$ . From the first claim, once such a lattice path reaches this line, it must traverse along this line until it reaches its destination. Also note that a unique series of $\{(1,-1), (-1,1) \}$ steps brings the point $(k,a+b-k)$ to $(a,b)$ . This proves our desired claim. QED

Let $L_n$ be the number of good lattice paths from the origin to the line $x+y=n$ . Note that we wish to determine $L_{7+3}= L_{10}$ . Let $T_{a,b}$ be the number of good lattice paths from the origin to the point $(a,b)$ which intersects the line $x+y=a+b$ at one point only (namely the point $(a,b)$ ). Note that $L_n= \sum \limits_{k=0}^{n} T_{k, n-k}$ . We now make the following observations:

$1)$ Note that \T {n,0}= T {0,n}= 0). This is obviously true, since those points can be approached only from the point $(n-1, 1)$ and $(1,n-1)$ respectively, but both of them lie on the line $x+y=n$ , and hence do not appear in the count of $T_{n,0}$ or $T_{0,n}$ .

$2)$ Consider a point $(m, n-m)$ on the line $x+y=n$ , such that $2 \leq m \leq n-2$ . Note that this point can be approached from the points $(m+1, n-m-1)$ , $(m-1, n-m+1)$ , and $(m-1, n-m-1)$ . However, out of them the first two points lie on the line $x+y=n$ , and therefore do not appear in the count of $T_{m,n-m}$ . Also note that the line $(m-1, n-m-1)$ lies on the line $x+y=n-2$ . Hence we conclude $T_{m,n-m}= f(n-2)$ . Now, note that: $f(n)= \sum \limits_{k=0}^{n} T_{k, n-k} = T_{0, n} + T_{n, 0} + \sum \limits_{k=1}^{n-1} T_{k,n-k}$ $= \sum \limits_{k=1}^{n-1} f(n-2) = (n-1)f(n-2) \text{ .....(i)}$ An easy check shows that $f(2)= 1$ . We now apply the recurrence relation in $(i)$ successively to obtain: $f(4)= 3 \times 1= 3$ $f(6)= 5 \times 3 = 15$ $f(8)= 7 \times 15 = 105$ $f(10)= 9 \times 105 = \boxed{945}$

1 x 3 x 5 x 7 x 9 In fact, per each step from 1;1 to 2;2 we can draw a rectangle of dimensions (1, 3/5/7/9)

In order to end at $(4,8)$ , a path in $S$ must have exactly 5 steps of size $(1,1)$ . Specifically, the nth such step will be from $(n+k_n,n-k_n)$ to $(n+1+k_n,n+1-k_n)$ with $k_n\in\{1-n, ...,0,...,n-1\}$ . Then the total numbers of ways of choosing those 5 steps of size $(1,1)$ is

$1 \cdot 3 \cdot 5 \cdot 7 \cdot 9 = 945$

and each such choice corresponds to exactly one path in $S$ ending at $(4,8)$ (i.e. there's exactly one legal way to get from $(n+1+k_n,n+1-k_n)$ to $(n+1+k_{n+1},n+1-k_{n+1})$ ).