Motivation for this solution to a British olympiad problem

The video solution is really clever, but you can also solve the problem by just slogging along. As the presenter said at the beginning, we have to choose $2k$ east-west moves, $k$ of which will be west, and then we have to choose $1009-k$ north moves. The remaining $1009-k$ moves will be south. This gives $$ n=\sum_{k=0}^{1009}{2018\choose k}{2018 -k\choose k}{2018-2k\choose1009-k}$$ possible paths. Let's try to simplify this before giving up. We have $$\begin{align} n&=\sum_{k=0}^{1009}{2018!\over k!(2018-k)!}{(2018-k)!\over k!(2018-2k)!}{(2018-2k)!\over (1009-k)!(1009-k)!}\\&=\sum_{k=0}^{1009}{2018!\over k!(1009-k)!k!(1009-k)!}\\&={2018!\over 1009!1009!}\sum_{k=0}^{1009}\left({1009!\over k!(1009-k)!}\right)^2\\&={2018\choose 1009}\sum_{k=0}^{1009}{1009\choose k}^2\end{align}$$

Up to here, I think it is pretty straightforward. Those factors of $k!(1009-k)!$ should suggest trying to express things in terms of ${1009\choose k}$. Now comes a trick, Vandermonde's identity. Even if you don't recall exactly what it says, if you've ever seen the proof, you should be able to recreate the formula. $$ \sum_{k=0}^{1009}{1009\choose k}^2=\sum_{k=0}^{1009}{1009\choose k}{1009\choose 1009-k}={2018\choose 1009}$$ The last equality comes because to choose $1009$ elements from a collection of $2018$ we can choose $k$ from the first $1009$ and the remaining $1009-k$ from the second $1009.$

Putting it all together, we have $$n={2018\choose1009}^2$$

I am not at all clever, so this is how I did it.

You can just count how many possible paths the ant can take by assuming it makes $k$ steps to the east and $k$ to the west, then deciding the order of the east-west paths, similarly those of the north-south ($1009-k$) and finally deciding how to mix both sequences. Everything can hence be expressed in terms of binomial coefficients: $$\sum_{k=0}^{N}C_k^{2k}C_{N-k}^{2N-2k}C_{2k}^{2N}=\sum_{k=0}^{N}\frac{(2k)!}{(k!)^2}\frac{(2N-2k)!}{((N-k)!)^2}\frac{(2N)!}{(2k)!(2N-2k)!}$$ $$=\sum_{k=0}^{N}\frac{(2N)!}{(k!)^2((N-k)!)^2}$$ $$=\frac{(2N)!}{(N!)^2}\sum_{k=0}^{N}\left(C_N^k\right)^2=\left(C_{2N}^N\right)^2$$ where $N=1009$.

Then you can compute the $2$- and $5$-adic valuations with the usual formula:

$$\nu_p(A!)=\left\lfloor A/p \right\rfloor + \left\lfloor A/p^2 \right\rfloor + \ldots $$

So:

$$\nu_5(2018!)=502, \nu_5(1009!)=250$$ $$\nu_2(2018!)=2011, \nu_2(1009!)=1002$$

So the highest power is $10^4$.

I just tried to solve the problem in my head, and thought of the change-of-coordinate trick within a minute or two (at which point I stopped, knowing that it is only computation starting from there).

To answer your question of "how does one come up with it", let me try to retrace the intuitive process in my mind. I thought roughly as follows:

"OK, so a point on the Euclidean plane is described by a pair of numbers (its coordinates). So a path is a sequence of pairs of numbers. Actually, it looks like the x-coordinate and the y-coordinate do not interact at all here - so we might as well encode paths as pairs of sequences of numbers.

OK, now what are the precise conditions that such a pair of sequences of numbers must satisfy in order to provide a solution?

Answer: $((x_1, \ldots, x_{2018}), (y_1, \ldots, y_{2018}))$ is a valid pair if and only if every term of each sequence is $-1$, $0$, or $1$, the sum of each sequence is $0$, and, for every $i$, $x_i$ and $y_i$ are never simultaneously nonzero exactly one of $x_i$ and $y_i$ is nonzero.

Dang! in fact, it turns out that the two sequences do interact - and in a rather messy way. This last condition seems hard to take into account when solving the problem.

So let us start by solving a simpler problem, which consists of two independent copies of the one-dimensional version of this problem: so let us allow $x_i$ and $y_i$ to take only the values $\pm 1$, but with all four combinations allowed.

Oh wait --- but actually this is the same as the original problem, just rotated 45 degrees (and rescaled)! So here we are."