In der Ausgangsposition, wie unten dargestellt, befinden sich alle Papiere in einem Stapel auf dem ersten Stapel

apartment

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. Du darfst nichts aufschreiben, noch darfst du die Zählung in deinem Gedächtnis behalten. Da Datenströme in der digitalen Welt allgegenwärtig sind – Telefongespräche, Kreditkartentransaktionen und Netflix-Filme beispielsweise sind alle Datenströme – ist es auch diese Art von Algorithmus.

Sie sind dabei, einen der wichtigsten frühen Streaming-Algorithmen kennenzulernen. In der Ausgangsposition, wie unten dargestellt, befinden sich alle Papiere in einem Stapel auf dem ersten Stapel.

Das heutige Rätsel ist knifflig! Ich meine Trickle-y. 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. Jetzt puffern!

Die große Abstimmungs-Denkaufgabe

Zwischen den Kandidaten A, B, C und D findet eine Wahl statt. 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). Ich bin immer auf der Suche nach tollen Rätseln. Es gibt einen viel schnelleren Weg. Eine Möglichkeit wäre, die Zwei-Gruppen-Strategie zu verwenden, wobei die Kandidaten in zwei Koalitionen aufgeteilt werden, sagen wir A&B vs. Wenn ein Kandidat dies getan hat, müssen Sie sagen, wer es ist.

Aber da ist ein Fang. BITTE KEINE SPOILER, sondern diskutieren Sie über Ihre bevorzugten Streaming-Dienste.

UPDATE: Klicken Sie hier, um die Lösung zu lesen.

Wenn Sie sich fragen, was das Bewegen von Stimmzetteln mit Streaming zu tun hat, hier ist die Analogie. 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. Usw. Sie dürfen nicht zählen, was analog dazu ist, dass Sie kein Gedächtnis zum Speichern von Informationen verwenden können. Die Idee dahinter war, so schnell wie möglich eine vollständige Auslesung der eingehenden Daten zu erhalten und dabei so wenig Speicher wie möglich zu verbrauchen. Kannst du es finden?

Ich werde um 17:00 Uhr in Großbritannien mit einer Lösung und einer Diskussion zurück sein. Es dreht sich alles um Ströme.

Die Quelle des Rätsels ist ein "Streaming-Algorithmus", eine Art Verfahren in der Informatik, das Daten analysiert, wenn sie in einem Stream ankommen, anstatt darauf zu warten, dass die Daten in einem Speicher gespeichert werden.

Die ersten Streaming-Algorithmen wurden in den 1980er Jahren entwickelt. 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. 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. Jeder Stimmzettel ist ein Stück eingehender Daten. Wir können jetzt herausfinden, welcher Stapel die meisten Stimmzettel hat, indem wir sie abwechselnd zurück auf den ersten Stapel legen. Nun, Sie sind es, wenn Sie das heutige Rätsel lösen. Kannst du es machen?

Wie so oft ist es hilfreich, das Problem zu vereinfachen, um zu sehen, ob es uns Erkenntnisse liefert. Nennen Sie dies die „Zwei-Gruppen-Strategie".

Versuchen Sie nun, auf vier Kandidaten zu skalieren, A, B, C und D. C&D. Nach 100 Zügen ist der erste Stapel leer, der zweite Stapel enthält alle As und der dritte Stapel alle Bs. 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. Die Stimmzettel liegen offen, sodass Sie immer sehen können, welcher Kandidat auf dem Stimmzettel ganz oben auf dem Stapel eine Stimme erhalten hat. Bei Interesse an Ihrer Schule wenden Sie sich bitte an uns.

. 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 etwas über die Gesamteigenschaft des gesamten Streams erfahren können: ob es einen Mehrheitswert gibt oder nicht, und wenn ja es ist was es ist.

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. 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. Sie verschieben den obersten Stimmzettel von Stapel 1 entweder auf Stapel 2 oder Stapel 3. Sie dürfen die Stimmzettel nicht auszählen. Das heißt, Sie dürfen in keiner Weise Zahlen verwenden. Es gibt zwei weitere Positionen für Stapel, aber sie sind noch leer.

Am Anfang hat Stapel 1 100 Stimmzettel und die anderen beiden Stapel haben null Stimmzettel

Es gibt nur zwei Startmöglichkeiten Kannst du es lösen? Die Wissenschaft des Streamings | Mathematik