Roads and the cities..

In Ozmania, all the cities are connected by 2 way roads. Before election, the king wanted to repair the roads. So some roads are made one way during repair, and rest were 2-way as before. After they are repaired, those were made back to 2-way, and some other roads are made 1-way for repairing. This is done until all roads are repaired. While repairing, citizens can move from any city to any other city.

Prove that, if we make all the roads 1-way, one still can move from any city to city.

I assume that 'all the cities are connected by 2 way roads' means 'each pair of cities is directly connected by a two way road'. I also assume that 'Prove that, if we make all the roads 1-way, one still can move from any city to city' means 'Prove that we can make all the roads 1-way in such a way that one can move from any city to any other city'.

Lemma: 'Some roads are made one way'. Therefore there are some roads. Therefore there are at least two roads. Therefore there are at least three cities. (If there were 0, 1 or 2 cities, the proof would be impossible.)

Proof: Consider any three cities. They are connected by a triangle of roads. Assign the directions so that these roads run clockwise. Now add another city to those already considered, ensuring that one road leads from it to them, and one from them to it. Repeat until we have dealt with all the cities.

I'm not quite sure how to interpret the statement of the problem. If all roads are made 1-way simultaneously then there are configurations for which your claim is not true, specifically a city for which all incident roads run away from it. If we can make as many or as few roads 1-way at each step then of course it's easy because we make only one 1-way road at a time. In fact, all roads can be made 1-way simultaneously (thereby obviating part of your puzzle statement) and still satisfy the condition provided we choose the directions of the roads and establish a cycle of 1-way roads that visits each city once. Of course if there are only 2 cities then there is no hope for the Ozmaniacs.

Mark

Mark Pilloff schrieb:

If there are only 2 cities, there must be two roads.

Have fun with yellow bricks

What about this: (X is a city, - or is a road)

'Mark J. Tilford' schrieb:

However, opposites cities are not connected directly.

<snip>

Yes, he should have said 'can be'.

But this ignores my stated assumption which you quote above.

If you make that assumption, then the problem become utterly trivial.

If, however, you take it to mean that all the roads that exist are two- way, then it becomes an interesting problem.

I thought that it might be possible to attack it with the graph theory theorem that states that if a graph is 2-connected then every set of two points lies on a cycle. However, it's possible for a set of roads to match the specified repair criteria without being 2-connected - they only need to be 2-line-connected.

If you don't make the assumption that I suggested, then, trivially, it is an impossible problem. There can be a city which is connected to the rest of the network only by a single road.

Nick Wedd schrieb:

That would violate the condition that people can still get to that city and away from it while that single road is being repaired.

Have fun with Men At Work