MR 08

Optimiertes Zuprosten

Wenn eine Gesellschaft mit $n$ Personen sich zuprostet, dann müssen sich insgesamt ${\binom {n}{2}}$ Pärchen zuprosten. Bei 8 Personen sind das z.B. 28 Pärchen. Jedoch zeigt, die "gefühlte" Erfahrung, dass das viel schneller geht. Das liegt vor allem daran, dass sich ja zu einem Zeitpunkt nicht nur 2 zuprosten, sondern mehrere. Bei $n$ Personen können sich gleichzeitig immer $\left\lfloor {\frac {n}{2}}\right\rfloor$ Pärchen zuprosten.

Die Aufgabe besteht darin einen Plan für das geordnete Zuprosten von $n$ Personen zu erstellen. Wie müssen sich die Personen aufstellen, wie müssen sie sich nach jedem Zuprosten umstellen, damit sich am Ende alle zugeprostet haben? Die Zusätzliche Aufgabe besteht darin diesen Prozess zu optimieren. D.h. die Wege der einzelnen Personen sollen minimal sein.

Hinweis: Über Kreuz kann nicht gleichzeitig zugeprostet werden. Im allgemeinen wird es nötig sein, dass sich die Personen umstellen, damit sie sich gleichzeitig zuprosten können.

Lösung

Bitte versucht es zuerst selber - drückt nicht gleich auf den Link.

Fossys Lösung