Black-box comptant jusqu'à 19 avec seulement 2 bits, et seulement modifiable?

Question

Certains élèves ont demandé cela sur un autre site, mais n'ont pas obtenu de réponse. J'ai eu quelques coups de poignard, mais je l'ai trouvé assez difficile. Le faire avec seulement les commutateurs exigerait un taux de compression de 9: 1, donc je suppose que l'astuce est tout à fait dans les règles que vous attribuez aux étudiants. Peut-être que chaque élève a besoin d'un ensemble de règles différent?

J'ai envisagé d'autoriser de nombreuses itérations sans réponse, en ne prêtant attention qu'aux élèves dans la bonne séquence. J'ai aussi pensé à encoder le nombre d'étudiants en binaire, et en combinant cela avec les bits des commutateurs, pour obtenir plus de bits, mais c'est toujours un problème de compression/validation: même si un de ces bits était utilisé pour la parité , vous auriez encore un gros potentiel de faux positifs.

Vraisemblablement, le problème n'aurait pas été demandé s'il n'y avait pas moyen de le faire. Peut-être que c'est un problème commun dans les cours comp-sci et bien connu? De toute façon, sans plus tarder ...

"Voici un problème que j'ai pour un cours d'informatique, il me semble assez mathématique et pourrait impliquer le code binaire, je ne suis pas sûr, toutes mes idées mènent à impasses.

Dix-neuf étudiants ont la possibilité de gagner un prix en jouant un jeu. Après un certain temps pour décider d'une stratégie, tous les étudiants seront placés dans des chambres d'isolement insonorisées séparées sans aucun moyen de communiquer.

Le jeu se joue comme suit: Il y a deux interrupteurs dans une pièce qui vont commencer dans la position «off», je vais amener les élèves dans cette pièce, une à la fois. puis il ou elle doit retourner l'un des commutateurs. Tous les élèves finiront par être amenés dans la salle, mais certains étudiants peuvent être amenés plus d'une fois.

Si une personne me dit correctement que tout le monde a été dans la salle, alors tout le monde gagne le prix. Cependant, si quelqu'un me dit à tort que tout le monde a été dans la pièce alors tout le monde sera nourri aux alligators! Notez que tous les étudiants gagnent le prix ou bien tout le monde perd.

Votre tâche est de déterminer une stratégie qui ne manquera pas de permettre à chacun de gagner le prix (et ne pas être mangés par des alligators). »

Answer 1

Cela ressemble à une variante du Prisoners and the Light Switch riddle, où un prisonnier est désigné comme un «compteur» et tout le monde «incrémente leur compte» une seule fois

Vraisemblablement, le compteur allumer un interrupteur, et si vous n'aviez jamais été compté, vous éteignez cet interrupteur, l'autre interrupteur serait " Une fois que le compteur a éteint l'interrupteur 18 fois, il sait que tous les autres étudiants sont allés dans la pièce

Answer 2

De la façon dont le problème est formulé, l'organisateur/enseignant peut s'assurer qu'il n'a jamais à donner le prix: Permettre à chaque étudiant dans la pièce à tour de rôle - qui permet seulement au Compteur de compter un autre étudiant. Alors seulement itérer un sous-ensemble des étudiants - disons 3 d'entre eux.

Ensuite, soit le Compteur peut compter deux autres étudiants, puis rester coincé, ou le Compteur ne retourne jamais dans la pièce.

Ceci satisfait aux conditions spécifiées: Tout le monde entre dans la pièce au moins une fois, et certains étudiants y vont plusieurs fois.

Pour permettre aux étudiants de gagner, vous devez ajouter la condition qu'il y ait une limite finie entre les visites d'un seul étudiant à la salle de commutation.