Maths Olympiad Prep

Library / /29 of 30

, 2023

Combinatorics Difficulty 9.0 Shortlist Prove it Saudi Arabia

Given is an n×nn \times n board, whose all cells are initially white. Khalid the Painter walks around the board and recolors the visited cells according to the following rules. Each walk of Khalid 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 standing on a black cell, he paints it white and moves one cell to the right (or walks off the board).

Determine the minimum positive integer ss with the following property: after exactly ss walks all the cells of the board will become white again.

Figure 1

Solution

(Base on the solution of Ali Alramdan, IMO 2023's team member)

For two times Khalid visits a square on two different directions, one of them he will go up and go right for the other. Let f(i,j)f(i, j) be the number of time Khalid visited square (i,j)(i, j) so f(0,0)=sf(0, 0) = s for some positive integer ss and
f(i,j)=f(i−1,j)+f(i,j−1)2. f(i, j) = \frac{f(i - 1, j) + f(i, j - 1)}{2}.
By induction on i+ji + j, one can prove that the color of cell (i,j)(i, j) after precisely ss walks is f(i,j) mod 2f(i, j) \bmod 2 where 1 is black and 0 is white. Define g(i,j)=f(i,j)⋅2i+jg(i, j) = f(i, j) \cdot 2^{i+j} for 0≤i,j≤n−10 \le i, j \le n-1, then
g(i,j)=g(i−1,j)+g(i,j−1). g(i, j) = g(i - 1, j) + g(i, j - 1).
Since g(0,0)=f(0,0)=sg(0, 0) = f(0, 0) = s, then base on the Pascal triangle formula, one can get
g(i,j)=s⋅(i+ji)  ⟹  f(i,j)=s⋅(i+ji)2i+j. g(i, j) = s \cdot \binom{i+j}{i} \implies f(i, j) = \frac{s \cdot \binom{i+j}{i}}{2^{i+j}}.
Thus for all squares to be white again, we need to find f(i,j)f(i, j) to be even for all i,j≤n−1i, j \le n-1, or
v2(s)+v2((i+ji))≥i+j+1. v_2(s) + v_2\left(\binom{i+j}{i}\right) \ge i + j + 1.
Now take s=s0=22n−1−v2((2n−2n−1))s = s_0 = 2^{2n-1-v_2\left(\binom{2n-2}{n-1}\right)} which is the smallest positive integer such that f(n−1,n−1)f(n-1, n-1) is even. We will prove that this choice is also such that: f(i,j)f(i, j) are all even for all 0≤i,j≤n−10 \le i, j \le n-1. We deduce to prove for j=n−1j = n-1 since the remaining values can be restore by these values as some linear combinations of even numbers with integer coefficients. Put k=v2((2n−2n−1))k = v_2\left(\binom{2n-2}{n-1}\right) then we need to prove for that
v2((2n−2−in−1))≥k−1,∀i=0,1,…,k. v_2\left(\binom{2n-2-i}{n-1}\right) \ge k-1, \forall i = 0, 1, \dots, k.
Note that
(2n−2−in−1)=(2n−2n−1)⋅(n−1)(n−2)…(n−i)(2n−2)(2n−3)…(2n−1−i) \binom{2n-2-i}{n-1} = \binom{2n-2}{n-1} \cdot \frac{(n-1)(n-2)\dots(n-i)}{(2n-2)(2n-3)\dots(2n-1-i)}
implies that 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
v2((2n−2−in−1))≥v2((2n−2n−1))−⌊i2⌋=k−⌊i2⌋≥k−i. v_2\left(\binom{2n-2-i}{n-1}\right) \ge v_2\left(\binom{2n-2}{n-1}\right) - \left\lfloor \frac{i}{2} \right\rfloor = k - \left\lfloor \frac{i}{2} \right\rfloor \ge k-i.
Therefore, the minimum value of ss is s0s_0 defined as above. ☐

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.