Cross Diagonal Cover – II

Standard

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

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

I did some calculations, for example:

 

New Doc 16_1

As per my calculations, I have following conjecture:

The following 3 cases are possible:

  1. If m = n, then m squares will be covered.
  2. If m>n and both m,n are odd, then m squares will be covered.
  3. If at least one of m,n is even then \frac{mn}{2} 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

4 responses »

  1. Pingback: Cross Diagonal Cover – V | Gaurish4Math

  2. Pingback: Cross Diagonal Cover – III | Gaurish4Math

  3. 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.

    Like

    • 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.

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s