# Homework Help: Tour Problem

1. Mar 28, 2013

### AUCTA

1. The problem statement, all variables and given/known data

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.

2. Relevant equations

No idea.

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

2. Mar 28, 2013

### 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?

3. Mar 28, 2013

### AUCTA

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

4. Mar 28, 2013

### Sunil Simha

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

5. Mar 28, 2013

### AUCTA

The colors change. From black to white.

6. Mar 28, 2013

### 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?

7. Mar 28, 2013

### AUCTA

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

8. Mar 28, 2013

### 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?

9. Mar 28, 2013

### AUCTA

How do I calculate parity?

10. Mar 28, 2013

### Sunil Simha

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

11. Mar 28, 2013

### AUCTA

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

12. Mar 28, 2013

### Sunil Simha

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

13. Mar 28, 2013

### 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?

14. Mar 28, 2013

### Sunil Simha

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)

15. Mar 28, 2013

### AUCTA

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

16. Mar 28, 2013

### 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 )