Pigeonhole-Prinzip Problem - Kreis
Ich arbeite an einem Hausaufgabenproblem mit der folgenden Anweisung:
Angenommen, es gibt eine Klasse von 2 n Schülern mit unterschiedlichen Namen, die in einer großen Show sitzen und einen Kreis erzählen. Der Lehrer gibt seine Hausaufgaben zurück, aber jeder Schüler im Kreis erhält die Hausaufgaben eines anderen Schülers. Daher erklärt sich die Klasse damit einverstanden, die Hausaufgaben an den rechts von ihnen sitzenden Schüler weiterzugeben. Wieder sind die Namen alle falsch. Für die ersten n mal sie dies tun, haben sie alle die falschen Namen Hausaufgaben. Insgesamt gibt es also n + 1 Konfigurationen, in denen jeder Schüler mit den Hausaufgaben eines anderen übereinstimmt. Zeigen Sie, dass sie, wenn sie die Hausaufgaben rechts weitergeben, irgendwann eine Konfiguration erreichen, in der 3 Schüler die Hausaufgaben mit ihren eigenen Namen haben.
Ich habe ein paar Probleme mit dem Pigeonhole-Prinzip gemacht, aber dieses gibt mir außergewöhnlich mehr Probleme. Ich habe zwei getrennte Fälle dargestellt, beide mit n = 2 , die beide zu einer Klassengröße von 4 führen. Die Großbuchstaben sind die Kinder und die Kleinbuchstaben sind die entsprechenden Hausaufgaben.
Test mit Klasse 4
Mit der obigen Startkonfiguration konnte ich nicht erreichen, dass drei Schüler gleichzeitig die richtigen Hausaufgaben haben, nur zwei gleichzeitig. Ich habe auch keine der offensichtlichen Einschränkungen gebrochen:
- Jeder Schüler erhält seine Hausaufgaben nicht anfänglich
- Jeder Schüler hat nach 1 Runde keine Hausaufgaben mehr
Der zweite Fall in den Zeichnungen soll veranschaulichen, was passieren würde, wenn der Schüler links von ihm seine Hausaufgaben hätte, dh nur einen Durchgang benötigt. Ich bin mir jedoch ziemlich sicher, dass die Frage besagt, dass dies seitdem nicht erlaubt ist
Daher erklärt sich die Klasse damit einverstanden, die Hausaufgaben an den rechts von ihnen sitzenden Schüler weiterzugeben. Wieder sind die Namen alle falsch.
Das bedeutet, dass die Runde nach dem ersten Durchgang auch sicherstellen muss, dass niemand seine Hausaufgaben hat. Ich vertraue darauf, dass die Frage in ihren Vorschlägen richtig ist, aber ich habe Probleme, sie zu verstehen und das Pigeonhole-Prinzip anzuwenden. Sind die "Löcher" die Kinder und die "Tauben" die Hausaufgaben und wenn ja, wie würde man rechnen, wenn es nicht so einfach ist wie eine Taube im Loch, sondern die richtige Taube im richtigen Loch? Jede Hilfe wäre dankbar.
Antworten
Wenn wir eine volle durchführen $2n - 1$Pässe, dann hat jeder seine Hausaufgaben genau einmal gesehen. Wir wissen das zuerst$n$ geht vorbei, der erste $n + 1$Konfigurationen hat niemand ihre Hausaufgaben gesehen. Wenn wir weiter in den Rest gehen$n - 1$Konfigurationen, und höchstens 2 Schüler sehen ihre Hausaufgaben in jeder Konfiguration, höchstens wie viele Schüler haben ihre Hausaufgaben gesehen? Wie widerspricht dies dem, was wir bereits gesagt haben?
So können Sie es angehen. Füllen Sie die Lücken selbst aus.
Im Allgemeinen ist es beim Auftragen von PP sehr wichtig, die Löcher und Tauben genau zu kennen. Sie zu definieren ist oft ein guter Anfang, also:
Lassen Sie die Löcher "Konfigurationen sein, in denen die Schüler Hausaufgaben bekommen, gedreht$k$mal ".
Lassen Sie die Tauben sein" Schüler hat die richtigen Hausaufgaben ".
Angenommen, diese Definitionen sind die richtigen, lassen Sie uns verfolgen, wie PP funktionieren könnte:
Wie viele Tauben gibt es?
Wie viele Löcher können wir maximal haben, um sicherzustellen, dass es ein Loch mit 3 Tauben gibt?
Können wir zeigen, dass wir höchstens so viele Löcher haben? Wenn nein, wie können wir die Löcher (oder Tauben) optimieren?
Es besteht eine gewisse Unsicherheit über die genaue Anzahl der Löcher.
- Wenn die Anzahl der Löcher ist $n-1$ (was bedeutet, dass es gibt $n+1$ Konfigurationen, die völlig nicht übereinstimmen), dann arbeitet PP direkt.
- Wenn die Anzahl der Löcher ist $n$ (was bedeutet, dass es gibt $n$Konfigurationen, die völlig unpassend sind), dann ist die Frage falsch. Insbesondere gilt die Aussage für gerade$n$ und falsch für ungerade $n$. Dies kann durch 1) einen Widerspruch für "genau 2 Papiere passen für$n$ ist gerade ", und 2) Konstruieren eines Falls für" genau 2 Papiere passen zu $n$ ist ungerade".