Cross Diagonal Cover – III


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 m\times n grid that can be covered by crosses (x) by following Cross Diagonal Cover Algorithm, was proved:

Given m>n, whenever n-1 divides m-1 we have m 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 k(m-1) = l(n-1) steps where k, l are natural numbers. It is certainly true, but I haven’t been able to use this idea for counting number of filled squares when n-1 does not divide m-1 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.

New Doc 21_1

Replacing cross (x) by any colour and applying Cross Diagonal Cover Algorithm

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  m>n and n-1 does not divide m-1 ?

Examples of such grids are: 7 by 5, 11 by 5, 15 by 5 …



2 responses »

  1. Pingback: Cross Diagonal Cover – IV | Gaurish4Math

Leave a Reply

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

You are commenting using your 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