The year 2600…
Finally, we discovered a planet where we can live besides Earth. Scientists named this planet as T-489. The living conditions in T-489 seems very much like the Earth’s. Satellite views show that there is water on this planet. And scientists discovered that the atmosphere on this planet is almost the same as Earth’s atmosphere.
Space agencies of the world’s biggest countries gathered a team to discover T-489. According to the plan, the first team that lands on T-489 will secure the landing point and build a headquarter. This point is set beforehand with the use of the satellite photos.
After the completion of the headquarters, three separate teams will be sent to T-489 to discover certain points on the planet that was set beforehand. These teams will be searching for the possible existence of life forms as well as testing the life conditions on each location.
The headquarter of T-489 should develop a map for those three teams which will be scouting the planet. This map is crucial since it will show how those teams should travel on the planet, and it will also explain how a team can return to the headquarters in case of an emergency.
In certain situations such as not knowing where a team is at a given time, headquarters must add an algorithm to the map. This way, in an emergency, any team can use this algorithm and return to the headquarters safely.
Road Coloring Problem
In 1970, Roy Adler suggested the road coloring problem. After almost 40 years, an Israeli mathematician called Trahtman solved this problem.
Trahtman thought of the map as a graph shown above; each road had a direction and a distinct color. Trahtman created these directions and colors such that, following a certain algorithm, your travel would always end up on a specific point. In this example, the algorithm is following blue-red-red roads three times and always ending up at the yellow point. You can try at any point and see by yourself.
Chaos on T-489
You must develop a map for the teams that will be scouting the planet. Headquarters and the locations to visit are shown as follows:
You should prepare for the worst possible scenario. If the connection breaks between the headquarters and the scouting teams, and if those teams can’t access to the map, your algorithm might save their lives.
The idea is: Place a sign on the entry of each point. These signs will have only two pieces of information: The color and the direction of the roads. (Why don’t you just hang the map on these signs? Because you are not sure if there is an alien life form on the planet. And in case they exist, such maps might put the headquarters and the whole mission at danger.)
Let’s say you created a map as follows:
Such a map would have an algorithm like this: Follow red-blue twice, and you will always return to the headquarters.
One wonders…
Let’s say that there is one more point added to the discovery. Create a map and an algorithm such that, whenever you use the algorithm you will end up at the headquarters.
(Try to use the least number of roads on your map.)
M. Serkan Kalaycıoğlu
kmatematikatolyesi.com 