Umsortieren von Bahnwagen, um Fahrgäste zu ärgern

22.12.2005, 20:00

Silencer

Umsortieren von Bahnwagen, um Fahrgäste zu ärgern

Moin, moin,
mir kam heute auf dem Hamurger Hauptbahnhof eine nette Frage in den Sinn, weil da ein Zug eine umgedrehte Wagensortierung hatte und damit ziemliches Gerenne ausbrach.

Wir nehmen uns 5 Abschnitte und nennen diese A, B, C, D und E
Zum zweiten nehmen wir uns einen Zug, der nicht durchgehend ist und aus 15 Wagen besteht, in jeden Bahnabschnitt passen 3 Wagen (die Loks parken halt vor A und nach E Augenzwinkern

), also stehen in Abschnitt A die wagen 1, 2 und 3, in Abschnitt B die Wagen 4, 5 und 6, in Abschnitt C die Wagen 7, 8 und 9, in Abschnitt D die Wagen 10, 11 und 12 und in Abschnitt E die Wagen 13, 14 und 15.

Zudem nehmen wir uns Fahrgäste. Alle Fahrgäste haben in einem Wagen reserviert und wollen diese Reservierung auch wahrnehmen und müssen daher und weil der Zug nicht durchgehend ist, am entsprechenden Punkt des Abschnittes auf den Wagen warten.
Der Einfachheit halber sollte man annehmen, dass in jeden Wagon die gleiche ANzahl Fahrgäste reinwollen.

Die Frage ist nun:
Wie muss man die Wagen umsortieren, damit die Fahrgäste im Durchschnitt maximal laufen müssen?
(als Weglänge nehmen wir einfach n Wagenlängen Augenzwinkern

)

Die intuitive Lösung wäre ja, zu sagen, dass man den Zug einfach umdreht, da so die Fahrgäste des 15. Wagens 15 Wagenlängen laufen müssten, die im Wagen 1 auch, aber vielleicht reissen die Leute, die bei Wagen 7 stehen und lachen da den Durchschnitt herunter?

Was meint ihr dazu?

22.12.2005, 20:04

JochenX

Auf diesen Beitrag antworten »

ohne da groß drüber nachgedacht zu haben:
warum muss jeder abschnitt 3 wagen enthalten?
wäre es irgendetwas anderes, wenn man das nur auf 5 abschnitte a je ein wagen betrachten würde (was zumindest mal die abzählung erleichtern würde)?

22.12.2005, 20:08

Silencer

Auf diesen Beitrag antworten »

Diese Abschnittseinteilung ist nur da, weil die da am Bahnhof so ist.

Eigentlich dürfte ja - weil die Gehlänge ja in Wagenlängen ist - die Abschnittseinteilung komplett egal sein.

Auch kann man sicher die Wagenanzahl verringern, um ein System zu finden, mit dem man für allgemeine n sagen kann, wie man das umsortieren kann.

22.12.2005, 22:47

Auf diesen Beitrag antworten »

Zitat:

Original von Silencer
Die Frage ist nun:
Wie muss man die Wagen umsortieren, damit die Fahrgäste im Durchschnitt maximal laufen müssen?
(als Weglänge nehmen wir einfach n Wagenlängen Augenzwinkern

)

Eine boshafte Frage - du bist nicht zufällig bei der Deutschen Bahn AG beschäftigt? Big Laugh

Mathematisch abstrahiert: Im Grunde genommen geht es um die Suche nach der Permutation $\begin{eqnarray*} \pi \end{eqnarray*}$ der Zahlen $\begin{eqnarray*} 1,\ldots,n \end{eqnarray*}$ , die den Ausdruck

$\begin{eqnarray*} f(\pi) = \sum_{k=1}^n ~ |\pi(k)-k| \end{eqnarray*}$

maximiert - so sehe ich das zumindest.

Zur Bestimmung des Maximums teilen wir die Indexmenge $\begin{eqnarray*} \{1,2,\ldots,n\} \end{eqnarray*}$ in zwei disjunkte Teilmengen $\begin{eqnarray*} I \end{eqnarray*}$ und $\begin{eqnarray*} J \end{eqnarray*}$ auf gemäß $\begin{eqnarray*} I=\{k:\;\pi(k)\geq k\} \end{eqnarray*}$ und $\begin{eqnarray*} J=\{k:\;\pi(k)<k\} \end{eqnarray*}$ .

