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.

Plätze

${\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}}$

Offsets zu Gegenüber

${\begin{array}{c|c|c|c|c|c|c|c}\\&n-2&n-4&n-6&\cdots &n-2k&\cdots &1\\\hline --&2&4&6&\cdots &2k&\cdots &n-3\end{array}}$

Die Plätze als auch die Personen haben Zahlen von 0 bis $n-1$. Die Personen nehmen zu Beginn an den Plätzen platz, die ihrer eigenen Zahl entsprechen. Dann prosten sich die jeweiligen Gegenüber zu - in der Darstellungen prosten die Leute "oben" jenen "unten" zu. Im nächsten Schritt wechseln alle Personen einen Platz weiter und das Zuprosten beginnt von neuem. Es prosten sich ($n$ ist ungerade immer ${n-1} \over 2$ Personen gleichzeitig zu. Nach $n$ gegenseitigen Zuprostungen und Weiterrückungen sind wieder alle am gleichen Platz, wie zuvor. Es haben also ${{n-1} \over 2}n$ Zuprostungen stattgefunden - das ist genau ${\binom {n}{2}}$! Es haben sich aber nur wirklich alle zugeprostet, wenn sich während der $n$ Weiterrückungen nicht die gleichen Pärchen wieder begegnet sind. Der Beweis besteht darin genau das zu zeigen - und das gelingt mit den Offsets.

Die Offsets geben an wie weit das Gegenüber "entfernt" ist. Dabei wird im Restklassenring modulo $n$ gerechnet. D.h. dass es nur Zahlen zwischen 0 und $n-1$ gibt. Nach $n-1$ kommt nicht $n$ - sondern 0. Vor 0 kommt $(n-1)$. Z.B. ist das Gegenüber von Platz 2 der Platz $(n-4)$. Der Offset auf Platz ist 2 ist $(n-6)$, weil $2+(n-6)=n-4$ ist. Der Offset an Platz $(n-4)$ ist 6, da $(n-4)+6=n+2$ ist wegen der Modulorechnung muss man $n$ subtrahieren um in den Zielbereich 0 bis $n-1$ zukommen und erhält 2.

Bei den Plätzen sind die allgemeinen Plätze $i$ mit dem Gegenüber $j$ zur Analyse "vorgesehen". Nach Platz $i$ kommen noch ${{n-1} \over 2}-1-i$ Plätze auf dieser Seite des Tisches - auf der anderen Seite nochchmals so viele und dann noch einer bis zum Platz $j$.

${\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)$ ist der Offset von Platz $i$ - $(i-j)$ oder $-(j-i)$ ist der Offset von Platz $j$.

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

Da $i-j$ negativ ist wurde $n$ dazugezählt (Restklassenring modulo $n$). Man erkennt auch, dass der Offset der "oberen" Seite ($j-i$) immer ungerade ist (weil $n$ ungerade ist) - und der Offset der "unteren" Seite immer gerade ist (wegen der Faktoren 2). D.h. aber auch, dass "oben" alle möglichen ungeraden Offests und "unten" alle möglichen geraden Offsets vorkommen - somit alle möglichen Offsets vorkommen. Darum treffen sich alle möglichen Pärchen!

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:

Plätze

${\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}}$

Offsets zu Gegenüber

${\begin{array}{c|c|c|c|c|c|c|c}\\n-1&n-3&n-5&n-7&\cdots &i&\cdots &1\\\hline 1&3&5&7&\cdots &j&\cdots &n-1\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:

<math>\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 - (