Author |
Topic: Roads between cities (Read 857 times) |
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
 |
Roads between cities
« on: Aug 27th, 2008, 8:31am » |
 Quote  Modify
|
Between any two cities of a country there is one direct road, possibly one-way.
Show that there is a city from which every other city can be reached by going over at most one intermediate city.
|
|
 IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Roads between cities
« Reply #1 on: Aug 27th, 2008, 4:01pm » |
Quote Modify
|
I hope I understand it well. We start with complete undirected graph and orient somehow it's edges.
We have to show there is a vertex from which each vertex is in distance at most 2.
Hmm, looks interesting 
Start with a vertex v with highest out degree d. Vertex w which is not in directed distance 1 is in directed distance 2 otherwise each edge with the d vertices is directed from w but there is also directed edge from w to v leading to contradiction with maximality of degree d.
on Aug 27th, 2008, 9:27pm, Noke Lieu wrote:
There should be a connection with the Grimbal's question?
|
| « Last Edit: Aug 28th, 2008, 6:25am by Hippo » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Roads between cities
« Reply #3 on: Aug 28th, 2008, 4:42am » |
Quote Modify
|
Hippo is correct!
Now we know where to build the firestation.
@Noke Lieu: it has nothing to do with that problem, except that visually you have n points and every point is connected to all others.
|
| « Last Edit: Aug 28th, 2008, 4:43am by Grimbal » |
IP Logged |
|
|
|
Noke Lieu
Uberpuzzler
pen... paper... let's go! (and bit of plastic)
Gender:
Posts: 1884
|
|
Re: Roads between cities
« Reply #4 on: Aug 28th, 2008, 4:10pm » |
Quote Modify
|
it was the visual thing I was talking about.
I was just looking for a backdoor solution. 
( combined with a mixture of misreading the question, a bit too much coffee and enthusiasm... sorry)
Just so I understand your answer... (I recognise graph theory, but don't know much about it)
Start with a vertex v with highest out degree d. Vertex w which is not in directed distance 1 is in directed distance 2
Up until here has be a restatement of the question, except we're looking at the city with the most roads leaving it.
otherwise each edge with the d vertices is directed from w but there is also directed edge from w to v leading to contradiction with maximality of degree d.
IF there is a city W that you can't get to from V directly (because the oneway street goes the wrong way) then you can go from V to W via another city.
If you can't do that, then you've miscounted the number of roads leaving each city (or in the case of having a few cities with the same number of roads leaving it, chosen the wrong city to put the firestation)
It seems to me I'm missing something... it seems like a clarification of the question, almost "You mean do this? Oh yeah, you can do that."
I suppose that's what "show that..." means though. 
(oh started this before ecoist posted, but had to do some work...)
|
| « Last Edit: Aug 28th, 2008, 5:55pm by Noke Lieu » |
IP Logged |
a shade of wit and the art of farce.
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Roads between cities
« Reply #5 on: Aug 28th, 2008, 5:30pm » |
Quote Modify
|
Induction on the number of cities. For two cities the conclusion is obvious. Assume the result is true for n>1 cities. Consider n+1 cities and let c be one of those cities. By induction, among the remaining n cities, there is a city, say c', from which any city except c can be reached directly or via passing through at most one city other than c. Let D be the set of all cities except c that c' can reach directly, and let I be the cities other than c that can only be reached from c' by going through an intermediate city other than c. If c can be reached directly from c', then we are done; c' works for the n+1 cities. Otherwise it's one way from c to c'. If c can be reached directly from from some city in D, then again we are done with c' as the city that works for the n+1 cities. Otherwise, every road from c to c' or a city in D must be one way from c. But then one can go from c directly to c' and any city in D, and with passing through at most one city (in D) reach a city in I. Hence c works for the n+1 cities.
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Roads between cities
« Reply #6 on: Aug 28th, 2008, 6:22pm » |
Quote Modify
|
Hippo's solution is beautiful and complete, although it may suffer from a slight run-on sentence. I'll try to rephrase.
A city x that works is any city that has the maximum number of roads leaving from it. If some city y cannot be reached from this city in two steps, then that city has more roads leaving from it than our original city: every city which can be reached from x in one step can also be reached from y in one step (otherwise we could reach y from x in two steps), and we can also reach x from y in one step. But this contradicts our choice of x as being the city with the most roads leaving from it.
(easy) follow up question: what if there are infinitely many cities?
|
|
IP Logged |
|
|
|
Noke Lieu
Uberpuzzler
pen... paper... let's go! (and bit of plastic)
Gender:
Posts: 1884
|
|
Re: Roads between cities
« Reply #7 on: Aug 28th, 2008, 8:15pm » |
Quote Modify
|
I was afraid this might happen.
iIdon't doubt that Hippo's answer is great. It says formally what I thought intuatively.
My issue is, I guess, that because I thought of that intuatively, it didn't seem like it'd be enough. or something.
|
|
IP Logged |
a shade of wit and the art of farce.
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Roads between cities
« Reply #8 on: Aug 29th, 2008, 9:20am » |
Quote Modify
|
I like more the contradiction end, but you can as well end with 'as the out degree of w is at most d, some of the d+1 edges should be directed towards w'. This will probably be easier to cope with.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Roads between cities
« Reply #9 on: Aug 29th, 2008, 10:33am » |
Quote Modify
|
on Aug 28th, 2008, 6:22pm, Obob wrote:| (easy) follow up question: what if there are infinitely many cities? |
|
If there are  cities, you can arrange things so that no city can reach (using paths of any length) cities. On the other hand, for any  < cf(), there is always a city that can reach at least others directly. I think that covers it for regular cardinals.
So what happens if there are  cities? 
|
| « Last Edit: Aug 29th, 2008, 10:35am by Eigenray » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print