Trouver votre propre numéro dans une boîte

https://stackoverflow.com/questions/34345

09-06-2019
|

Question

100 (ou certains nombre pair 2N :-) ) les détenus sont dans une chambre en A.Ils sont numérotés de 1 à 100.

Un par un (à partir de prisonnier n ° 1 de prisonnier #100, dans l'ordre), ils vont être laissé dans une salle de B dont 100 cases (numérotées de 1 à 100) les attendent.À l'intérieur de l' (fermé) boîtes sont des nombres de 1 à 100 (les chiffres à l'intérieur des boîtes de permutation au hasard!).

Une fois à l'intérieur de la salle B, chaque prisonnier arrive à ouvrir 50 boîtes (il choisit celui qu'il s'ouvre).Si il trouve le numéro qui lui a été assigné dans l'un de ces 50 boîtes, le prisonnier arrive à marcher dans une salle de C et toutes les boîtes sont fermées à nouveau avant la prochaine, marche dans la salle B de la salle A.Sinon, tous les prisonniers (dans les salles A, B et C) se fait tuer.

Avant d'entrer dans la salle B, les prisonniers peuvent s'entendre sur une stratégie (algorithme).Il n'y a aucun moyen de communiquer entre les chambres (et aucun message ne peut être laissé dans la chambre de B!).

Est-il un algorithme qui maximise la probabilité que tous les prisonniers survivre?Ce que la probabilité n'est que de l'algorithme de réaliser?

Notes:

Faire les choses au hasard (ce que vous appelez "pas de stratégie"), en effet, donne une probabilité de 1/2 pour chaque prisonnier, mais alors la probabilité de chacun d'eux survivant est de 1/2^100 (ce qui est assez faible).On peut faire beaucoup mieux!
Les prisonniers ne sont pas autorisés à réorganiser les boîtes!
Tous les prisonniers sont tués la première fois qu'un prisonnier ne parvient pas à trouver son numéro. Et aucune communication n'est possible.
Astuce:on peut économiser plus de 30 prisonniers en moyenne, qui est beaucoup plus que (50/100) * (50/99) * [...] * 1

La solution

Ce puzzle est expliqué au http://www.math.princeton.edu/~wwong/blog/blog200608191813.shtml et que personne ne fait un bien meilleur travail d'expliquer le problème.

Le "tous les détenus ont été tués" énoncé est faux.L'", vous pouvez enregistrer 30+ en moyenne" est aussi faux, le l'article dit que 30% du temps, vous pouvez enregistrer 100% des prisonniers.

Autres conseils

J'ai trouver une low tech solution à ce type de problème est toujours la meilleure façon d'aller.

nous avons d'abord faire des hypothèses sur la situation

Les prisonniers ne sont pas tous des programmeurs ou des mathématiciens
Ils ne veulent pas mourir
Les gardes sont bien armés

Donc, avec un taux de 0,005% de chance qu'ils vont voir demain, il est très simple et low tech solution à ce problème. RIOT

son tout sur les pertes v potentiel de gain, les chances sont les prisonniers de beaucoup le nombre des gardes, et à l'aide les uns les autres comme boucliers humains, comme ils sont tous morts, des hommes de toute façon si ils ne le font pas, ils peuvent augmenter les chances qu'ils seront plus de puissance, une garde, une fois son arme, il y a de chance monte, en les aidant plus de puissance plus de gardes pour obtenir plus de puissance de feu pour augmenter encore là, le taux de survie.une fois les gardes rendre compte de ce qui se passe, ils vont probablement courir dans les collines, et de fermer la prison, ce sera de donner aux médias un heads-up et ensuite ses une question de droits humains.

Mettre en œuvre un algorithme de tri et de trier les cases selon les chiffres à l'intérieur d'eux.

Premier prisonnier sortes de 50 boîtes, et le second prisonnier trie les autres 50 et se confond avec la première.(Notez que le deuxième prisonnier peut deviner les valeurs à l'intérieur de la première 50 boîtes)

Après la 2ème prisonnier, toutes les cases seront dans un ordre trié !!!

Tout le monde peut ouvrir les boîtes contenant les numéros facilement.

Je ne sais pas si c'est autorisé mais la meilleure approximation que je peux trouver est:

EDIT:Ok, je pense que ce qu'il fait.Bien sûr, je suis de la traiter comme un problème informatique, je ne pense pas que tout prisioner sera en mesure d'effectuer ce, même si c'est assez simple si vous n'avez pas.

Trouver les 50 premiers nombres premiers, nous allons asume nous tenir dans un tableau appelé nombres premiers.

La première prissioner entre dans la salle B et ouvre la première case et trouve le nombre m.
Attendre nombres premiers[1]^m (ce qui serait le 3^m)
Ouvrir la boîte de 2 et de lire le nombre --> n
Attendre (les nombres premiers[2]^n - 1) * les nombres premiers[1]^m, qui serait (5^n - 1) * 3^m et le temps qu'il a attendu serait de 3^n * 5^n

Répétez.Après la première prisioner le temps total pour lui serait:3^m * 5^n * 7^p ...= X

Avant la seconde prisioner entre dans la salle de factoriser X.Vous savez à l'avance les nombres premiers qui ont été utilisées jusqu'à la factorisation est trivial.Faire de sorte que vous obtenir m, n, p, etc ... donc la deuxième prisioner connaît chaque case/nombre de combinaison de la précédente prisioner utilisé.

La probabilité de la première de rendre tout le monde tués est de 1/2, la seconde aura 50 / (100 - n) (soit n le nombre de tentatives de la première) le troisième aura 50 / (100 - n - m) (si n + m = 100 alors toutes les positions sont connues) et ainsi de suite.

Évidemment, la prochaine prissioner doit passer le déjà connu des boîtes (sauf pour le dernier choix si la boîte qui contient son numéro est déjà connu)

Je ne sais pas ce qui est l'exact possibilité qu'il dependes sur la façon dont de nombreux choix qu'ils ont à faire, mais je dirais qu'il est assez élevé.

EDIT:En relisant, si le prissioner ne pas avoir à arrêter quand il obtient son numéro, puis la probabilité pour l'ensemble du groupe s'est grandement amélioré, exactement 50%.

EDIT2:@OysterD la voir de cette façon.Si le premier prisioner pouvez ouvrir 50 boîtes puis, la seconde de savoir si son numéro est dans l'une quelconque des boîtes.Si c'est le cas, il peut ouvrir les 49 autres (et, par conséquent, l'apprentissage de la boîte/du numéro de la combinaison de l'boîtes de 100) et enfin, ouvrir son un.Ainsi, si la première prissioner insurpassable puis tout le monde réussisse.N'oubliez pas que chaque prisioner fournit un moyen pour les autres de savoir exactement les boîtes de/nombre de combinaison pour chaque boîte, il s'ouvre.

Peut-être que je ne suis pas la lecture de la droite, mais la question semble être mal construit ou informations manquantes.

Si il trouve le nombre qui a été qui lui est assignée à l'un de ces 50 des boîtes, le prisonnier arrive à marcher dans une chambre C et toutes les boîtes sont fermées de nouveau avant la prochaine, marche dans la salle B de la salle A.Sinon, tous les les prisonniers (dans les salles A, B et C) obtient tué.

La dernière phrase de là à dire que tous les prisonniers sont tués la première fois qu'un prisonnier ne parvient pas à trouver leur numéro?Si pas, ce qui se passe pour les prisonniers qui ne trouvent pas leur nombre?

Si aucune communication n'est possible, et chaque fois qu'un détenu entre dans la salle B, il est toujours à l'identique alors il n'y a pas de possibilité pour une stratégie.

Les prisonniers pouvaient peut dire, avant de quitter la salle Un qui, au nombre de box, ils vont ouvrir.Mais sans les prisonniers de savoir s'ils ont réussi ou non (en cas de panne de l'un n'est pas l'échec de toutes les) lors de la prochaine prisonnier entre dans la salle B, ils ont toujours la même probabilité de choisir leur numéro que le précédent prisonnier (toujours de 1:100).

Si la défaillance de l'un est l'échec pour tous, en sachant quelle case de la précédente prisonniers ouvert, et par la force des choses le fait qu'ils n'ont pas tous été tués, chaque détenu peut réduire les chances de choisir la mauvaise boîte, une boîte.c'est à dire1:100 pour le premier prisonnier, 1:99 pour la deuxième, en baisse de 1:1 pour le dernier.

Les prisonniers pouvaient convenir que le prisonnier 1 ouvrez les boîtes de 1-50.

Si ils sont tous encore en vie, ils conviennent que la prochaine prisonnier ouvre les boîtes de 2-51.(le 2 est arbitraire, mais simple pour se souvenir de cette règle) Ses chances de survie étant donné que P1 survécu sont maintenant 50/99.Vous voulez éliminer l'ouverture de la boîte lorsque vous savez que les gars précédente trouvé son.

Je ne sais pas si c'est optimal, mais c'est beaucoup mieux qu'au hasard.

La probabilité de survie qui ressemble à

50/100 * 50/99 * 50/98 *. . .50/51 * 1

Je pense que depuis, aucune communication n'est possible, la meilleure stratégie consisterait

la distribution de la probabilité de chacun des prisonniers de manière aussi uniforme que possible

Suis-je sur la bonne voie ou pas?

Les informations disponibles pour chaque détenu:

Le nombre de survivied prisonniers, donc si vous avez une boîte de cueillette système qui utilise l'ordre de tout prisonnier entre dans la salle B, alors une stratégie est certainement possible

Les cases qui le plus tôt prisonniers choisi.Bien sûr, aucune communication n'est possible au cours de la course et il ne serait pas possible de mémoriser toutes les 100s zone de cueillette de permutation. Mais vous pouvez utiliser cette information pour calculer dans un système avant la course commence.

De mon point de vue:

Dessiner un tableau de nombres avec 2 colonnes, la première colonne contient le numéro de la boîte (à partir de la case 1 à la case no 100).Chaque détenu reçoit alors de choisir 50 boîtes et quelle que soit la boîte de sélection, ils devraient mettre 1 marque sur la ligne correspondante dans la deuxième colonne.

Tous les prisonniers sont toutefois tenus de ne jamais choisir n'importe quelle boîte deux fois.Et pas de boîte peut être marqué plus de 50.Certains détenus peuvent recevoir moins d'options que les autres depuis une case peut se remplir de 50 marques de première.

Lorsqu'un prisonnier est déplacé à la salle B il/elle s'ouvre quelle que soit boîtes qu'il a marqué sur.

Si tous les prisonniers sont tués quand quelqu'un ne parvient pas à trouver leur numéro, puis vous enregistrer 100 ou 0.Il n'y a pas de moyen d'économiser de 30 personnes.

Même concept.

Aonther prendre:

Écrire une liste des 100 premiers nombres binaires qui a cinquante 1s et cinquante 0s.

Trier du plus bas au plus élevé.

Prisonnier n ° 1 obtient le premier numéro de prisonnier #2 obtient le deuxième, prisonnier #3 obtient la troisième et ainsi de suite...

Chaque prisonnier se souvient de son nombre binaire.

Quand tout prisonnier est déplacé à la salle B, il/elle a alors une correspondance entre les chiffres binaires de le nombre il s'en souvenait avec chacun de la boîte, le bit le plus élevé correspond à la case la plus à gauche, le côté le plus élevé de bits correspond à la deuxième case la plus à gauche ...le bit le plus bas correspond à la plus à droite de la boîte.

Il/elle les ouvre, quelle que soit boîtes appariés avec 1 et laisser fermer les boîtes appariés avec des 0.

Cela permettrait de réduire la probabilité parce que les premiers prisonniers obtenir des chiffres qui sont différentes de la plus tard, les prisonniers et les détenus, qui a le numéro de proximité, ensemble, obtenir des chiffres proches.Cela ne garantit pas la survie, mais si les premiers prisonniers ne survivre, les chances sont le plus tard, les prisonniers ont une plus grande probabilité de survivre ainsi.

Je n'ai pas pensé à sortir l'exactitude des chiffres et de logique, mais c'est une solution rapide, je peux penser en ce moment.

Il n'y a pas de limites de temps dans la question, alors je vous suggère de prisonniers décide de prendre 1 heure par boîte et ouvrez-les dans l'ordre présenté.Si le deuxième prisonnier est admis dans la salle après 2 heures, puis il sait que le premier prisonnier trouvé son propre numéro dans la case 2.Donc il sait de sauter la case 2 dans sa séquence et ouvre les boîtes de 1, 3, 4...51 Premiers prisonniers chances de perdre sont 50/100 Donner que le premier prisonnier survécu alors le deuxième prisonniers de chances de gagner sont 50/99 Donc, la réponse semble être ((50 ^51)*49!)/100!qui, selon google fait de 2,89*10^-9 qui est à peu près nul Donc, même si les prisonniers savaient les cases précédemment chanceux ont trouvé leur nombre à il n'y aurait pas d'espoir

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow