Ernie and the Underground Network

Question

I haven't seen Ernie for a few weeks - he's been on holiday in the People's Republic of Kzijekistan (PRK). But yesterday I got an e-mail and thought I would share it with you. It reads as follows:

The history of Kzijekopolis is intriguing. It was founded by Kzijekl the Great, who built a castle atop Mt. Chatcal in the late 18th century. When Kzijekl's wife had identical quadruplets - all boys - the traditional solution would have been to 'retire' the younger sons to distant monasteries. But the midwife made a dreadful mistake - she put them all in the same cot and when the Khan arrived in the birthing chamber it was impossible to tell which was the eldest. Kzijekl decided that all the boys should be brought up as potential rulers, and on their 21st birthday the true heir would be chosen (by God) via 4 on 4 combat to the death. He built four massive walls to divide the city into quarters, one for each son to live in, so they would not meet before their 21st birthday Battle Royale. It was decreed that no opening could be made in the dividing walls until a single son ruled the Empire, unopposed.

But Kzijekl's plans were dashed when the four brothers met by chance on a holiday to Paris and became friends. On their return they declared themselves co-chairmen of a new Peoples's Republic and 'retired' their father to a distant monastery. As no individual son ruled the Empire, the city judges decided that the dividing walls must remain unbroken - as they do to the present day. Nowadays the city is divided into four distinct sectors: Arts & Sciences (A&S), Bureaucracy and Administration (B&A), Commerce and Industry (C&I), and Dining and Accommodation (D&A), echoing the brothers' specialties in their chairmanship.

Late in their lives the co-chairmen decided it was inefficient to have to travel via city gates and the ox-cart-laden ring-road just to get to a different city quarter, so they built a subterranean railway with lines passing 'under' the walls. Thus they built the world's first Metro System and ensured efficient intra-city travel without breaking the now sacrosanct laws that the dividing walls should never be breached. Recently the PRK has became convinced that terrorists are bent on the destruction of the city. To make it difficult for saboteurs to abuse the Metro, some rather unusual rules have been instigated - described in the Information for Metro Users pamphlet that I was handed at the Hotel's front desk. I quote it verbatim:

The System
1) There are precisely four Metro stations - one in each quarter.
2) There are precisely five tracks, each connecting two distinct stations.
3) There are no track crossings and tracks only meet at the stations.

Security
4) For security reasons there are no maps of the metro.
5) For security reasons there are no fixed timetables. At the instant each train leaves a station its destination is chosen randomly and without bias from one of the other stations directly connected to it by a track.
6) For security reasons it is illegal to exit a train after a single station-to-station journey (1-trip) - every passenger must remain on board while the train makes a minimum of two station-to-station journeys (n-trip where n>1).

Tips for Travelers
7a) From any station in the network a 2-trip journey has a non-zero probability of reaching any station in the network (including the starting point).
7b) From any station in the network a 3-trip journey has a non-zero probability of reaching any station in the network (including the starting point).

As you might guess, I took this as a challenge and decided to try and map out the underground for myself. As I bought a selection of 2-trip and 3-trip tickets at the desk I asked the clerk if there was anything he could tell me to make it easier to get around town efficiently. He paused for a few seconds, and checked that nobody was listening. "Well, I probably shouldn't tell you this but all locals know from experience that if you use a 2-trip ticket from either A&S or C&I, you have an almost 45% chance of ending up back where you started".

I had an enjoyable day touring the city. It was frustrating at times - it took me several attempts to get to get to A&S so I could visit the National Museum, but the people were friendly, the food (once I managed to get back to D&A) was delicious. And of course, I was happy because I knew exactly which pairs of stations were connected by the five tracks - thanks to the tip the clerk had provided. As I was dropping off my room key the next morning the clerk handed me a new Information for Metro Users pamphlet. It was identical except that sections 7a and 7b had been crossed out and replaced with the following:

7c) From any station in the network a 4-trip journey has a non-zero probability of reaching any station in the network (including the starting point).

"The old Tips, 7a and 7b don't work anymore", the clerk commented ruefully. "Of course we are offering to exchange any 2-trip or 3-trip tickets you have left over with new 4-trip tickets". I asked what had changed and he replied, "Just overnight a single new station-to-station track has just been completed and opened to the public - but simultaneously exactly one of the old tracks has been temporarily closed down for maintenance".

I asked if he had any hints to make travel easier. "Well, maybe I shouldn't be telling you this, but my brother works for the Railway Administration Committee. He let it slip to me last night that with the new set-up if you use a 4-trip ticket, starting from either C&I or D&A, you have an exact 25% chance of ending up back where you started".

I had another great day touring around, this time at the National Gallery. The art was exquisite, but for me the highlight of the day was that I still knew exactly which pairs of stations were connected by the five tracks - thanks to the new information the clerk had provided.

Now I'm sure the story of the underground system will come up again once Ernie is back home. But for the life of me I can't work out how the stations were connected either before or after the network changes. Could anyone possibly help me with a description or diagram?

Answer 1

Clearly, by the conditions given, the original graph of the subway looks like a square under the city with a single diagonal included, running either from C&I to A&S or from D&A to B&A. If we started from a station not including this diagonal, then it is connected to two other stations, each of which is connected to three other stations (exactly one of which is the original station). The probability of return from such a station is $\frac{1}3$. For a station on the diagonal, it is connected to both the stations off the diagonal (with a $\frac{1}2$ chance of return from each) and to the station across the diagonal (from which it may return with probability $\frac{1}3$). This yields a $\frac{1}3\cdot(\frac{1}2+\frac{1}2+\frac{1}3)=\frac{4}9$ chance of returning to the original station, which is in line with the number cited by the clerk. Thus, C&I and A&S are connected by subway originally:

D&A---A&S | / | | / | | / | | / | C&I---B&A

For the second problem, we can guess that we have a symmetry in the graph, whereby we may "exchange" D&A and C&I while maintaining topological properties - this needn't be true in general, but we expect them to have the same properties roughly, so it's a good guess to start with. A graph satisfying this with one edge deleted is:

D&A---A&S | / | | / | | / | | / | C&I B&A

Then, we note that the only violations to 7a and 7b are that a 2-trip cannot take B&A to A&S (or vice versa) and a 3-trip cannot take D&A to C&I (or vice versa). Adding the diagonal from B&A to D&A or any self loop would cause one of these pairs to be connected by 2 or 3 trip respectively - meaning 7a or 7b would still hold. Thus, we conclude that the new line runs parallel to an old one. The only edge fixed by exchanging D&A and C&I (which is the symmetry we want to preserve) is the A&S to B&A line, so we try doubling it:

D&A---A&S | /|| | / || | / || | / || C&I B&A

If we compute the probabilities here (via Markov chain), we find that this must be the new map of the city, as it gives D&A and C&I a probability of $\frac{1}4$ returning with a 4-trip.