MathDB

7

Part of 2014 Switzerland - Final Round

Problems(1)

n cities on a round lake

Source: Switzerland - 2014 Swiss MO Final Round p7

1/14/2023
There are n≥4n \ge 4 cities on a round lake, between which n−4n -4 people travel and one green drivers operate. Each ferry connects two non-adjacent cities, and itself do not cross two driving routes so that collisions can be avoided. In order to better adapt the transport routes to the needs of the passengers, the following change can be done: A new route can be assigned to any driver. The routes of the remaining drives must not cross and also must not be changed at the same time. Let Santa Marta and Cape Town be two non-adjacent cities. Show that you have finitely many route changes so that the Green Driver will operate between Santa Marta and Cape Town after these changes.
Note: At no time may two trips between the same cities or one drive between two neighboring cities.
[hide=original wording]An einem runden See liegen n>=4n >= 4 Stadte, zwischen denen n−4n - 4 Personenfahren und eine grune Autofahre verkehren. Jede Fahre verbindet zwei nicht benachbarte Stadte, wobei sich keine zwei Fahrenrouten uberkreuzen, damit Kollisionen vermieden werden konnen. Um die Transportrouten besser den Bedurfnissen der Passagiere anzupassen, kann folgende Anderung vorgenommen werden: Einer beliebigen Fahre kann eine neue Route zugeordnet werden. Dabei durfen die Routen der restlichen Fahren nicht uberkreuzt und auch nicht gleichzeitig verandert werden. Seien Santa Marta und Kapstadt zwei nicht benachbarte Stadte. Zeige, dass man endlich viele Routenanderungen vornehmen kann, sodass die grune Autofahre nach diesen Anderungen zwischen Santa Marta und Kapstadt verkehrt. Bemerkung: Zu keinem Zeitpunkt durfen zwei Fahren zwischen denselben Stadten oder eine Fahre zwischen zwei benachbarten Stadten verkehren.
combinatorics