
Problem 6. Given is an integer $n \geq 1$ and an $n \times n$ board, whose all cells are initially white. Peter the painter walks around the board and recolors the visited cells according to the following rules. Each walk of Peter starts at the bottom-left corner of the board and continues as follows:

- if he is standing on a white cell, he paints it black and moves one cell up (or walks off the board if he is in the top row);
- if he is standing on a black cell, he paints it white and moves one cell to the right (or walks off the board if he is in the rightmost column).

Peter's walk ends once he walks off the board. Determine the minimum positive integer $s$ with the following property: after exactly $s$ walks all the cells of the board will become white again.

E.g. for $n=3$ the states of the board after each of the initial five walks will be:
![](https://cdn.mathpix.com/cropped/2024_04_17_ea42bc7e448a11d39c22g-11.jpg?height=142&width=784&top_left_y=888&top_left_x=584)

(Łukasz Bożyk)


Solution. Answer: the highest power of 2 which is a divisor of $2(2 n-2)$ !, i.e. $2^{1+\nu_{2}((2 n-2) !)}$, or equivalently: two to the power $n+\sum_{i=1}^{\infty}\left\lfloor\frac{n-1}{2^{i}}\right\rfloor$, or equivalently: the smallest $s$ such that $\frac{s}{2^{2 n-1}}\left(\begin{array}{c}2 n-2 \\ n-1\end{array}\right)$ is an integer.

Let $\mathbb{N}=\{0,1,2, \ldots\}$. Extend the board to $\mathbb{N} \times \mathbb{N}$ (the full quadrant of the checkered plane), with the bottom-left corner $(0,0)$. The coloring after a fixed number of walks extends naturally to the infinite board as well (each walk is considered to have infinitely many steps $\uparrow / \rightarrow$ ).

For a fixed $s \geq 0$ define the function $f_{s}: \mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{N}$ recursively as follows:

- $f_{s}(x, y)=0$ if $x0$ walks if and only if for each pair $0 \leq x, y<n$ the following inequality holds:

$$
\nu_{2}(s)+\nu_{2}\left(\left(\begin{array}{c}
x+y \\
x
\end{array}\right)\right) \geq x+y+1
$$

Let $s=2^{\left.2 n-1-\nu_{2}\left(\begin{array}{c}(2 n-2 \\ n-1\end{array}\right)\right)}$; it is the smallest positive integer such that $f_{s}(n-1, n-1)$ is even. We will prove that for this choice of $s$ the remaining values of $f_{s}$ in the $n \times n$ square are even as well, and the proof will be concluded. To this end it is enough to show that all the values $f_{s}(x, n-1)$ (in the row $y=n-1$ ) are even (all the remaining terms can be uniquely restored from them by the given recurrence formula, and will be some linear combinations of even numbers with integer coefficients).

Suppose that $\nu_{2}\left(\left(\begin{array}{c}2 n-2 \\ n-1\end{array}\right)\right)=k$. The proof will be finished if we show that for each $i=0,1, \ldots, k$ we have

$$
\nu_{2}\left(\left(\begin{array}{c}
2 n-2-i \\
n-1
\end{array}\right)\right) \geq k-i \text {. }
$$

But this is clearly true since

$$
\left(\begin{array}{c}
2 n-2-i \\
n-1
\end{array}\right)=\left(\begin{array}{c}
2 n-2 \\
n-1
\end{array}\right) \cdot \frac{(n-1)(n-2) \ldots(n-i)}{(2 n-2)(2 n-3)(2 n-4) \ldots(2 n-1-i)}
$$

and each even term of the product in the denominator of the fraction has its corresponding half in the numerator, so it could eat at most one 2 from the prime factorization, hence

$$
\nu_{2}\left(\left(\begin{array}{c}
2 n-2-i \\
n-1
\end{array}\right)\right) \geq \nu_{2}\left(\left(\begin{array}{c}
2 n-2 \\
n-1
\end{array}\right)\right)-\left\lceil\frac{i}{2}\right\rceil=k-\left\lceil\frac{i}{2}\right\rceil \geq k-i
$$


[^0]:    ${ }^{1}$ Here, $D(n)$ denotes the set of all positive divisors of a positive integer $n$.

