# Cross Diagonal Cover – V

Standard

This has been an exciting week! Prof. Sukanta Pati proved an interesting theorem that enables us to get decomposition of $2m-1\times n$ grids into simpler grids, hence simplifying counting to large extent (note that $m=n$ is also allowed). It enables us to surpass the difficulty posed by “more than two crosses in one square”, thus supporting the idea of colouring (i.e. not giving importance to two crosses in a square).

Given $\dpi{300}\inline m\times n$ grid which has consisting of $\dpi{300}\inline m$ rows and $\dpi{300}\inline n$ columns such that the terminating corner square lie in $\dpi{300}\inline m^{th}$ row. Let the number of covered squares in $\dpi{300}\inline m\times n$ grid be $\dpi{300}\inline C(m,n)$ . Then for  $\dpi{300}\inline 2m-1\times n$ grid we have $\dpi{300}\inline C(2m-1, n)= 2C(m,n)-\beta(m,n)$  where $\dpi{300}\inline \beta(m,n)$ is the number of covered squares in $\dpi{300}\inline m^{th}$ row of $\dpi{300}\inline m\times n$ grid.

Instead of giving its proof, I will give an  example when $m=5, n=10$.

I omitted the repetitions of crosses (x) since the number of x in each square doesn’t matter. Note that if we reflect 5×10 about the middle of 5th row we will get 9×10.

Here, $C(5,10) = 25$ and $C(9,10) = 2\times 25 - 5 = 45$. Using this example you can easily prove the generalized statement by exploiting the bilateral symmetry of grid and x about ythe dotted line.

Though  I suspected that least common multiple of $m-1, n-1$ determine the number of steps my algorithm evaluates, Pritam Laskar  found the exact formula.

Given a $m\times n$ grid, the Cross Diagonal Cover algorithm terminates after  $lcm(m-1, n-1) + 1$  steps.

For proof, follow the arguments of grant93jr in his/her comment (he/she mistakenly called their lcm to be their gcd).

Using the SageMath Program, about which I wrote in previous post, I am pretty sure that $\gcd(m,n)$ always divides the number of filled squares. So, now the question is

Why the greatest common divisor of m and n always divides the number of filled squares?