B4. An ant walks from the bottom left corner of a $10 \times 10$ square grid to the diagonally-opposite corner, always walking along grid lines and taking as short a route as possible. Let $N(k)$ be the number of different paths that ant could follow if it makes exactly $k$ turns. Find $N(6)-N(5)$.
Solution: These paths are parameterized by their starting direction (north or east) and the lengths of all northward or eastward segments $\left\{a_{j}, j=1, \ldots, k+1\right\}$, which must sum to 10 in each direction. The number of segments is one more than the number of turns, so for $k=5$ we have $a_{1}+a_{3}+a_{5}=10$ and $a_{2}+a_{4}+a_{6}=10$ and for $k=6$ we have $a_{1}+a_{3}+a_{5}+a_{7}=10$ and $a_{2}+a_{4}+a_{6}=10$. Sample paths starting east with 6 and 5 turns respectively are shown below:
Let $P_{\ell}$ be the number of positive integer solutions to the equation $b_{1}+b_{2}+\cdots+b_{\ell}=10$. It is easy to see that $P_{\ell}=\binom{9}{\ell-1}$ because there are $10-1=9$ spaces in a row between 10 objects, and we pick $\ell-1$ of them to place a delimiter; the number of objects between two adjacent delimiters are $b_{i}$ respectively.
We need $P_{3}=\binom{9}{2}=36$ and $P_{4}=\binom{9}{3}=84$.
Then the desired number of paths is $N(5)=2 P_{3} P_{3}=2592$ and $N(6)=2 P_{3} P_{4}=6048$.
The factor of 2 accounts for the option to begin either to the north or east.
Thus, $N(6)-N(5)=2 P_{3}\left(P_{4}-P_{3}\right)=2 \times 36 \times(84-36)=3456$.
Alternative solution: After fixing the initial direction, the set of rows and set of columns we 'turn onto' uniquely determine the walk. For example, if the first step is horizontal, then for $k$ even the last step must be horizontal, which means that the we are forced to choose the last row as one of the rows that we 'turn into'. Similarly, when $k$ is odd, we are forced to turn into the last column. Thus, there are $\binom{n-1}{$ floor ((k-1)/2) } possible sets of rows and $\binom{n-1}{$ ceiling((k-1)/2) } sets of columns.
Then we double the result to account for the other initial direction.
In our case $n=10$ and $k=6$ or $k=5$, so
$$
N(6)-N(5)=2\binom{9}{2}\binom{9}{3}-2\binom{9}{2}\binom{9}{2}=2 \times 36 \times(84-36)=3456 \text {. }
$$

Answer: 3456