wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> A tourist problem
        
(Message started by: Cool_Joh on Aug 10^th, 2007, 6:44pm)

Title: A tourist problem
Post by Cool_Joh on Aug 10^th, 2007, 6:44pm

A tourist left his hotel and walked all around a city for a whole day. After having supper, he decided to return to his hotel, going along streets that he had already travelled on an uneven number of times ONLY. Prove that this can always be done.

Title: Re: A tourist problem
Post by mikedagr8 on Aug 11^th, 2007, 6:20am

Because he can always walk on the streets only once, hence an uneven number?

Title: Re: A tourist problem
Post by ThudanBlunder on Aug 11^th, 2007, 6:44am

on 08/11/07 at 06:20:39, mikedagr8 wrote:

Because he can always walk on the streets only once, hence an even number?

It is related to the Konigsberg Bridge Problem (http://www.google.co.uk/search?hl=en&client=firefox-a&rls=org.mozilla:en-GB:official&hs=twq&sa=X&oi=spell&resnum=0&ct=result&cd=1&q=konigsberg+bridge+problem&spell=1).

Title: Re: A tourist problem
Post by mikedagr8 on Aug 11^th, 2007, 6:46am

Is that the 7 bridges problem, my net is stuffed so i can't look it up.

Title: Re: A tourist problem
Post by ThudanBlunder on Aug 11^th, 2007, 6:54am

on 08/11/07 at 06:46:03, mikedagr8 wrote:

Is that the 7 bridges problem, my net is stuffed so i can't look it up.

That's the one.

Title: Re: A tourist problem
Post by mikedagr8 on Aug 11^th, 2007, 6:56am

In that though, they can never travel on all of the bridges, how does this relate?

Title: Re: A tourist problem
Post by rmsgrey on Aug 11^th, 2007, 10:32am

Key observation (cf Konigsberg bridges):
[hideb]
For each intersection (except the start and end locations) the tourist must have left that intersection each time he arrived at it, so summing the number of times each street meeting there has been traversed will always give an even total.

The start and end (unless they're the same place) must each have an odd total.
[/hideb]

Note that, in real life, things may not work out so well - for example, if I were to wander around town here for a while, there are several places where I can leave the streets at one location, and rejoin at another. To further complicate things, many of these shortcuts close overnight.

Title: Re: A tourist problem
Post by mikedagr8 on Aug 11^th, 2007, 4:40pm

Thankyou rmsgrey for the explanation and clever problems in real life it may cause.

Title: Re: A tourist problem
Post by Grimbal on Aug 12^th, 2007, 2:22am

Of course, the tourist might have trouble with one-way streets (or one-way gates for pedestrians).

Title: Re: A tourist problem
Post by Cool_Joh on Aug 15^th, 2007, 6:43am

okay, now can someone explain it clearly to me in simple english? i still don't get it..

Title: Re: A tourist problem
Post by Barukh on Aug 17^th, 2007, 11:18pm

Seems like nobody has answered Cool_Joh question?

Following rmsgrey’s observation, let’s associate a counter with every street, and with every street intersection as follows:

1. At the beginning (while the tourist is at the hotel), all the counters are 0.
2. Every time tourist comes to an intersection, its counter is increased by 1.
3. Every time tourist leaves an intersection, its counter is also increased by 1.
4. Every time tourist walks down the street, its counter is increased by 1.

It should not be difficult to see that for every intersection, its counter is equal to the sum of counters of streets leading to that intersection (since walking on a street leading to a particular intersection adds 1 to both counters).

Second observation is the following: For every intersection except the start point S (the hotel) and the end point E (where he had his supper), the corresponding counter is even. This is because for every intermediate intersection the tourist came to it and left it (cf. 2 and 3 above). Which actually means that the number of streets with odd counter leading to any intermediate intersection is even.

For the intersections S and E, the situation is different, because the tourist has left S one more time than he has come to it, and he has come one more time to E than he has left it (unless S and E coincide). Which means the counters of S and E are both odd. But this actually means that the number of streets with odd counter leading to S and E is odd.

An important corollary if the above argument is that there is at least one street with an odd counter leading to E. Let’s the other intersection of this street be N.

Now, consider all the streets leading to N. What do you get?

Title: Re: A tourist problem
Post by Grimbal on Aug 18^th, 2007, 2:24am

on 08/17/07 at 23:18:33, Barukh wrote:

Second observation is the following: For every intersection except the start point S (the hotel) and the end point E (where he had his supper), the corresponding counter is odd.

In fact, it is even for every intersection except S and E, and odd at S and E (provided S and E are distinct).

One interesting thing is that when the man is not at S, there is at least one road from E that he walked an odd number of times. Going down that road will reduce by one the number of roads he walked an odd number of times, meaning that by walking down just any "odd" road he is sure to eventually reach the hotel.

Title: Re: A tourist problem
Post by Hippo on Aug 18^th, 2007, 3:33am

Just Note ... Grimbal uses E in other meaning than Barukh ... it is place where tourist currently stands in Grimbal argument ... argument therefore can be repeated while there are odd roads, but as their number decreases, he must eventualy return to S

Title: Re: A tourist problem
Post by Barukh on Aug 18^th, 2007, 5:26am

on 08/18/07 at 02:24:05, Grimbal wrote:

In fact, it is even for every intersection except S and E, and odd at S and E (provided S and E are distinct).

Oops... :o :o :o

Corrected.