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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {{n-1} \over 2}} , gefolgt von der nächsten Zahl, usw. bis Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-1} benannt.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \leftrightarrow (n-2) , 1 \leftrightarrow (n-3) , \cdots} ) zu; der Platz Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-1} hat Pause. Dann wandert jede Person zu dem Platz mit der nächst höheren Nummer weiter. Von Platz Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-1} wird zu Platz 0 gewechselt.

Der allgemeine Platz Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} hat das Gegenüber $j$. Um von Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} aus bis zu Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} zu gelangen, muss man die Anzahl an Plätzen rechts von Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} zweimal (oben und unten) überspringen. Rechts von Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} sind Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {{n-1} \over 2}-1 - i} Plätze.

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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j - i} sind die "Schritte", die man in der Zählung vom Platz Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} aus weiterwandern muss um zu Platz Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} zu gelangen.

Sitzt am Platz Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} die Person Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} , dann ist ihr Gegenüber die Person Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k + (n - 2) - 2i \pmod{n}} .

In die andere Richtung: Das gegenüber der Person Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} auf Platz Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} ist die Person $k+2j-(n-2){\pmod {n}}$.

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.