This has been an exciting week! Prof. Sukanta Pati proved an interesting theorem that enables us to get decomposition of grids into simpler grids, hence simplifying counting to large extent (note that 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 grid which has consisting of rows and columns such that the terminating corner square lie in row. Let the number of covered squares in grid be . Then for grid we have where is the number of covered squares in row of grid.

Instead of giving its proof, I will give an example when .

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, and . 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 determine the number of steps my algorithm evaluates, Pritam Laskar found the exact formula.

Given a grid, the Cross Diagonal Cover algorithm terminates after 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 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?

### Like this:

Like Loading...

*Related*

Pingback: Cross Diagonal Cover – VI | Gaurish4Math