Sauver des nains probabilistes

[newton]

Bonjour,
J'ai un problème très théorique qui m'a été posé sous cette forme :
Soit 100 nains étant attribué à un nombre n de 1 à 100 inclus (chaque nain à un nombre différent.
Pour chacun des nains on a une salle contenant 100 coffres chacun numéroté par nombre x de 1 à 100. Et chaque coffre contient un nombre y. Un nain a le droit d’ouvrir 50 coffres. Si il ouvre un coffre pour lequel y=n il est sauvé sinon on le considérera mort.
Chaque expérience (donc chaque salle) est indépendante.
Combien de nain peut-on espérer sauver ?

PS : On m’a dit que ça ne marche que parce qu’il y a exactement 100 nains (et pas 98,99,101 ou 102) et que la proportion sauvé vaut plus de 50% (au alentour de 60 ou plus, je ne sais pas exactement).
Merci (d’avoir lu tout ça).

[Michel]

Voir l'énigme d'Oswald : viewtopic.php?f=8&t=13214

[Khainyan]

c'est pas la même chose michel... ici ils ne vont pas dans la même salle. Alors à moins que chaque salle ai la même config le problème est différent. De plus ici c'est le nombre de nain statiquement sauvé... pas la probabilité de tous les sauver.

[Michel]

si tu le dis...

[newton]

Khainyan a tout a fait raison chaque salle peut avoir des config différentes. D'après ce que j'ai compris les nains doivent ouvrir le coffre qu porte le numéro contenu dans le coffre précédent. Le premier coffre est probablement pris au hasard. En ce qui me concerne cette stratégie ne m'explique pas comment ça marche car je trouve toujours 50%.

[Khainyan]

en fait dans la précédente énigme il y a une seule salle pour les 100 scientifiques.. ils entre chacun à leur tour. ils "affronte" donc tous exactement la même salle.
La stratégie mise en place consiste à apprendre le nom et le numéro de chacun, à commencer par ouvrir la boite correspondant à son nom/numéro en premier, regarder le nom/numéro qu'elle indique, aller ouvrir la boîte correspondante, ect... C'est très important de ne pas ouvrir la première au hasard. je vais expliquer pourquoi.
Si on met cette stratégie en place, la probabilité de tomber sur son nom est égale à celle qu'il n'y ai pas de cycle de taille supérieur à 50 parmi l'agencement des boîtes. En effet si il y en a pas en commençant par ouvrir la boîte à son nom on trouvera forcément son nom dans une des boites dans le cycle dont la première fait partie (puisque un cycle par définition "reviens sur lui-même"). A contrario si il y a un cycle supérieur à 50 c'est foutu... puisque au moins un des scientifique (cas d'un cycle à 51) ne trouvera pas son nom en ouvrant 50 boîtes (il ouvrira la première... puis les 49 suivantes alors que son nom se trouve dans la 51°). Ainsi la probabilité qu'ils survivent est égale à celle qu'il n'y ai pas de cycle supérieur à 50. Et ça c'est environ égale à 30% et tant vers 1-ln(2) quand n tend vers l'infini.
ah oui le coup de la première boite: si il ouvre la première au pif il risque de tomber sur un cycle qui n'inclue pas son nom. D'où c'est foutu.

Dans ton cas euh... si ils appliquent cette méthode... bin 30% de chance pour que dans chaque salle il n'y ai pas de cycle supérieur à 50. Donc ouvrir au pif est même plus intéressant (50% de chance de trouver son nom). mais pour sauver 50% des nains je vois pas... faudrait que j'y réfléchisse un peu

[franckpiton]

Bonjour,
J'ai un problème très théorique qui m'a été posé sous cette forme :
Soit 100 nains étant attribué à un nombre n de 1 à 100 inclus (chaque nain à un nombre différent.
Pour chacun des nains on a une salle contenant 100 coffres chacun numéroté par nombre x de 1 à 100. Et chaque coffre contient un nombre y. Un nain a le droit d’ouvrir 50 coffres. Si il ouvre un coffre pour lequel y=n il est sauvé sinon on le considérera mort.
Chaque expérience (donc chaque salle) est indépendante.
Combien de nain peut-on espérer sauver ?

Excuser moi messieurs, l'énoncé, c'est juste cela ou c'est un problème connu des matheux (que je ne suis pas) et ici juste résumé?

Car vu comme cela, chaque nain à le même souci que ses camarades et sa résolution ou pas n'influence aucunement les chances de survit des autres. Chaque nain peut ouvrir un coffre sur deux (50/100) et donc une chance sur deux d'y rester. Chaque nain à le même souci qui est indépendant du résultat des autres, donc à la question "Combien de nain peut-on espérer sauver", la réponse est 50 ou 1/2 en moyenne.

Je me doute bien que j'arrive ici comme un chien dans un jeu de quille, mais c'est quoi que je ne comprend pas ?

Ps: Si ces nains sont aussi bossus et qu'ils se la touchent mutuellement alors peut être que...

[franckpiton]

Je viens de réalisé qu'il n'est pas précisé de fourchette pour "y", je pensais qu'il était comprit entre 1 et 100.

Si "y" n'a pas de fourchette, le problème est insoluble, donc pas de problème.

Encore une fois, c'est où que je me plante?

[newton]

Excuser ma distraction sans limite y est effectivement compris entre 1 et 100. Pour moi ça paraissait évident. Mais je suis quasi sur qu'on peut en sauver plus de 50% mais je ne sais pas comment.

[franckpiton]

Si l'énoncé est corect et que "y" est comprit entre 1 et 100, alors c'est 50 nains en moyenne.

L'énoncé est surement incomplet.

Où alors ils ont un anneau magique.

[Khainyan]

Si effectivement les salles sont strictement indépendantes tu ne risque pas de dépasser le 50%.
Donc on peut sauver jusqu'à 100% des nains mais en moyenne c'est 50%.





Mais qu'est ce que je hais les stats et les probas.

[newton]

Je vais vous expliquer la stratégie qui permettrai de dépasser les 50% (mais j'en doute affreusement).
Le nain ouvre un coffre au hasard puis ouvre le coffre dont le numéro est le y du coffre précédent. C'est compréhensible ?
Cette stratégie me parait inutile car le premier coffre est pris au hasard. On m'a dit d'essayer toutes les possibilités sauf que j'ai aucune envie d'essayer 100! possibilités. J'ai donc ramener le tout à des nombres entre 1 et 4 mais rien de concluant ne s'est montré.

[Khainyan]

Dans ce cas il ne faut pas prendre au hasard le premier coffre.
L'intérêt de cette stratégie c'est que la probabilité de trouver son nom est celle qu'il n'y a pas de p-cycyles de tailles supérieure à 50 dans la permutation des boîtes. Sauf que ça n'a un intérêt que si tu commence par ouvrir la boîte qui te correspond, comme cela tu es sûr de tomber sur un cycle qui contient ton nom. Sinon bin t'as 1 chance sur n de tomber sur le bon cycle où n est le nombre de cycle.
En suivant cette stratégie tu as donc environ 30% de chance de trouver ton nom à coup sûr, mais surtout de trouver tous les noms, à conditions que tout le monde passe par la même salle. Donc 30% de chance de tous les sauver, ce qui est mieux que de piocher au pif car (1/2)^100=7,9 x 10^-31. En revanche si toutes les pièces sont indépendantes ça n'a aucun intérêt cette stratégie car cela reviens à faire du 0,3^100 de chance de tous les sauver, où du 30% de sauvés en moyenne...