Proving the Existence/Non-Existence of a Grid Tour

[AUCTA]

Homework Statement

Consider a grid with height p >= 2 and width q >= 2, so there are pq squares in the grid. A valid walk on the grid is a walk that starts on one square and subsequently moves to adjacent squares (you cannot move diagonally). Define a tour to be a valid walk on the grid that touches each and every square exactly once and begins and ends on the same square. First show that if either p or q is even then there exists a tour. Prove that if p and q are odd, there does not exist a tour.

Homework Equations

No idea.

The Attempt at a Solution

No induction. I have no idea how to go about this proof. I would love some guidance on how to get started.

 

[Sunil Simha]

Hello AUCTA,

I cannot help you guarantee a tour if p or q are even but I can definitely help you show that a tour is non existent for both p and q being odd.

Firstly, color your grid like a chess board i.e. alternative black and white. Once you have done that, think about how many steps must you take on a tour?

 

[AUCTA]

Since a tour is all squares, then it is pq.

 

[Sunil Simha]

Yes that is correct. Now what happens to the color of the square as you take each step?

 

[AUCTA]

The colors change. From black to white.

 

[Sunil Simha]

Correct again, So how is the color of the square you are on (after the taking the first step) depend on the number of steps you take?

 

[AUCTA]

0, 2, 4, 6, ... (all the even number of steps) have the same color and all the odds have the same color.

 

[Sunil Simha]

Okay, Think about it like this: From the first square (assuming black), what would be the color of the square you are on after
a)even number of steps and
b)Odd number of steps

Once you figure that out, what should be the parity of the number of steps you must take to complete a tour?

 

[AUCTA]

How do I calculate parity?

 

[Sunil Simha]

Parity (in this case) means whether the number is even or odd.

 

[AUCTA]

Well the parity must be even for a tour to be able to be completed.

 

[Sunil Simha]

Well the parity must be even for a tour to be able to be completed.

Bingo. You have the desired result!
What does this tell about p and q?

 

[AUCTA]

Then they must be both even. But my question is, how can I proof that the parity must be even. I just said it because I did a few examples and it made sense. But how do you actually know it must be even?

 

[Sunil Simha]

Then they must be both even. But my question is, how can I proof that the parity must be even. I just said it because I did a few examples and it made sense. But how do you actually know it must be even?

It is sufficient if one is even.

As for the parity; If you start on a black square, you must end on a black square right? So what will be the parity of the number of steps?

(go back to post#8, first question for a hint)

 

[AUCTA]

Ah it makes sense now. Thanks a lot Sunil, you have helped me greatly.

 

[Sunil Simha]

You are welcome.

Did you get any lead on proving the other part of the question?
(draw some grids and see if there can be a general method to tour )