I will continue the previous post. Now the question to be answered is that:

What percentage (or how many) of given grid can be covered by following Cross Diagonal Cover Algorithm?

I did some calculations, for example:

As per my calculations, I have following conjecture:

The following 3 cases are possible:

- If , then squares will be covered.
- If and both are odd, then squares will be covered.
- If at least one of is even then squares will be covered.

As you can see that Case – 1 is quite trivial. I tried to prove other two cases for one week, but failed, so decided to post it as conjecture.

Advertisements

Pingback: Cross Diagonal Cover – V | Gaurish4Math

Pingback: Cross Diagonal Cover – III | Gaurish4Math

Hi Gaurish

I am afraid I believe I have a couple of counter examples to your conjectures. For case 2 I believe a 5 by 7 board will result in 12 squares being covered and for case 3 I believe a 4 by 7 board will result in only 7 squares being covered.

I think the result has something to do with the greatest common divisor of (m-1) and (n-1). I believe this because of the number of steps after which we are in an edge square. Assuming m >= n at step 0 we start in the top left hand corner and have covered 1 square. After n-1 steps we are adjacent to one of the horizontal edges and again after a further n-1 steps and so on. Also after m-1 steps we are adjacent to one of the vertical edges and again after a further m-1 steps and so on. The algorithm terminates when it reaches a corner. That is to say when we are adjacent to both a vertical edge and a horizontal edge. Thus the algorithm terminates after k(m-1) = l(n-1) steps where k and l are natural numbers. Thus if (n-1) divides (m-1) then the algorithm terminates after m-1 steps and m squares have been covered.

The above is probably not formal enough to be a proof but I think the ideas could be extended to get a complete set of results for your problem.

Hope that helps. Also I enjoy this blog thank you.

LikeLike

Thanks for your comments!

Yes, I also found counter examples to case 2 and case 3 of my conjecture, within a day of posting it, but was working on alternate formulations.

For Case 2 (when both m and n are odd): in 7×5 we have 12, 11×5 we have 19 and 15×5 we have 26 filled squares. My conjecture holds for 9×5 and 3×5.

For Case 3 (when at least one side is even number)in 4×10 we have 10 filled squares. My conjecture holds for 10×5 and 12×10.

I think that my algorithm is a non-deterministic cellular automata, I.e. one can’t find a general rule for outcomes.

Currently I am working with it’s group theoretic formulation (symmetry arguments) and gcd argument.

Your gcd argument, which is actually lcm argument, has given me a better understanding of my algorithm. Since for 5×7 LCM(5-1, 7-1) = 12. but again this doesn’t seem to work for 4×7, LCM(4-1, 7-1) = 6

I suspect that I can’t find a way to count the number of cross filled squares by this argument.

LikeLike