Author |
Topic: A tourist problem (Read 1044 times) |
|
Cool_Joh
Guest
|
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.
|
|
 IP Logged |
|
|
|
mikedagr8
Uberpuzzler
A rich man is one who is content; not wealthy.
Gender: 
Posts: 1105
|
 |
Re: A tourist problem
« Reply #1 on: Aug 11th, 2007, 6:20am » |
 Quote  Modify
|
Because he can always walk on the streets only once, hence an uneven number?
|
| « Last Edit: Aug 11th, 2007, 6:45am by mikedagr8 » |
IP Logged |
"It's not that I'm correct, it's that you're just not correct, and so; I am right." - M.P.E.
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: A tourist problem
« Reply #2 on: Aug 11th, 2007, 6:44am » |
Quote Modify
|
on Aug 11th, 2007, 6:20am, mikedagr8 wrote:| Because he can always walk on the streets only once, hence an even number? |
|
It is related to the Konigsberg Bridge Problem.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
mikedagr8
Uberpuzzler
A rich man is one who is content; not wealthy.
Gender:
Posts: 1105
|
|
Re: A tourist problem
« Reply #3 on: Aug 11th, 2007, 6:46am » |
Quote Modify
|
Is that the 7 bridges problem, my net is stuffed so i can't look it up.
|
|
IP Logged |
"It's not that I'm correct, it's that you're just not correct, and so; I am right." - M.P.E.
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: A tourist problem
« Reply #4 on: Aug 11th, 2007, 6:54am » |
Quote Modify
|
on Aug 11th, 2007, 6:46am, mikedagr8 wrote:| Is that the 7 bridges problem, my net is stuffed so i can't look it up. |
|
That's the one.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
mikedagr8
Uberpuzzler
A rich man is one who is content; not wealthy.
Gender:
Posts: 1105
|
|
Re: A tourist problem
« Reply #5 on: Aug 11th, 2007, 6:56am » |
Quote Modify
|
In that though, they can never travel on all of the bridges, how does this relate?
|
|
IP Logged |
"It's not that I'm correct, it's that you're just not correct, and so; I am right." - M.P.E.
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: A tourist problem
« Reply #6 on: Aug 11th, 2007, 10:32am » |
Quote Modify
|
Key observation (cf Konigsberg bridges):
| hidden: |
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.
|
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.
|
|
IP Logged |
|
|
|
mikedagr8
Uberpuzzler
A rich man is one who is content; not wealthy.
Gender:
Posts: 1105
|
|
Re: A tourist problem
« Reply #7 on: Aug 11th, 2007, 4:40pm » |
Quote Modify
|
Thankyou rmsgrey for the explanation and clever problems in real life it may cause.
|
|
IP Logged |
"It's not that I'm correct, it's that you're just not correct, and so; I am right." - M.P.E.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: A tourist problem
« Reply #8 on: Aug 12th, 2007, 2:22am » |
Quote Modify
|
Of course, the tourist might have trouble with one-way streets (or one-way gates for pedestrians).
|
|
IP Logged |
|
|
|
Cool_Joh
Guest
|
okay, now can someone explain it clearly to me in simple english? i still don't get it..
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: A tourist problem
« Reply #10 on: Aug 17th, 2007, 11:18pm » |
Quote Modify
|
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?
|
| « Last Edit: Aug 18th, 2007, 5:26am by Barukh » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: A tourist problem
« Reply #11 on: Aug 18th, 2007, 2:24am » |
Quote Modify
|
on Aug 17th, 2007, 11:18pm, 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.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: A tourist problem
« Reply #12 on: Aug 18th, 2007, 3:33am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: A tourist problem
« Reply #13 on: Aug 18th, 2007, 5:26am » |
Quote Modify
|
on Aug 18th, 2007, 2:24am, 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... 
Corrected.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove