Browse · MathNet
PrintSAUDI ARABIAN IMO Booklet 2023
Saudi Arabia 2023 counting and probability
Problem
Given is an 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 with the following property: after exactly walks all the cells of the board will become white again.
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 with the following property: after exactly walks all the cells of the board will become white again.
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 be the number of time Khalid visited square so for some positive integer and By induction on , one can prove that the color of cell after precisely walks is where 1 is black and 0 is white. Define for , then Since , then base on the Pascal triangle formula, one can get Thus for all squares to be white again, we need to find to be even for all , or Now take which is the smallest positive integer such that is even. We will prove that this choice is also such that: are all even for all . We deduce to prove for since the remaining values can be restore by these values as some linear combinations of even numbers with integer coefficients. Put then we need to prove for that Note that 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 Therefore, the minimum value of is defined as above. ☐
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 be the number of time Khalid visited square so for some positive integer and By induction on , one can prove that the color of cell after precisely walks is where 1 is black and 0 is white. Define for , then Since , then base on the Pascal triangle formula, one can get Thus for all squares to be white again, we need to find to be even for all , or Now take which is the smallest positive integer such that is even. We will prove that this choice is also such that: are all even for all . We deduce to prove for since the remaining values can be restore by these values as some linear combinations of even numbers with integer coefficients. Put then we need to prove for that Note that 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 Therefore, the minimum value of is defined as above. ☐
Final answer
s = 2^{2n - 1 - v_2\big(\binom{2n - 2}{n - 1}\big)}
Techniques
Recursion, bijectionInvariants / monovariantsAlgebraic properties of binomial coefficientsFactorization techniques