Dann gilt im Fall $\begin{eqnarray*} |I|=m \end{eqnarray*}$ mit $\begin{eqnarray*} 1\leq m\leq n \end{eqnarray*}$ :

$\begin{eqnarray*} f(\pi) &=& \sum_{k\in I} (\pi(k)-k) ~ + ~ \sum_{k\in J} (k-\pi(k)) = 2\sum_{k\in I} (\pi(k)-k) ~ + ~ \sum_{k=1}^n (k-\pi(k))\\ &\leq& 2\sum_{k=1}^m ([n+1-k]-k) = 2m(n+1)-4\sum_{k=1}^m ~ k = 2m(n-m) \end{eqnarray*}$

Das Maximum wird erreicht durch $\begin{eqnarray*} m = \left\lfloor \frac{n}{2} \right\rfloor \end{eqnarray*}$ oder falls $\begin{eqnarray*} n \end{eqnarray*}$ ungerade ist auch noch durch durch $\begin{eqnarray*} m = \left\lfloor \frac{n+1}{2} \right\rfloor \end{eqnarray*}$ . Das ist der Maximumwert, der auch tatsächlich erreicht werden kann. Für $\begin{eqnarray*} n\geq 3 \end{eqnarray*}$ gibt es aber nicht nur die von dir richtig angeführte "umgedrehte" Permutation $\begin{eqnarray*} \pi(k)=n+1-k \end{eqnarray*}$ , die die Funktion $\begin{eqnarray*} f \end{eqnarray*}$ maximiert. Kannst dir ja mal überlegen, wieso das so ist, sowie welche und wieviele $\begin{eqnarray*} \pi \end{eqnarray*}$ die Funktion $\begin{eqnarray*} f \end{eqnarray*}$ maximieren!

23.12.2005, 11:04

Leopold

Auf diesen Beitrag antworten »

Eine Computer-Simulation bestätigt Arthurs Ergebnis:

max(1) = 0
1

max(2) = 2
2 1

max(3) = 4
2 3 1
3 1 2
3 2 1

max(4) = 8
3 4 1 2
3 4 2 1
4 3 1 2
4 3 2 1

max(5) = 12
3 4 5 1 2
3 4 5 2 1
3 5 4 1 2
3 5 4 2 1
4 3 5 1 2
4 3 5 2 1
4 5 1 2 3
4 5 1 3 2
4 5 2 1 3
4 5 2 3 1
4 5 3 1 2
4 5 3 2 1
5 3 4 1 2
5 3 4 2 1
5 4 1 2 3
5 4 1 3 2
5 4 2 1 3
5 4 2 3 1
5 4 3 1 2
5 4 3 2 1

max(6) = 18
4 5 6 1 2 3
4 5 6 1 3 2
4 5 6 2 1 3
4 5 6 2 3 1
4 5 6 3 1 2
4 5 6 3 2 1
4 6 5 1 2 3
4 6 5 1 3 2
4 6 5 2 1 3
4 6 5 2 3 1
4 6 5 3 1 2
4 6 5 3 2 1
5 4 6 1 2 3
5 4 6 1 3 2
5 4 6 2 1 3
5 4 6 2 3 1
5 4 6 3 1 2
5 4 6 3 2 1
5 6 4 1 2 3
5 6 4 1 3 2
5 6 4 2 1 3
5 6 4 2 3 1
5 6 4 3 1 2
5 6 4 3 2 1
6 4 5 1 2 3
6 4 5 1 3 2
6 4 5 2 1 3
6 4 5 2 3 1
6 4 5 3 1 2
6 4 5 3 2 1
6 5 4 1 2 3
6 5 4 1 3 2
6 5 4 2 1 3
6 5 4 2 3 1
6 5 4 3 1 2
6 5 4 3 2 1

