I found many counterexamples to my conjecture, like
- for Case 2 in 7 by 5 grid we have 12, 11 by 5 grid we have 19 and 15 by 5 grid we have 26 filled squares
- for Case 3 in 4 by 10 grid we have 10 filled squares
In a comment by grant93jr following part of of my initial question, to determine the number of squares in grid that can be covered by crosses (x) by following Cross Diagonal Cover Algorithm, was proved:
Given m>n, whenever divides we have filled squares.
Examples of such grids are: 3 by 5, 4 by 7, 4 by 10, ….
Also in that comment it has been suggested that the algorithm terminates after steps where are natural numbers. It is certainly true, but I haven’t been able to use this idea for counting number of filled squares when does not divide since in that case some squares are filled twice.
There is another unexplained observation:
Why no filled square has more than 2 crosses?
Frustrated by so many unanswered questions I started colouring squares, so that number of times I visited a square is not visible. Since I really don’t care about how many times I visited given square while counting the number of filled squares this may help in understanding the underlying symmetry.
After observing above diagrams I suspect that my algorithm leads to a non-deterministic cellular automata.
So, the question which still remains to be answered is:
How many filled squares are there when and does not divide ?
Examples of such grids are: 7 by 5, 11 by 5, 15 by 5 …