Heute früh habe ich das folgende Rätsel gestellt, das hier mit seiner Lösung wiederholt wird.
Die Inspiration für das Problem ist einer der frühesten und wichtigsten Streaming-Algorithmen, der Vorgänger der Technologie, die von Streaming-Diensten wie Netflix und Spotify verwendet wird.
Die große Abstimmungs-Denkaufgabe
Zwischen den Kandidaten A, B, C und D findet eine Wahl statt. Sie erhalten einen Satz von 100 ausgefüllten Stimmzetteln und Ihre Aufgabe besteht darin, herauszufinden, ob einer der Kandidaten die Gesamtmehrheit hat, dh 51 oder mehr Stimmen erhalten hat. Wenn ein Kandidat dies getan hat, müssen Sie sagen, wer es ist.
Aber da ist ein Fang. Sie dürfen die Stimmzettel nicht auszählen. Das heißt, Sie dürfen in keiner Weise Zahlen verwenden. Du darfst nichts aufschreiben, noch darfst du die Zählung in deinem Gedächtnis behalten. Stattdessen müssen Sie eine clevere Strategie entwickeln, die beinhaltet, sofortige Entscheidungen über jeden Stimmzettel zu treffen, wenn Sie ihn sehen.
Alles, was Sie tun dürfen, ist, die Papiere zwischen drei Stapeln auf einem Tisch zu verschieben. In der Ausgangsposition, wie unten dargestellt, befinden sich alle Papiere in einem Stapel auf dem ersten Stapel. Die Stimmzettel liegen offen, sodass Sie immer sehen können, welcher Kandidat auf dem Stimmzettel ganz oben auf dem Stapel eine Stimme erhalten hat. Es gibt zwei weitere Positionen für Stapel, aber sie sind noch leer.
Es sind nur zwei Optionen zu starten. Sie verschieben den obersten Stimmzettel von Stapel 1 entweder auf Stapel 2 oder Stapel 3. Für Ihren nächsten Zug können Sie dasselbe noch einmal tun, oder Sie können den Stimmzettel, der sich auf Stapel 2 oder Stapel 3 befindet, auf einen anderen Stapel verschieben. Usw. In jedem Stadium können Sie nur den Stimmzettel, der sich oben auf einem Stapel befindet, auf einen anderen Stapel verschieben.
Ihre Aufgabe ist es, eine Strategie zu finden, die Ihnen sagt, ob ein Kandidat die Gesamtmehrheit (dh 51 oder mehr Stimmen) hat, indem Sie einfach die Stimmzettel zwischen den Stapeln verschieben. Kannst du es machen?
Der Hinweis
Wie so oft ist es hilfreich, das Problem zu vereinfachen, um zu sehen, ob es uns Erkenntnisse liefert. Betrachten wir den Fall, in dem es nur 2 Kandidaten gibt, A und B.
Eine einfache Strategie lautet wie folgt: Wenn wir A auf dem ersten Stapel sehen, legen wir es auf den zweiten Stapel, und wenn wir B auf dem ersten Stapel sehen, legen wir es auf den dritten Stapel. Nach 100 Zügen ist der erste Stapel leer, der zweite Stapel enthält alle As und der dritte Stapel alle Bs. Wir können jetzt herausfinden, welcher Stapel die meisten Stimmzettel hat, indem wir sie abwechselnd zurück auf den ersten Stapel legen. Wenn am Ende noch Stimmzettel auf dem zweiten Stapel übrig sind, dann hat A mindestens 51 Stimmen, und wenn noch Stimmzettel auf dem dritten Stapel übrig sind, dann B. Nennen Sie dies die „Zwei-Gruppen-Strategie“.
Versuchen Sie nun, auf vier Kandidaten zu skalieren, A, B, C und D. Eine Möglichkeit wäre, die Zwei-Gruppen-Strategie zu verwenden, wobei die Kandidaten in zwei Koalitionen aufgeteilt werden, sagen wir A&B vs. C&D. Wenn eine der Koalitionen mehr als 51 Stimmen hat, wenden wir die Zwei-Gruppen-Strategie noch zweimal an – einmal für jedes Mitglied der siegreichen Koalition. Diese Strategie funktioniert, ist aber nicht sehr effizient: Sie beruht darauf, Papiere mindestens 500 Mal zwischen Stapeln zu verschieben und Koalitionen zu verfolgen. Es gibt einen viel schnelleren Weg. Kannst du es finden?
Lösung
Ich werde zuerst den Algorithmus erklären und danach die Argumentation erklären.
SCHRITT 1. Bewegen Sie den obersten Stimmzettel von Stapel 1 zu Stapel 2
SCHRITT 2: Sehen Sie sich die Kandidaten an, die auf den obersten Stimmzetteln von Stapel 1 und Stapel 2 ausgewählt wurden. Wenn sie gleich sind, legen Sie den obersten Stimmzettel von Stapel 1 oben auf Stapel 2, wie unten gezeigt.
Wenn die auf dem obersten Stimmzettel von Stapel 1 und dem obersten Stimmzettel von Stapel 2 ausgewählten Kandidaten unterschiedlich sind, legen Sie diese beiden Stimmzettel wie unten beschrieben auf Stapel 3.
SCHRITT 3: Wenn Stapel 2 leer ist, wenden Sie SCHRITT 1 an. Wenn Stapel 2 Stimmzettel enthält, wenden Sie SCHRITT 2 an. Fahren Sie fort, bis in Stapel 1 keine Stimmzettel mehr übrig sind. Am Ende des Vorgangs werden entweder Stimmzettel in Stapel vorhanden sein 2 oder es wird leer sein. Wenn es leer ist, hat kein Kandidat eine Gesamtmehrheit. Wenn es nicht leer ist, werden alle Stimmzettel in Stapel 2 für denselben Kandidaten sein, und es kann der Fall sein, dass dieser Kandidat eine Gesamtmehrheit hat oder nicht. Der letzte Schritt besteht darin, zu prüfen, ob dieser Kandidat eine Gesamtmehrheit hat. Wir können dies mit der Zwei-Gruppen-Strategie tun, indem wir den Kandidaten gegen eine Koalition der anderen drei testen, oder etwas schneller, diese zweite Strategie erneut verwenden, indem wir Stapel 1 als „Stapel 3“-Dump verwenden.
Warum das funktioniert:
Was der Algorithmus macht, ist, dass Stapel 2 ein „Klicker“ für den Kandidaten in Stapel 2 ist. Wenn wir diesem Stapel einen Stimmzettel hinzufügen, klickt die Gesamtzahl um eins nach oben, und wenn wir einen Stimmzettel aus diesem Stapel entfernen, klickt er nach unten einzeln.
Es ist zu keinem Zeitpunkt für Stapel 2 möglich, Stimmzettel für mehr als einen Kandidaten zu haben. Es ist möglich, dass Stapel 2 mit dem Stapeln von Stimmzetteln für beispielsweise A beginnt und mit einem Stapel Stimmzettel für beispielsweise D endet. Dieser Wechsel kann jedoch nur erfolgen, wenn der Prozess einen Punkt durchläuft, an dem Stapel 2 leer ist.
Am Ende des Vorgangs muss Stapel 3 eine gerade Anzahl Stimmzettel enthalten, da dort Stimmzettel paarweise abgelegt werden. Jedes Paar hat Stimmen für zwei verschiedene Kandidaten, und daher hat kein einzelner Kandidat in Stapel 3 mehr als 50 Prozent der Stimmen in Stapel 3. (Das Beste, worauf sie hoffen können, sind 50 Prozent, dh ein Stimmzettel in jedem Paar.)
Somit ist der einzige Kandidat, der eine Chance auf eine Gesamtmehrheit hat, der Kandidat in Stapel 2. Wenn wir dies überprüfen, indem wir die Strategie erneut anwenden und Stapel 1 als „Stapel 3“-Dump verwenden, dann wird Stapel 1 eine gleiche Anzahl von haben Kandidaten- und Nicht-Kandidaten-Stimmzettel, und der Status von Stapel 2 sagt uns, ob der Kandidat eine Mehrheit hat oder nicht.
Sauber!
Diese Lösung ist die Basis für die Boyer-Moore Mehrheitswahlalgorithmusveröffentlicht von Robert S. Boyer und J. Strother Moore im Jahr 1981. Dieser und ähnliche Algorithmen werden heute in großem Umfang in der Telekommunikation und der Analyse von Webanfragen verwendet.
Nur um die Analogie zwischen dem Puzzle und den Streaming-Algorithmen deutlich zu machen: Stellen Sie sich vor, dass jeder Stimmzettel ein Stück eingehender Daten ist. Sie dürfen nicht zählen, was analog dazu ist, dass Sie kein Gedächtnis zum Speichern von Informationen verwenden können. Stattdessen müssen Sie eine sofortige Entscheidung darüber treffen, was zu tun ist, sobald jedes Datenelement eintrifft, in der Hoffnung, dass Sie sehr schnell einige allgemeine Eigenschaften des gesamten Streams lernen können.
Ich hoffe, du bist mit dem Strom gegangen! Bitte sprudeln Sie mit Ihren Kommentaren unten.
Das heutige Rätsel wurde von Pierre Chardaire, einem pensionierten Informatiker, entwickelt.
Ich stelle hier alle zwei Wochen an einem Montag ein Rätsel auf. Ich bin immer auf der Suche nach tollen Rätseln. Wenn Sie einen vorschlagen möchten, senden Sie mir eine E-Mail.
Ich halte Schulvorträge über Mathematik und Rätsel (online und persönlich). Bei Interesse an Ihrer Schule wenden Sie sich bitte an uns.