0
$\begingroup$

"A sheet has a height (h) of at least 2 and a width (w) of at least 2. There are (w)x(h) tiles on the sheet. A valid path is one that moves adjacent to the current tile (forward, backwards, left, right, but not diagonal). Show that if either w or h is an even number, then there exists a path (P) that touches every single tile exactly once and ends up at the same tile it started at. Then prove that if both w or h is odd, then this path (P) can not exist."

I'm stumped. I'm not sure how to prove this. I have drawn it out and can see that it holds, but i'm not sure how to prove it generally for any number of w and h. We are told not to use induction on this question, and that was the only method i was thinking could work. Any help would be greatly appreciated.

$\endgroup$
1
$\begingroup$

HINT: When at least one of $w$ and $h$ is even, there is a systematic way to traverse the sheet; try to generalize from this example, in which the bullet points represent square of the sheet.

$$\begin{array}{|c|c|c|} \hline \bullet&\to&\bullet&\to&\bullet&\to&\bullet\\ \uparrow&&&&&&\downarrow\\ \bullet&&\bullet&\leftarrow&\bullet&&\bullet\\ \uparrow&&\downarrow&&\uparrow&&\downarrow\\ \bullet&\leftarrow&\bullet&&\bullet&\leftarrow&\bullet\\ \hline \end{array}$$

For the odd case, imagine coloring the squares alternately black and white, like a checkerboard. Each move must go from a square to a square of the other color. If $w$ and $h$ are both odd, and the square in the upper lefthand corner is white, how many white squares are there? How many black squares?

$\endgroup$
  • $\begingroup$ Would it be because the sheet can be broken down into smaller 2x2 graphs? For the odd case would there be wh/2 white squares? $\endgroup$ – Team. Coco Oct 26 '16 at 19:02
  • $\begingroup$ @Team.Coco: No, because the traversal is possible even when only one of the dimensions is even. The route that I used in the $3\times 4$ example above really does generalize to all sheets with at least one even dimension. Try it first with even widths: start in the upper lefthand corner, go across the top, and then try to generalize what I did. When you have that down, you can go to even heights; that requires turning the pattern sideways. $\endgroup$ – Brian M. Scott Oct 26 '16 at 19:05
  • $\begingroup$ Hmmm. Is that path the ONLY path that could exist for that certain grid? I am having trouble coming up with another. The reason i am having trouble generalizing is because that certain path doesnt exist in a 2x2 grid. Im not sure how to apply that to EVERY grid possible $\endgroup$ – Team. Coco Oct 26 '16 at 19:12
  • $\begingroup$ @Team.Coco: The case in which one dimension is $2$ is a special case that has to be handled separately, but it’s also completely trivial, since you can simply loop around the sheet. What I did generalizes to all sheets with an even dimension $\ge 4$. $\endgroup$ – Brian M. Scott Oct 26 '16 at 19:15
  • $\begingroup$ Thank you. I think i'll be able to solve it now with what you told me. I will mark this as answered, but i might ask a question later tonight if you are still around. $\endgroup$ – Team. Coco Oct 26 '16 at 19:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.