Coin Walk

Because to move North/West the first flip must be heads and to move South/East it must be tails, there has to be an equal number of heads flipped on the first flip as tails. This gives $(^{20}_{10})$ ways to flip the first coin and get back to where you started.

Likewise, to move North/East, the second flip must be heads, and to move South/West, it must be tails. This means there are $(^{20}_{10})$ ways to flip the second coin and end up back where you started.

Because there are $4^{20}$ ways to perform all of the flips, the probability of returning to the start becomes $\frac{(^{20}_{10})^2}{4^{20}} = \frac{2133423721}{68719476736}$

so the answer is $70852900457$ .

Moving in each of the cardinal directions is equally likely. To return to the starting position after $20$ steps, you need to have taken an equal number ( $n$ each, say) of East and West steps and an equal number ( $10-n$ each) of North and South steps. Thus the probability of getting back to the start is $\frac{1}{4^{20}}\sum_{n=0}^{10} \frac{20!}{n! \times n! \times (10-n)! \times (10-n)!} \; = \; \frac{2133423721}{68719476736}$ making the answer $2133423721 + 68719476736 = \boxed{70852900457}$ .

To get back to where you started, you must have an equal amount of north steps and south steps, and an equal amount of west steps and east steps. If there are $2n$ steps, then you could have $n$ north, $n$ south, $0$ west, and $0$ east steps in any order for a total of $\frac{(2n)!}{n!n!0!0!}$ different ways, or you could have $n - 1$ north, $n - 1$ south, $1$ west, and $1$ east steps in any order for a total of $\frac{(2n)!}{(n - 1)!(n - 1)!1!1!}$ different ways, and so on, until $0$ north, $0$ south, $n$ west, and $n$ east steps in any order for a total of $\frac{(2n)!}{0!0!n!n!}$ different ways. In summary:

$W = \sum_{k=0}^{n} \frac{(2n)!}{((n - k)!)^2(k!)^2}$

which can be shown inductively to be equal to

$W = \bigg(\frac{(2n)!}{n!n!}\bigg)^2$

For $20$ steps, there are $\bigg(\frac{(2 \cdot 10)!}{10!10!}\bigg)^2 = 34134779536$ ways to get back to where you have started out of a total of $4^{20} = 1099511627776$ ways , for a probability of $\frac{2133423721}{68719476736}$ . Therefore, $p = 2133423721$ , $q = 68719476736$ , and $p + q = \boxed{70852900457}$ .