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."

A good idea for whenever you don't know how to start a combinatorics problem that asks you to compute something for a very high integer (in this case, 2018) is to compute some small cases and look for a pattern. To get started on this one, note that the number of paths of length $n$ to any given point is the sum of paths of length $n-1$ to it's neighboring points. This makes it easy to compute small cases:

n=0                         
                1           
n=1                         
                1           
            1       1       
                1           
n=2                         
                1           
            2       2       
        1       4       1   
            2       2       
                1           
n=3                         
                1           
            3       3       
        3       9       3   
    1       9       9       1
        3       9       3   
            3       3       
                1            

See the pattern yet? The edges are rows of Pascal's triangle, and the inner diagonals are just multiples of the same row of Pascal's triangle. Prove this by induction. The middle element (for even numbers $n$ of steps) will be just the square of the central binomial coefficient $\binom{n}{n/2}^2$. Evaluate the pattern for $n=2018$, look for the highest power of $5$, and you've got your answer.

I see mention of a coordinate change in several answers and comments. From the pictures above, it's clear why that might be a good idea. However, I think it's not really necessary once you see the pattern.

Commentary: Since the OP is interested in problem solving strategies, one minor metaprinciple I would mention is that binomial coefficients and Pascal's triangle come up a lot in lattice path problems, so it is well advised to be expecting them. Another neat example (actually two examples, which closely related to each other) are the Catalan numbers and Bertrand's ballot theorem, which I would highly recommend studying for anyone interested in competition math.