max(7) = 24
4 5 6 7 1 2 3
4 5 6 7 1 3 2
4 5 6 7 2 1 3
4 5 6 7 2 3 1
4 5 6 7 3 1 2
4 5 6 7 3 2 1
4 5 7 6 1 2 3
4 5 7 6 1 3 2
4 5 7 6 2 1 3
4 5 7 6 2 3 1
4 5 7 6 3 1 2
4 5 7 6 3 2 1
4 6 5 7 1 2 3
4 6 5 7 1 3 2
4 6 5 7 2 1 3
4 6 5 7 2 3 1
4 6 5 7 3 1 2
4 6 5 7 3 2 1
4 6 7 5 1 2 3
4 6 7 5 1 3 2
4 6 7 5 2 1 3
4 6 7 5 2 3 1
4 6 7 5 3 1 2
4 6 7 5 3 2 1
4 7 5 6 1 2 3
4 7 5 6 1 3 2
4 7 5 6 2 1 3
4 7 5 6 2 3 1
4 7 5 6 3 1 2
4 7 5 6 3 2 1
4 7 6 5 1 2 3
4 7 6 5 1 3 2
4 7 6 5 2 1 3
4 7 6 5 2 3 1
4 7 6 5 3 1 2
4 7 6 5 3 2 1
5 4 6 7 1 2 3
5 4 6 7 1 3 2
5 4 6 7 2 1 3
5 4 6 7 2 3 1
5 4 6 7 3 1 2
5 4 6 7 3 2 1
5 4 7 6 1 2 3
5 4 7 6 1 3 2
5 4 7 6 2 1 3
5 4 7 6 2 3 1
5 4 7 6 3 1 2
5 4 7 6 3 2 1
5 6 4 7 1 2 3
5 6 4 7 1 3 2
5 6 4 7 2 1 3
5 6 4 7 2 3 1
5 6 4 7 3 1 2
5 6 4 7 3 2 1
5 6 7 1 2 3 4
5 6 7 1 2 4 3
5 6 7 1 3 2 4
5 6 7 1 3 4 2
5 6 7 1 4 2 3
5 6 7 1 4 3 2
5 6 7 2 1 3 4
5 6 7 2 1 4 3
5 6 7 2 3 1 4
5 6 7 2 3 4 1
5 6 7 2 4 1 3
5 6 7 2 4 3 1
5 6 7 3 1 2 4
5 6 7 3 1 4 2
5 6 7 3 2 1 4
5 6 7 3 2 4 1
5 6 7 3 4 1 2
5 6 7 3 4 2 1
5 6 7 4 1 2 3
5 6 7 4 1 3 2
5 6 7 4 2 1 3
5 6 7 4 2 3 1
5 6 7 4 3 1 2
5 6 7 4 3 2 1
5 7 4 6 1 2 3
5 7 4 6 1 3 2
5 7 4 6 2 1 3
5 7 4 6 2 3 1
5 7 4 6 3 1 2
5 7 4 6 3 2 1
5 7 6 1 2 3 4
5 7 6 1 2 4 3
5 7 6 1 3 2 4
5 7 6 1 3 4 2
5 7 6 1 4 2 3
5 7 6 1 4 3 2
5 7 6 2 1 3 4
5 7 6 2 1 4 3
5 7 6 2 3 1 4
5 7 6 2 3 4 1
5 7 6 2 4 1 3
5 7 6 2 4 3 1
5 7 6 3 1 2 4
5 7 6 3 1 4 2
5 7 6 3 2 1 4
5 7 6 3 2 4 1
5 7 6 3 4 1 2
5 7 6 3 4 2 1
5 7 6 4 1 2 3
5 7 6 4 1 3 2
5 7 6 4 2 1 3
5 7 6 4 2 3 1
5 7 6 4 3 1 2
5 7 6 4 3 2 1
6 4 5 7 1 2 3
6 4 5 7 1 3 2
6 4 5 7 2 1 3
6 4 5 7 2 3 1
6 4 5 7 3 1 2
6 4 5 7 3 2 1
6 4 7 5 1 2 3
6 4 7 5 1 3 2
6 4 7 5 2 1 3
6 4 7 5 2 3 1
6 4 7 5 3 1 2
6 4 7 5 3 2 1
6 5 4 7 1 2 3
6 5 4 7 1 3 2
6 5 4 7 2 1 3
6 5 4 7 2 3 1
6 5 4 7 3 1 2
6 5 4 7 3 2 1
6 5 7 1 2 3 4
6 5 7 1 2 4 3
6 5 7 1 3 2 4
6 5 7 1 3 4 2
6 5 7 1 4 2 3
6 5 7 1 4 3 2
6 5 7 2 1 3 4
6 5 7 2 1 4 3
6 5 7 2 3 1 4
6 5 7 2 3 4 1
6 5 7 2 4 1 3
6 5 7 2 4 3 1
6 5 7 3 1 2 4
6 5 7 3 1 4 2
6 5 7 3 2 1 4
6 5 7 3 2 4 1
6 5 7 3 4 1 2
6 5 7 3 4 2 1
6 5 7 4 1 2 3
6 5 7 4 1 3 2
6 5 7 4 2 1 3
6 5 7 4 2 3 1
6 5 7 4 3 1 2
6 5 7 4 3 2 1
6 7 4 5 1 2 3
6 7 4 5 1 3 2
6 7 4 5 2 1 3
6 7 4 5 2 3 1
6 7 4 5 3 1 2
6 7 4 5 3 2 1
6 7 5 1 2 3 4
6 7 5 1 2 4 3
6 7 5 1 3 2 4
6 7 5 1 3 4 2
6 7 5 1 4 2 3
6 7 5 1 4 3 2
6 7 5 2 1 3 4
6 7 5 2 1 4 3
6 7 5 2 3 1 4
6 7 5 2 3 4 1
6 7 5 2 4 1 3
6 7 5 2 4 3 1
6 7 5 3 1 2 4
6 7 5 3 1 4 2
6 7 5 3 2 1 4
6 7 5 3 2 4 1
6 7 5 3 4 1 2
6 7 5 3 4 2 1
6 7 5 4 1 2 3
6 7 5 4 1 3 2
6 7 5 4 2 1 3
6 7 5 4 2 3 1
6 7 5 4 3 1 2
6 7 5 4 3 2 1
7 4 5 6 1 2 3
7 4 5 6 1 3 2
7 4 5 6 2 1 3
7 4 5 6 2 3 1
7 4 5 6 3 1 2
7 4 5 6 3 2 1
7 4 6 5 1 2 3
7 4 6 5 1 3 2
7 4 6 5 2 1 3
7 4 6 5 2 3 1
7 4 6 5 3 1 2
7 4 6 5 3 2 1
7 5 4 6 1 2 3
7 5 4 6 1 3 2
7 5 4 6 2 1 3
7 5 4 6 2 3 1
7 5 4 6 3 1 2
7 5 4 6 3 2 1
7 5 6 1 2 3 4
7 5 6 1 2 4 3
7 5 6 1 3 2 4
7 5 6 1 3 4 2
7 5 6 1 4 2 3
7 5 6 1 4 3 2
7 5 6 2 1 3 4
7 5 6 2 1 4 3
7 5 6 2 3 1 4
7 5 6 2 3 4 1
7 5 6 2 4 1 3
7 5 6 2 4 3 1
7 5 6 3 1 2 4
7 5 6 3 1 4 2
7 5 6 3 2 1 4
7 5 6 3 2 4 1
7 5 6 3 4 1 2
7 5 6 3 4 2 1
7 5 6 4 1 2 3
7 5 6 4 1 3 2
7 5 6 4 2 1 3
7 5 6 4 2 3 1
7 5 6 4 3 1 2
7 5 6 4 3 2 1
7 6 4 5 1 2 3
7 6 4 5 1 3 2
7 6 4 5 2 1 3
7 6 4 5 2 3 1
7 6 4 5 3 1 2
7 6 4 5 3 2 1
7 6 5 1 2 3 4
7 6 5 1 2 4 3
7 6 5 1 3 2 4
7 6 5 1 3 4 2
7 6 5 1 4 2 3
7 6 5 1 4 3 2
7 6 5 2 1 3 4
7 6 5 2 1 4 3
7 6 5 2 3 1 4
7 6 5 2 3 4 1
7 6 5 2 4 1 3
7 6 5 2 4 3 1
7 6 5 3 1 2 4
7 6 5 3 1 4 2
7 6 5 3 2 1 4
7 6 5 3 2 4 1
7 6 5 3 4 1 2
7 6 5 3 4 2 1
7 6 5 4 1 2 3
7 6 5 4 1 3 2
7 6 5 4 2 1 3
7 6 5 4 2 3 1
7 6 5 4 3 1 2
7 6 5 4 3 2 1

Neue Frage »

Antworten »

Umsortieren von Bahnwagen, um Fahrgäste zu ärgern

Verwandte Themen