Black-Box-Zählung auf 19 mit nur 2 Bit und nur umschaltbar?

Question

Ein Schüler fragte dies auf einer anderen Seite, bekam aber keine Antworten. Ich hatte ein paar Stiche darauf, fand es aber ziemlich schwierig.

Wenn Sie dies nur mit den Schaltern tun, würde ein Komprimierungsverhältnis von 9: 1 erforderlich sein. Ich denke, der Trick liegt in den Regeln, die Sie den Schülern zuweisen. Vielleicht braucht jeder Schüler eine andere Reihe von Regeln?

Ich habe darüber nachgedacht, viele Iterationen zuzulassen, bei denen keine Antwort auftaucht, indem ich den Schülern nur in der richtigen Reihenfolge beachtet. Ich habe auch darüber nachgedacht, die Schülernummer als binär zu codieren und diese mit den Bits aus den Schaltern zu kombinieren, um mehr Bits zu erreichen, aber das ist immer noch ein Komprimierungs-/Validierungsproblem: Auch wenn eines dieser Bits für die Parität verwendet wurde Sie hätten immer noch ein großes Potenzial für falsch positive Ergebnisse.

Vermutlich wäre das Problem nicht gefragt worden, ob es keinen Weg gab, es zu tun. Vielleicht ist dies ein häufiges Problem in Comp-Sci-Kursen und bekannt? Wie auch immer, ohne weiteres ...

"Hier ist ein Problem, das ich für eine Computerklasse habe. Es scheint mir eine Art mathematisch und könnte möglicherweise den Binärcode beinhalten. Ich bin mir nicht sicher, dass alle meine Ideen zu Sackgassen führen.

Neunzehn Studenten haben die Möglichkeit, einen Preis zu gewinnen, indem sie ein Spiel spielen. Nach einiger Zeit, um sich für eine Strategie zu entscheiden, werden alle Schüler in separate schalldichte Isolationskammern versetzt, die absolut keine Möglichkeit haben, zu kommunizieren.

Das Spiel wird wie folgt gespielt. Es gibt zwei Lichtschalter in einem Raum, der in der "Aus" -Position beginnt. Ich werde die Schüler einzeln in diesen Raum bringen. Jedes Mal, wenn ein Schüler den Raum betritt, muss er oder sie einen der Schalter umdrehen. Alle Schüler werden schließlich in den Raum gebracht, aber einige Schüler können mehr als einmal eingebracht werden.

Wenn mir eine Person richtig sagt, dass jeder im Raum war, gewinnt jeder den Preis. Wenn mir jedoch jemand falsch sagt, dass jeder im Raum war, wird jeder den Alligatoren gefüttert! Beachten Sie, dass entweder alle Studenten den Preis gewinnen oder jeder verliert.

Ihre Aufgabe ist es, eine Strategie zu bestimmen, mit der jeder den Preis gewinnen kann (und nicht von Alligatoren gefressen werden kann). "

Answer 1

Das klingt nach einer Variation der Gefangene und das Lichtschalter Rätsel, wo ein Gefangener als "Zähler" bezeichnet wird und alle anderen "ihre Zählung" nur einmal erhöht.

Vermutlich würde der Zähler einen Schalter einschalten, und wenn Sie noch nie gezählt worden wären, schalten Sie diesen Schalter aus. Der andere Schalter wäre "Müll". Sobald der Schalter 18 Mal den Schalter ausgeschaltet hat, weiß er, dass alle anderen Schüler im Raum waren.

Answer 2

Die Art und Weise, wie das Problem formuliert ist, kann der Organisator/Lehrer sicherstellen, dass er niemals den Preis vergeben muss: Erlauben Sie jedem Schüler wiederum in den Raum - was es dem Zähler nur ermöglicht, einen anderen Schüler zu zählen. Dann nur eine Untergruppe der Schüler wiederholen - sagen Sie 3 von ihnen.

Dann kann der Zähler zwei andere Schüler zählen, dann stecken bleiben oder die Theke geht nie zurück in den Raum.

Dies erfüllt die angegebenen Bedingungen: Jeder geht mindestens einmal in den Raum, und einige Schüler gehen mehrmals ein.

Damit die Schüler gewinnen können, müssen Sie die Bedingung hinzufügen, dass zwischen den Besuchen der einzelnen Schüler im Switch -Raum eine begrenzte Begrenzung besteht.