A walk on the chessboard with conditions!

Question

A 16 step path is to go from (-4,-4) to (4,4) with each step increasing in either the x-coordinate or the y-coordinate by 1. How many such paths stay outside or on the boundary of the square $-3<x<3,\ -3<y<3$ at each step?

(Background) I am a 12th grader and I know about dots and dashes and Pascal's triangle.

Answer 1

For this particular question, it i s probably easiest just to write a table of the number of ways of reaching each square moving up or right from the bottom left. Each value is the sum of the value below it and the value to its left.

1   9   17  25  33  41  49  65  130
1   8   8   8   8   8   8   16  65
1   7                       8   49
1   6                       8   41
1   5                       8   33
1   4                       8   25
1   3                       8   17
1   2   3   4   5   6   7   8   9
1   1   1   1   1   1   1   1   1

Combinatorially, look at the possible positions after eight steps and the numbers associated going to and from them. You can either take routes via the points $(4,-4)$ or $(-4,4)$ or go via the points $(3,-3)$ or $(-3,3)$ which will give you the answer $${8 \choose 0}{8 \choose 0}+{8 \choose 0}{8 \choose 0}+{8 \choose 1}{8 \choose 1}+{8 \choose 1}{8 \choose 1}=1+1+64+64=130$$

Answer 2

Start with the total number of combinations for 8 Ups and 8 Rights (UUUUUUUURRRRRRRR, RRLLRRLLRRLLRRLL, ...) $\frac{16!}{(8!)^2} = 12870$

There are 8 that let you enter the NO spaces for the first time:

(-2,2) from (-3,2)

(-2,1) from (-3,1)

(-2,-1) from (-3, -1)

(-2, -2) from (-3, -2)

(-2,-2) from (-2, -3)

(-1, -2) from (-1, -3)

(1, -2) from (1, -3)

(2,-2) from (2, -3)

Find [number of paths from (-4,-4) to the first half of the entry into the middle] * [number of paths to (4,4) from the second half of the entry] for each of the 8 entries, then subtract the 8 numbers from 12870.

Answer 3

We will make four cases based on the first two steps in our path:

RR: For the next six steps, we are allowed to take only one U step, if we take it at all. If we take it, then there are $\binom{6}{1}$ ways for the six steps and $\binom{8}{1}$ ways for the next eight steps. If we don't take it, there is only one way to choose the six steps (all Rs) and then only one way to choose the next eight (all Us). This gives a total of $6\cdot 8 + 1\cdot 1 = 49$ ways for this case.

UU: Since this case is symmetric to the case above, the argument and total number of ways are the same, i.e. $49$.

RU: We cannot enter the inner square but we are now on its border, so we must follow it. We will reach either the top left or bottom right corner, from which there are [symmetrically] $\binom{8}{1}$ ways for the next steps. This gives us $2 \cdot 8 = 16$ ways for this case.

UR: Since this case is symmetric to the case above, the argument and total number of ways are the same, i.e. $16$.

We thus have a total of $49+49+16+16 = 130$ ways to go from $(-4,-4)$ to $(4,4)$ through lattice points avoiding the square $-3<x,y<3$. However, I do not think this method can be generalized to different constraints easily, and I am trying to find an approach that can.