Olympic elementary combinatorics problem

Question

This is a problem taken from the regional selections of the Italian mathematical olympiads:

A knight is placed on the bottom left corner of a $ 3\times3 $ chess board. In how many ways can you move it to the upper right corner in exactly 12 moves?

I've found two different solutions, but both require a few long calculations. The official one is shorter, but a bit difficult to understand. I'm curious to see if there is another nice solution to it, since I find this kind of problem particularly difficult.

Answer 1

A quick -not very elegant- solution:

First, if $k$ is even, after $k$ steps the knight must be on a corner.

Let $\pmatrix{ A_k & B_k \\ C_k& D_k}$ be the number of ways of getting to each corner after step $k$ (even), and $\pmatrix{ A_{k+2} & B_{k+2} \\ C_{k+2}& D_{k+2}}$ the same after $k+2$ steps. Then we have $A_{k+2}=2 A_k+C_k+B_k$ and the same for other corners (multiply by two and add the two adjacent corners). Hence, starting at $k=0$ we have

$$\pmatrix{ 0 & 0 \\ 1& 0} \hspace{1cm} k=0$$ $$\pmatrix{ 1 & 0 \\ 2& 1} \hspace{1cm} k=2$$ $$\pmatrix{ 4 & 2 \\ 6& 4} \hspace{1cm} k=4$$ $$\pmatrix{ 16 & 12 \\ 20& 16} \hspace{1cm} k=6$$ $$\pmatrix{ 64 & 56 \\ 72& 64} \hspace{1cm} k=8$$ $$\pmatrix{ 256 & 240 \\ 272& 256} \hspace{1cm} k=10$$ $$\pmatrix{ 1024 & 992 \\ 1056& 1024} \hspace{1cm} k=12$$

So the solution is $992$.

Alternatively, one could verify that, for $k>0$, $A_k=D_k=2^{k-2}$, $A_k=2^{k-2}+2^{k/2-1}$, $B_k=2^{k-2}-2^{k/2-1}$ is a solution of the recursion; and hence the desired solution is $B_{12}=2^{10}-2^5=992$

Answer 2

The first thing is to draw the graph of possible knight's moves, which turns out to be a cycle of length$~8$, with the two squares in question corresponding to opposite points (at distance $4$). So the question is equivalent to how many walks of length $12$ on a cyclic graph of length$~8$ move to a diametrically opposite point.

The twelve steps must be either clockwise or counterclockwise in the cycle; if we represent them with terms $+1$ and $-1$ respectively, then we are looking for the ordered sums of $12$ such terms whose sums$~s$ satisfies $s\equiv4\pmod8$. With $a$ terms equal to $+1$, and $12-a$ terms equal to $-1$, one gets $s=a-(12-a)=12-2a$, so given $s$ one must have $a=6-s/2$; the number of ways to order those terms is $\binom{12}a=\binom{12}{6-s/2}$. So the number we are after is $$ \sum_{s\equiv4\pmod8} \binom{12}{6-s/2} =\sum_{a\equiv0\pmod4} \binom{12}a = \binom{12}0+\binom{12}4+\binom{12}8+\binom{12}{12} $$ which gives $1+495+495+1= 992$.

Answer 3

Suppose the knight is placed at location c1, then by two moves it can move to a2 then to c3, covering an edge in two moves, which are the shortest possible method of covering an edge. Now in $12$ moves you can cover at max $12/2$ the rest four edges should then only be used to cover the perimeter, reaching the smae point again.Choice of two edges are c1-c3-a3 or c1-a1-a3, now we can choose oneof them in $\binom21=2$.So we can reac c1 to a3 in total 8 ways (wait only four moves/two edges have been utilized). Now you can reach back a block again in moving back and forth with (left,right) or (up,down) in a suitable order if you're at a corner or in 2 possible (from a2-c1-a2 or a2-c3-a2) back and forth knight moves if you're at middle of an edge.Out of the two edges we have moved two positions are at mid and the rest two at corner (leaving the starting block).Now for corners we come back in four moves and for mid we come back in two (with choice of two "to" block)and we're left with 8 moves.

So you need to make sets of moves which are either edge moves or to and fro moves (you first need to caluculate possible to and fro moves) then permute them(you need to consider the blocks where what type of to and fro can be done).