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

I have a 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.

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

### Like this:

Like Loading...

*Related*

Pingback: Cross Diagonal Cover – II | Gaurish4Math

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.

LikeLike

This won’t work. I am trying to answer a closely related question for next post 🙂

LikeLiked by 1 person

Ok, looking forward!

LikeLiked by 1 person