MR 08 Loesung

Optimiertes Zuprosten

zurück zur Aufgabenstellung

Durch Herumprobieren auf einem Zettel (was hier nicht wiedergegeben werden kann) kommt man schnell d'rauf, dass es fast mit einem natürlichen "um den Tisch weiterrücken" und dem Zuprosten der jeweiligen Gegenüber funktionieren könnte. Wenn man das aber mit einer geraden Anzahl an Personen (das bietet sich an, weil sich immer alle zuprosten können) nicht funktioniert. Das liegt daran, dass sich nachdem durch das Weiterrücken alle von der einen Seite des Tisches zur anderen gelangt sind, sich wieder ihren gleichen Partnern gegenüber sehen.

Im folgenden wird immer von der Nummer 0 wegnumeriert. Das hat den Vorteil, dass man beim Beweis mit der Modulorechnung, nicht künstlich eins dazu und danach wieder abziehen muss. Die Plätze für $n$ Personen sind mit den Zahlen 0 bis $n-1$ benannt.

Jedoch funktioniert das Herumwandern um einen Tisch immer für eine ungerade Anzahl an Personen.

Personenzahl ist ungerade

Dabei steht aber immer eine Person frei (das ist der Platz $n-1$). Der Tisch hat zwei Seiten; auf der oberen Seite ist der erste Platz frei, der nächste hat die Nummer 0, dann folgt, 1 usw. bis ${{n-1} \over 2}-1$. Die andere Seite des Tisches wird von links weg mit dem Platz ${{n-1} \over 2}$, gefolgt von der nächsten Zahl, usw. bis $n-1$ benannt.

${\begin{array}{c|c|c|c|c|c|c|c}\\&0&1&2&\cdots &i&\cdots &{{n-1} \over 2}-1\\\hline n-1&n-2&n-3&n-4&\cdots &j&\cdots &{{n-1} \over 2}\end{array}}$

In der obigen Darstellung sind die Plätze dargestellt. Die Personen haben die Gleichen Nummern ($0\cdots n-1$). Zu Beginn nehmen die Personen die gleichen Plätze ein, die ihrer eigenen Nummer entsprechen, dann prosten sich alle möglichen Gegenüber ($0\leftrightarrow (n-2),1\leftrightarrow (n-3),\cdots$) zu; der Platz $n-1$ hat Pause. Dann wandert jede Person zu dem Platz mit der nächst höheren Nummer weiter. Von Platz $n-1$ wird zu Platz 0 gewechselt.

Der allgemeine Platz $i$ hat das Gegenüber $j$. Um von $i$ aus bis zu $j$ zu gelangen, muss man die Anzahl an Plätzen rechts von $i$ zweimal (oben und unten) überspringen. Rechts von $i$ sind ${{n-1} \over 2}-1-i$ Plätze. Im Folgenden gilt $i$ ist immer "oben" und $i\leq {{n-1} \over 2}-1$ und $j$ ist immer "unten" und $j\geq {{n-1} \over 2}$.

${\begin{array}{lcl}j&=&i+2{\Big (}{{n-1} \over 2}-1-i{\Big )}+1\\&=&i+n-1-2-2i+1\\&=&n-2-i\\i&=&n-2-j\\j-i&=&n-2-2i\\&=&j-(n-2-j)\\&=&2j-(n-2)\end{array}}$

$j-i$ sind die "Schritte", die man in der Zählung vom Platz $i$ aus weiterwandern muss um zu Platz $j$ zu gelangen. Um vom Platz $j$ zum Platz $i$ zu gelangen sind $i-j$ Schritte nötig - das ist die gleiche Zahl - nur negativ. Diese negativen Zahlen (dargestellt im Restklassenraum $n$) sind es, die über das Funktionieren bzw. nicht Funktionieren entscheiden!

Sitzt am Platz $i$ die Person $p$, dann ist ihr Gegenüber die Person $p+(n-2)-2i{\pmod {n}}$. Das sind $(n-2)-2i$ Schritte nach vor.

