Motivation for this solution to a British olympiad problem

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

Let the no. of $N$ moves $= S$ moves $=k $ and $E$ moves $= W$ moves $=1009-k $. Clearly grouping $k$ with $k$ will be messy so lets group $k$ with $1009-k$. So lets just pick $1009 ([k]+ [1009-k])$ moves for N and E and the remaining $1009$ will correspond for S and W. Clearly, there is${2018\choose 1009}$ ways of doing this.

Now, we have selected $1009$ for N and E and $1009$ for S and W. Now we only need to see in each of these groups which positions are for which direction. Let us find the no. of ways to pick the exact positions of N and W among each of the groups of $1009$ and the remaining positions will be filled by E and S in the respective groups. Since, there are a total of $2018$ positions and we are choosing $([k]+ [1009-k])= 1009$ , the no. of ways we can do this is:

$${2018\choose 1009}$$

Now we need to just multiply this by our initial ways of separating $2018$ into the groups of $1009$ for both sets.

Thus our Final Answer would be : $${{2018\choose 1009}}^2$$

Answer 6

Similar to the other answers above, but a slightly more explicit counting approach to the above; also tried to explain everything fully for complete clarity, including links to useful resources.

Let $x_{N}=$ no. of north moves, and $x_{S},x_{W},x_{E}$ be defined similarly. As she returns to O in 2018 moves, her displacement is 0m and so $x_N=x_S, \ x_W=x_E.$ Also, $\ x_N+x_{S}+x_{W}+x_{E}=2018$ as that is the total no. of moves. If $x_N=x$ say, it must then follow that $x_S=x$ and that $x_W=\frac{1}{2}(2018-2x)=1009-x=x_E$. Note that $x$ cannot exceed 1009, as it is clear that $$ x_W=x_E \geqslant 0, \ x_N=x_S \geqslant 0 \\\iff \ 1009-x\geqslant 0, \ x \geqslant 0 \\\iff 0\leqslant x\leqslant1009 \ \blacksquare $$ For some given $x$ in the established interval, we can arrange the order in which the moves are made in multiple different ways (that's the question lol). Consider the general arrangement $\underbrace{NN\ldots N}_{x}\underbrace{SS\ldots S}_{x}\underbrace{WW\ldots W}_{1009-x}\underbrace{EE\ldots E}_{1009-x}$.

There are $2018!$ ways to arrange the above. However, in any given arrangement, we will be overcounting due to repetition of the same symbol (N, S, W, E occur multiple times as shown), as you could arrange within any one of the 4 symbols any way you like and obtain the same initial arrangement (intuitively, swap any of the 2 E's and you can't notice a dfference). So to only count each such arrangement once, we must divide $2018!$ by the number of possible rearrangements of each symbol in the above arrangement. Therefore there are $$ \dfrac{2018!}{x!x!(1009-x)!(1009-x)!}=\dfrac{2018!}{x!^2(1009-x)!^2} $$ total ways to arrange a general arrangement above. Now, to determine $n$ all that is required is to sum the expression just found over all integers such that $0\leqslant x \leqslant 1009$. $$ \begin{align} \therefore n &= \sum_{x=0}^{1009} \dfrac{2018!}{x!^2(1009-x)!^2} \\ &= \dfrac{2018!}{1009!^2} \sum_{x=0}^{1009} \dfrac{1009!^2}{(x!(1009-x)!)^2} \\ &= \binom{2018}{1009} \sum_{x=0}^{1009} \binom{1009}{x}^2 \end{align} $$ To help evaluate the remaining sum, by the binomial theorem, we get $(1+x)^\gamma=\displaystyle\sum_{k=0}^{\gamma}\binom{\gamma}{k}x^k\implies (1+x)^{2\gamma}=\displaystyle\sum_{k=0}^{2\gamma}\binom{2\gamma}{k}x^k$ but $$ \begin{align} (1+x)^{2\gamma}&=((1+x)^\gamma)^2 \\\implies \displaystyle\sum_{k=0}^{2\gamma}\binom{2\gamma}{k}x^k &=\left(\displaystyle\sum_{k=0}^{\gamma}\binom{\gamma}{k}x^k\right)^2 \end{align} $$ consider the coefficient of $x^\gamma$ on the left and right: $$ \begin{align} \binom{2\gamma}{\gamma} &= \binom{\gamma}{0}\binom{\gamma}{\gamma}+\binom{\gamma}{1}\binom{\gamma}{\gamma-1}+\ldots +\binom{\gamma}{\gamma-1}\binom{\gamma}{1}+\binom{\gamma}{\gamma}\binom{\gamma}{0} \\ &= \sum_{k=0}^\gamma \binom{\gamma}{k}\binom{\gamma}{\gamma-k} \\ &= \sum_{k=0}^\gamma \binom{\gamma}{k}\binom{\gamma}{k} \\ &= \sum_{k=0}^\gamma \binom{\gamma}{k}^2 \end{align} $$ This is actually a special case of a common combinatorial identity, known as Vandermonde's identity, which can be proven similarly. So now, we know that $\displaystyle \sum_{x=0}^{1009}\binom{1009}{x}^2=\binom{2(1009)}{1009}=\binom{2018}{1009}$.

$$ \therefore n = \binom{2018}{1009}^2 $$

To obtain the final answer, finding how many times 10 divides $n$, we need to find the number of times BOTH 2 and 5 divide $n$ as $10=2\times5$. Using p-adic valuation, this number will just be $$ \begin{align} \min\{\nu_2(n),\nu_5(n)\} &=\min\left\{\nu_2\left( \binom{2018}{1009}^2\right),\nu_5\left( \binom{2018}{1009}^2\right)\right\} \\ &= \min\left\{2\nu_2\left( \binom{2018}{1009}\right),2\nu_5\left( \binom{2018}{1009}\right)\right\} \end{align} $$ We have that, by Legendre's theorem (line 4) $$ \begin{align} \\\nu_2\left(\binom{2018}{1009}\right) &= \nu_2\left(\frac{2018!}{(1009!)^2}\right) \\ &= \nu_2(2018!)-\nu_2((1009!)^2) \\ &= \nu_2(2018!)-2\nu_2(1009!) \\ &= \sum_{k=1}^{\infty} \left\lfloor\dfrac{2018}{2^k}\right\rfloor-2\sum_{k=1}^{\infty} \left\lfloor\dfrac{1009}{2^k}\right\rfloor \\ &= \sum_{k=1}^{10} \left\lfloor\dfrac{1009}{2^{k-1}}\right\rfloor-2\sum_{k=1}^{9} \left\lfloor\dfrac{1009}{2^k}\right\rfloor \\ &= \sum_{k=0}^{9} \left\lfloor\dfrac{1009}{2^k}\right\rfloor-2\sum_{k=1}^{9} \left\lfloor\dfrac{1009}{2^k}\right\rfloor \\ &= \left\lfloor \dfrac{1009}{2^0} \right\rfloor-\sum_{k=1}^{9} \lfloor2^{10-k}-2^{4-k}+2^{-k}\rfloor \\ &= 1009-\sum_{k=1}^{9} \lfloor2^{10-k}-2^{4-k}\rfloor \\ &= 1009-\sum_{k=1}^{4} (2^{10-k}-2^{4-k})-\sum_{k=5}^{9} (2^{10-k}-1) \\ &= 1009-\sum_{k=1}^{9} 2^{10-k}+\sum_{k=1}^{4} 2^{4-k}+\sum_{k=5}^{9} 1 \\ &= 1009-\sum_{k=1}^{9} 2^{k}+\sum_{k=1}^{4} 2^{k}+5 \\ &= 1014-\dfrac{2(2^9-1)}{2-1}+\dfrac{2(2^4-1)}{2-1} \\ &= 1014+2-2^{10}+2^5-2 \\ &=1014-1024+32 \\ &= 22 \end{align} $$ and that $$ \begin{align} \\\nu_5\left(\binom{2018}{1009}\right) &= \nu_5\left(\frac{2018!}{(1009!)^2}\right) \\ &= \nu_5(2018!)-\nu_5((1009!)^2) \\ &= \nu_5(2018!)-2\nu_5(1009!) \\ &= \sum_{k=1}^{\infty} \left\lfloor\dfrac{2018}{5^k}\right\rfloor-2\sum_{k=1}^{\infty} \left\lfloor\dfrac{1009}{5^k}\right\rfloor \\ &= \sum_{k=1}^{4} \left\lfloor\dfrac{2018}{5^{k}}\right\rfloor-2\sum_{k=1}^{4} \left\lfloor\dfrac{1009}{5^k}\right\rfloor \\ &= 403+80+16+3-2(201+40+8+1) \\ &= 502-500 \\ &=2. \end{align} $$

So finally, we get the desired answer as $$ \begin{align} \min\{\nu_2(n),\nu_5(n)\} &=\min\{2(22),2(2)\} \\ &= 4 \end{align} $$