I was doing question 6 from this BMO1 paper: https://bmos.ukmt.org.uk/home/bmo1-2019.pdf and I didn't manage to get it. Then I looked at the solution and found the solution. I can see how the solution works but there is a step that I cannot see how anyone would have ever thought to have tried. I'm trying to improve at problem solving so I'd like to know how I would be supposed to think of something like that.
Ada the ant starts at a point $O$ on a plane. At the start of each minute she chooses North, South, East or West, and marches $1$ metre in that direction. At the end of $2018$ minutes she finds herself back at $O$. Let $n$ be the number of possible journeys which she could have made. What is the highest power of $10$ which divides $n$.
(READ FULL QUESTION BEFORE GOING TO VIDEO) Here is the video solution: https://bmos.ukmt.org.uk/solutions/bmo1-2019/ The step I am confused about how someone could think of it is the part at 4:15 in the solution video. How is someone meant to think of creating a new set of coordinates ((x + y), (x – y))? I just can't see how you would make that jump or even think to try that. If you want to try the problem yourself first, maybe you will be more able to explain to me how you realised that you needed to make that step however if you want you can just look at the video solution.
Best Answer
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.