Wednesday, August 6, 2008

How Many Ways?

So, given this picture of four rooms interlinked by pink gates or doors, do you think you can find a route through the doors such that you pass through every door only once? Or do you think there's no such route?


Well, Luoning nailed down the essence of my explanation; basically, it's got to do with the number of entrances to each room you see in the picture above. To facilitate the explanation, let me redraw the network of rooms above as such:

Notice I've represented each room by a black dot, which I shall now refer to as a node; so there's nodes A, B, C and D, each representing the rooms. Now, notice each node has lines connecting it to other nodes - these lines represent the doors or entrances leading from one room to another room.

Looking at this diagram, you'll find that it's much more easier to figure out possible routes.

So what did Luoning say again? Ah yes, the even or odd number of entrances! Indeed! Ask yourself what it means to be able to trace out a path where you don't re-use an entrance: this means that you must be able to arrive at the room the same number of times as you leave the room.

For you to arrive at the room the same number of times as you leave the room, one obvious condition is needed: you need each room to have an even number of entrances. Try it!

Of course, there is another condition: you could also have two rooms having an odd number of entrances but of course you need these rooms to be directly linked to one another as well. The direct linkage of these two rooms then means that the two rooms can be visualised as one big room and therefore reduces the number of effective entrances by one, turning an odd number of entrances into an even number of entrances!

Well I didn't think of this myself, but I did think of how to put forward this explanation myself! So give me some credit, won't ya? Haha.

So for this problem, of course no single route can be found! :)

[Edit: Hmm, this post isn't that well explained - I'll come back to this once I've figured out Graph Theory for myself!]

No comments: