Cross Diagonal Cover – I

Standard

While doodling in my college classes, I designed an algorithm which I called Cross Diagonal Cover Algorithm:

I have a m\times n rectangle divided into unit squares. I start by placing a x (cross) in leftmost corner. Every time I visit a square in diagonal direction I place a  x in the squares till I reach any boundary of rectangle, from where I switch to adjacent diagonal.

New Doc 17_1

Illustrating the algorithm… Follow the arrow numbers to fill the grid.

Please note that it doesn’t matter that how many x (cross) are there in each square. The number of x (cross) in each square just signify number of times I visited that square while executing the algorithm.

Then I asked myself the following question:

Can I cover whole grid with at least one x in each unit square?

The answer to my above question is NO! The proof is pretty easy.

If m=n then it’s trivial that I can’t cover the whole grid with x since I will  be tracing the main diagonal again and again.

Moreover, the key observation here is that I will be stuck in loop (which can’t cover whole grid) whenever I reach another corner of the grid since it supports only one diagonal. Since I want to cover whole grid I must visit all the corners but they are dead ends!

Quod Erat Demonstrandum.

Any references about this idea from literature would be appreciated. I am working on a better question on “Cross Diagonal Cover Algorithm”, which I will discuss in next post.

Advertisements

4 responses »

  1. Pingback: Cross Diagonal Cover – II | Gaurish4Math

  2. It seems you need to do it twice (upper left and bottom left) and then you would cover it whole though I do not know if it is true and I have no idea how to make a proof of that.

    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