Zeigen Sie mit Induktion, dass eine solche Reihung immer möglich ist, egal was sie entscheidet.

Question

Ein überaus beliebtes Partyspiel besteht bekanntlich darin, die Gäste der Größe nach zu sortieren. Diesmal haben wir uns aber etwas besonderes ausgedacht: wir wollen statt dessen, dass sich die Gäste wie folgt aufstellen: $$ G_{1}<G_{2}<G_{3}>G_{4}<G_{5}>\cdots<G_{n} $$ Ob zwischen \( G_{i} \) und \( G_{i+1} \) ein "\(<\)" oder "\( >\)" steht, entscheidet die Gastgeberin. Zeigen Sie mit Induktion, dass eine solche Reihung immer möglich ist, egal was sie entscheidet.

Ich stehe völlig auf der Leitung. Kann mir jemand vielleicht bitte Tipps geben wie man am Besten anfängt bzw. die Induktionsvoraussetzung aufstellt?

Comments

Angenommen \( G_i > G_j \) gilt auch, wenn die Gäste \( G_i \) und \( G_j \) exakt gleich groß sind.

Falls gar kein Gast kommt gibt es wohl kein Spiel.

Für einen Gast ergibt das Spiel keinen Sinn. Der Gast würde dann ganz alleine in der Raummitte stehen, immerhin werden die Abstandsregeln dann eingehalten!

(IA) Bei 2 Gästen können nur die Fälle \( G_1 > G_2 \) und \( G_1 < G_2 \) eintreten. Im ersten Fall stellt man den größeren halt links hin, sonst rechts.

(IV) Die Aussage gelte für n Gäste.

(IS) Bei n+1 Gästen kann die Gastgeberin entweder

1. \( G_n > G_{n+1} \) oder

2. \( G_n < G_{n+1} \) auswählen.

Im ersten Fall sucht man sich den kleinsten aus der Gruppe, nennt ihn \( G_{n+1} \) und schickt ihn Knabberzeug holen. In der Zwischenzeit sortiert man gemäß (IV) die verbleibenden n Gäste. Wenn der kleinste Gast das Knabberzeug geholt hat, stellt man ihn mit 1,5m Abstand ganz rechts an die Menschenkette. Er ist offensichtlich kleiner als Gast \( G_n \).

Im zweiten Fall muss man den größten Gast in den Keller schicken, um erfrischendes Mineralwasser mit Hopfengeschmack hochzutragen. Der Rest funktioniert aber vollkommen analog.

Answer 1

1) Was ist, wenn

$$G_1=G_2$$

2)

Ind ANF

Sei

$$G_1 <G_2 <...<G_{n-1} <G_n$$

so ist es möglich, die erste Relation zu wechseln.

$$G_n >G_1 <G_2 <...<G_{n-1} $$

es ist auch möglich, die k-te Relation zu wechseln

$$(G_1 <G_2 <...G_{k-1}<G_k)<$$$$(G_{k+1}<G_{k+2}<...<G_{n-1} <G_n)$$

$$(G_{k+1} <G_{k+2} <...<G_{n-1} <G_n) >$$

$$(G_1 <G_2 <...G_{k-1}<G_k)$$

Es ist also möglich eine Relation zu wechseln

Induktion Annahme

?

Weiter komme ich zur Zeit nicht.

Was müssen wir annehmen?

Dass wir die ersten n beliebig gewechselt haben?

Und schließen, dass wir dann auch die n-te Relation wechseln können?

Oder müssen wir annehmen, dass wir n Relationen gewechselt haben und auch die (n+1)-te Relation wechseln können?

Spannende Frage, habe momentan aber leider keine Zeit mehr.

Comments

es ist auch möglich, die k-te Relation zu wechseln
Tatsächlich wechselst du eine ganz andere als die k-te.

Mach lieber eine Induktion nach der Anzahl der Gäste, dann ist es ganz einfach.

---

Warum wechsel ich nicht die k-te Relation ?

Wenn es ganz einfach ist, dann schaff ich das noch.

Ind. Annahme

2 Gäste, können beliebig sortiert werden.

Ind Annahme, n Gäste wurden beliebig sortiert.

Jetzt kommt der( n+1)te Gast.

Es gibt also x Gäste die kleiner sind als er und (n-x) Gäste, die größer sind.

Ich bin nicht bei der Sache, bis später.

---

Warum wechsel ich nicht die k-te Relation ?

Wenn du in G1 < G2 < G3 < G4 < G5 < G6 das vierte Relationszeichen (das <-Zeichen zwischen G4 und G5) wechseln willst, dann schreibst du G5 < G6 > G1 < G2 < G3 < G4 und hast dann tatsächlich das Zeichen an Position 2 gewechselt.

---

Danke

............

Gruß, Hogar

---

Danke , jetzt ist auch der Groschen gefallen. Ich betrachte das letzte Zeichen bei > kommt hinten der kleinste Gast und die anderen wie gehabt, falls es ein < ist steht hinten der größte Gast.

So leicht. Manchmal hilft es zwischendurch etwas anderes zu machen.