62. A checker moves from the bottom left corner of a $100 \times 100$ board to the top right corner, moving one cell to the right or one cell up on each step. Let $a$ be the number of paths in which the checker makes exactly 70 steps below the diagonal running from the bottom left corner to the top right corner, and $b$ be the number of paths in which such steps are exactly 110. Which is greater: $a$ or $b ?$

![](https://cdn.mathpix.com/cropped/2024_05_06_9edb286abaeee11d94cfg-1.jpg?height=46&width=186&top_left_y=1739&top_left_x=1780)
62. Answer: $a=b$.

For each $k, 0 \leqslant k \leqslant n$, let $M_{k}$ denote the set of routes the checker can take from the bottom-left to the top-right corner of an $n \times n$ board, making exactly $2 k$ steps below the main diagonal. There is a remarkable fact: for a fixed $n$, all sets $M_{k}$ contain the same number of elements!

This statement is known as the Chang-Feller theorem, first proven by MacMahon in 1909. The combinatorial proof presented below appeared in 1955.

We will establish a one-to-one correspondence between the sets $M_{k}$ and $M_{k+1}, 0 \leqslant k \leqslant n$. A checker's route can be interpreted as a sequence of $2 n$ letters "v" or "p", with an equal number of each. Consider an arbitrary route $a$ from the set $M_{k}$. Write it in the form

$$
a=u \mathbf{B} v \boldsymbol{\Pi} w
$$

where "v" denotes the first move the checker made upwards while on the diagonal; "p" is the move by which it first returned to the diagonal after that; $u$ is a possibly empty sequence of moves the checker made before the move v (these moves were made below the diagonal); $v$ is a possibly empty sequence of moves the checker made after the move v but before the move p (these moves were made above the diagonal); finally, $w$ is all the other moves the checker made.

Corresponding to the route, we assign the following route $b$ from the set $M_{k+1}$:

$$
b=v \boldsymbol{\Pi} u \mathbf{B} w
$$

This correspondence is bijective.