In die andere Richtung: Von Platz $j$ zu Platz $i$ sind es $(n-2)-2i$ Schritte zurück - oder $2i-(n-2)$ Schritte nach vor (weil das eine negative Zahl ist. Will man eine positive Zahl (um alle Schritte besser vergleichen zu können), dann ist das der Wert $2i-(n-2){\pmod {n}}$. Um eine positive Zahl (zwischen 0 und $n-1$) zu bekommen, braucht man (in diesem Fall) nur $n$ dazuzählen:

Failed to parse (unknown function "\begin{array}"): {\displaystyle \begin{array} 2i-(n-2)+n = \\ 2i-n+2+n = \\ 2i+2n+2 \end{array}}

Noch'mal - um vom Platz $i$ zu Platz $j$ zu gelangen bzw. von $j$ zu $i$ braucht man die folgenden Schritte:

Failed to parse (unknown function "\begin{array}"): {\displaystyle \begin{array} i -> j & n - 2 - 2i \\ j -> i & 2i+2n+2 \end{array}}

Die erste Zahl ist sicher ungerade (weil n ungerade ist) - die zweite Zahl ist sicher gerade (wegen dem Faktor 2).

In die andere Richtung: Das gegenüber der Person $p$ auf Platz $j$ ist die Person $p+2j-(n-2){\pmod {n}}$. Das sind $2j-(n-2){\pmod {n}}$ Schritte nach vor.

Man kann leicht erkennen, dass, wenn eine Person an der oberen Reihe des Tisches ist, sie niemals dem gleichen Gegenüber begegnen kann. Zu prüfen gilt, ob gesichert ist, dass, wenn die Person dann an der unteren Seite des Tisches ist, sie nicht den gleichen Personen wieder begegnet.

Das wird jetzt gleich, wie ein Trick mit doppeltem Boden aussehen. Es wird gezeigt, dass es für das Gegenüber von einer Person auf Platz $i$ keinen Platz auf der anderen Seite gibt, der auch dieses Gegenüber hat. Die $i$ und $j$ der nächsten Formeln sind nicht notwendigerweise die gegenüberliegenden Plätze - es kommt nur am Schluss heraus, dass das nicht anders geht.

${\begin{array}{lcl}q&=&p+(n-2)-2i{\pmod {n}}\\q&=&p+2j-(n-2){\pmod {n}}\end{array}}$

   

${\begin{array}{lcl}p+(n-2)-2i&=&p+2j-(n-2){\pmod {n}}\\2(n-2)-2i&=&2j{\pmod {n}}\\(n-2)-i&=j\end{array}}$

Die letzte Formel ist genau, die gleiche, die den gegenüberliegenden Paltz von $i$ von weiter oben angibt. D.h. jede Person erhält nur einmal das gleiche Gegenüber!

Personzahl ist gerade - wie's nicht geht

Wenn man das um den Tisch weiterrücken, wie oben gezeigt mit geradem n durchführt, dann treffen sich nicht alle nötigen Pärchen.

Die Plätze sind wieder von 0 bis $n-1$ durchnumeriert:

${\begin{array}{c|c|c|c|c|c|c|c}\\0&1&2&3&\cdots &i&\cdots &{n \over 2}-1\\\hline n-1&n-2&n-3&n-4&\cdots &j&\cdots &{n \over 2}\end{array}}$

Diesmal könne sich alle $n \over 2$ gleichzeitig zuprosten. An der rechten Seite des Tisches haben sich die Nummern gegenüber den ungeraden $n$ geändert.

Um die Platznummer des Gegenübers von Platz $i$ zu bestimmen muss mann wieder zweimal ${n \over 2}-1-i$ und dann noch eins dazuzählen:

${\begin{array}{lcl}j&=&i+2{\Big (}{n \over 2}-1-i{\Big )}+1\\&=&i+n-2-2i+1\\&=&n-1-i\\i&=&n-1-j\\j-i&=&n-1-2i\\&=&j-(n-1-j)\\&=&2j-(n-1)\end{array}}$

Sitzt am Platz $i$ die Person $p$, dann ist ihr Gegenüber die Person $p+(n-1)-2i{\pmod {n}}$.

In die andere Richtung: Das gegenüber der Person $p$ auf Platz $j$ ist die Person $p+2j-(n-1){\pmod {n}}$.

Wieder die Frage: Kann die Person $p$, der am Platz $i$ die Person $q$ gegenübersitzt - $q$ gegenübersitzen, wenn $p$ an einem Platz $j$ (der nichts mit $i$ zu tun haben muss) sitzt?

${\begin{array}{lcl}q&=&p+(n-1)-2i{\pmod {n}}\\q&=&p+2j-(n-1){\pmod {n}}\end{array}}$

   

${\begin{array}{lcl}p+(n-1)-2i&=&p+2j-(n-1){\pmod {n}}\\2(n-1)-2i&=&2j{\pmod {n}}\\(n-1)-i&=j\end{array}}$

???