Bahnlinien (not that easy)

Freizeit & Hobby Rätsel
#1

Hi Rätselfreunde,

Gegeben seien n Städte. Zwischen diesen sollen Eisenbahnstrecken eingerichtet werden. Dabei sollen allerdings ein paar Bedingungen eingehalten werden. Von und zu jeder Stadt gibt es Bahnstrecken jeweils in exakt gleicher Zahl von und zu anderen Städten. Also alle Städte sind direkt (ohne Zwischenstop) mit genau m anderen Städten per Bahnlinie verbunden. Und eine zweite Bedingung gilt. Zwischen je zwei Städten, gibt es eine Bahnreiseroute, derart, das auf der Bahnreise von Stadt A nach Stadt B maximal eine weitere Stadt als Zwischenstation durchfahren wird. Dank Weichen und Bahnbrücken, stellen Kreuzungen kein Problem dar und dürfen vorkommen.
Die Frage lautet: wieviel Städte sind es, die auf diese Weise miteinander verbunden sind? also wie groß ist n?

Ok. die Frage ist nicht ganz fair, weil sie nicht eindeutig zu beantworten ist. Deshalb eine kleine Einschränkung: wenn ich mehr als 100 aber weniger als 1000 Städte will, kann mir dann jemand die genaue Zahl an Städten nennen?

rauchende köpfe wünscht

unimportant

#2

Hallo,
sind die einzelnen Strecken nur in einer Richtung passierbar ? Wenn ich die Aufgabe richtig verstehe, ist zu einem fixen aber beliebigen m das ein n gesucht, so daß es ein Verbindungsnetz gibt, daß die zwei Bedingungen erfüllt. Fordert man für n, daß es maximal ist, würde ich annehmen, daß es eindeutig wird.
Mich irritiert diesbzgl. nur Deine zusätzliche Einschränkung 100

#3

Zusatz
Hi,

Hallo,
sind die einzelnen Strecken nur in einer Richtung passierbar ?

nein, immer in beide Richtungen.

Wenn ich die Aufgabe richtig verstehe, ist zu einem fixen aber
beliebigen m das ein n gesucht, so daß es ein Verbindungsnetz
gibt, daß die zwei Bedingungen erfüllt. Fordert man für n, daß
es maximal ist, würde ich annehmen, daß es eindeutig wird.
Mich irritiert diesbzgl. nur Deine zusätzliche Einschränkung
1002 in diesem Fall wäre m=1.

Für n=3 und n=4 gibt es keine Lösung. Für n=5 gibt es wieder eine Lösung und zwar der Graph, der lediglich einen Kreis durch die 5 Knoten bildet. Da wäre m=2. Das nächstgrößere n wäre n=10 mit dem Petersen-Graphen und m=3. Dass sollte als Anschauungsmaterial genügen.

Ich hab mir aber leider eine kleine Unexaktheit in der Formulierung geleistet. Statt Zwischen je zwei Städten, gibt es eine Bahnreiseroute, derart, das auf der Bahnreise von Stadt A nach Stadt B maximal eine weitere Stadt als Zwischenstation durchfahren wird.
muss es korrekt lauten: ‚Zwischen je zwei Städten, gibt es genau eine Bahnreiseroute, derart, das auf der Bahnreise von Stadt A nach Stadt B maximal eine weitere Stadt als Zwischenstation durchfahren wird.‘

aber dass die Lösung nicht gerade einfach ist, das gilt immer noch.
jedoch kann man sich dem Problem durchaus durch Überlegungen annähern, also man muss jetzt nicht wirklich jedes n zwischen 100 und 1000 untersuchen und muss das Problem auch nicht mit dem Computer bruteforcen.

Vielleicht, weil es wirklich nicht ganz einfach ist, noch als Info:

es gibt genau 6 Zahlen n, für die das Problem lösbar ist, das sind 2,5,10,50,3250 sowie die gesuchte Zahl. Damit kann man schon mal ganz gut überprüfen, ob die Überlegungen in die richtige Richtung gehen.

dann noch viel Spaß

unimportant

#4

Hallo,
poste bitte vorerst erst mal keine Antwort. Ich komme erst heute abend dazu, mir das Problem näher anzuschauen.

Gruss
Enno