Question

A museum is in the shape of a square with six rooms to a side; the entrance and exit are at diagonally opposite corners. Each pair of adjacent rooms is joined by a door. Some very efficient tourists would like to tour the museum by visiting each room exactly once.

Prove that the tour is impossible. Imagine that the rooms are colored black and white like a checkerboard.

a) Show that the room colors alternate between white and black as the tourists walk through the museum.

b) Use part a & the fact that there are an even # of rooms in the museum to conclude that the tour cannot end @ the exit

Answer 1

Any ideas on how I would go about proving this?

Answer 2

its really hard to picture what they are describing. But it seems like they want you to say something like, "The tour is impossible because if you start in a "white room" you will finish in a "black room" which isnt the exit" or something like that. But without a clear picture im lost.

Answer 3

Sounds like u have to show if u represent your set up as a graph, there is no Hamiltonian cycle (like the famous Konigsberg bridges problem).

http://en.wikipedia.org/wiki/Hamiltonian_path

U need to use the properties7theorems possibly together with some thinking to resolve the question.

Like Joe, I am having a hard time drawing what u describe.

Answer 4

It's like a checkerboard. A square - the museum - with 6 squares on each side for a total of 36 squares. Each square is a room. the entrance is in the top left room. the exit is in the bottom right room. So basically I need to prove that you can get from the top left corner to the bottom right corner going through each room once. if that helps....

Answer 5

Doesn't help me, don't know about joe.

How do you get in and out of each room?

Why can't you just walk round a row at a time?

Answer 6

Ah, i see it now. you have this checkerboard type structure, 6 by 6 (for 36 rooms), the start is in one corner, and the exit is in the opposite corner, and the question is, "by going up, down, left or right, is it possible to get from the start to the finish only touching each square once?"
The answer is no. and the logic behind it has to do with the color of the floors. First, we note that the start and the finish have the same color. They will either both be black, or both be white. Second, if a person starts on one color (black or white), and travels through an odd number of rooms other than the room he started with, he will always end up in a room with the opposite color floor. Then all we have to say to prove out statement is that if someone wanted to visit all the rooms once with the finish being the last room, the color of the floor would have to be the opposite of whatever color he started on because he will travel through 35 rooms, but the start and finish have same color floor, therefore its impossible.

Answer 7

Yes! That's exactly it. thank you :)