1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Tour Problem

  1. Mar 28, 2013 #1
    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. jcsd
  3. Mar 28, 2013 #2
    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?
  4. Mar 28, 2013 #3
    Since a tour is all squares, then it is pq.
  5. Mar 28, 2013 #4
    Yes that is correct. Now what happens to the color of the square as you take each step?
  6. Mar 28, 2013 #5
    The colors change. From black to white.
  7. Mar 28, 2013 #6
    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?
  8. Mar 28, 2013 #7
    0, 2, 4, 6, ... (all the even number of steps) have the same color and all the odds have the same color.
  9. Mar 28, 2013 #8
    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?
  10. Mar 28, 2013 #9
    How do I calculate parity?
  11. Mar 28, 2013 #10
    Parity (in this case) means whether the number is even or odd.
  12. Mar 28, 2013 #11
    Well the parity must be even for a tour to be able to be completed.
  13. Mar 28, 2013 #12
    Bingo. You have the desired result!
    What does this tell about p and q?
  14. Mar 28, 2013 #13
    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?
  15. Mar 28, 2013 #14
    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)
  16. Mar 28, 2013 #15
    Ah it makes sense now. Thanks a lot Sunil, you have helped me greatly.
  17. Mar 28, 2013 #16
    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 )
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted