Devinette, 100 Prisonniers

[invité576543]

Yat, j'ai regardé ton programme, je me demande s'il n'y a pas un problème avec rand()%100. Ce serait une variable uniforme uniquement si rand() prenait ses valeurs dans un intervalle de taille multiple de 100. Or ça a toutes les chances d'être une taille multiple de 2. Ca introduit un biais qui peut être suffisant pour expliquer la différence, non?

L'laternative est quelque chose comme

repéter n <- rand() jusqu'à n<100*k
choix <- n%100

avec k choisi selon l'intervalle effectif de rand()

Cordialement,
-----

[invité576543]

correctif mineur...

d'être une taille multiple de 2

d'être une taille puissance de 2

[yat]

Yat, j'ai regardé ton programme, je me demande s'il n'y a pas un problème avec rand()%100. Ce serait une variable uniforme uniquement si rand() prenait ses valeurs dans un intervalle de taille multiple de 100. Or ça a toutes les chances d'être une taille multiple de 2. Ca introduit un biais qui peut être suffisant pour expliquer la différence, non?

Bien vu !

Dans la fonction rand(), le maximum est de 32767, ce qui n'est pas très grand devant 100 (j'ai l'habitude d'utiliser une fonction aléatoire qui renvoie des résultats sur 32 bits)... du coup les prisonniers entre 0 et 67 ont une chance sur 327 de plus que les autres de tomber. Ca suffit à tout foutre en l'air.

Je viens donc de relancer les jeux de tests avec la correction que tu proposes...


...les résultats des trois premiers jeux sont 10416,97, 10417,55 et 10417,72

Je savais qu'il fallait que j'envoie mon code pour que quelqu'un trouve la banane Merci pour cette correction, mmy.

[Médiat]

En nettoyant mon code avant de le publier, j'ai trouvé une ch'tite connerie, qui une fois rectifiée m'a donné un résultat très stable autour de 10408, et une fois corrigée la connerie détectée par mmy (oui, oui, j'avais la même ), j'obtiens :
10418.45
10418.33
10418.73
10418.69
10418.28

L'écart de 1 avec yat viens sans doute de ce que je compte le premier passage du compteur, et j'ai l'impression que yat ne le compte pas.

[yat]

L'écart de 1 avec yat viens sans doute de ce que je compte le premier passage du compteur, et j'ai l'impression que yat ne le compte pas.

Euh... si, si. Qu'est-ce que tu veux dire ?

[Médiat]

Euh... si, si. Qu'est-ce que tu veux dire ?

Tu as raison (nbs=1).
Je vais vérifier mon code ce soir, c'est moi qui ait dû me planter (d'autant plus que 10417 est conforme au résultat théorique que j'avais calculé )

[Médiat]

Je ne vois rien de bien différent d'avec ton code (sauf les habitudes de programmation ) A tout hasard, voila mon code.

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <time.h>


void Jeu(void)
{
   unsigned long nTotal = 0;
   unsigned long nCpt;
   int           nTirage;
   int           nPrisonnier;
   int           nEtat[100];
   int           bNext;

   for (nCpt = 0; nCpt < 400000; nCpt++)
   {
	  for(nPrisonnier = 0; nPrisonnier < 100; nPrisonnier++)
		  nEtat[nPrisonnier] = 0;
	  bNext = 1;
	  nTotal++;

	  for(nPrisonnier = 1; nPrisonnier < 100; )
	  {
		  
		  for(;;)
		  {
			  nTirage = rand(); 
			  if (nTirage < 32700)
				  break;
		  }
		  nTirage %= 100;
		  nTotal++;

		  if (nTirage == 0 && bNext == 0)
		  {
			  nPrisonnier++;
			  bNext = 1;
		  }
		  if (nTirage != 0 && bNext == 1 && nEtat[nTirage] == 0)
		  {
			  bNext = 0;
			  nEtat[nTirage] = 1;
		  }
	  }
	  if (nCpt % 10000 == 0)
		  printf("%8d - ", nCpt);

   }
   printf("\n%lf\n", (double)nTotal / 400000.0);
}

void main(void)
{
 int i;
 for(i = 0; i< 10; i++)
 {
	srand( (unsigned)time( NULL ) );
	Jeu();
 }
 getch();
}

[yat]

Hé hé... tu as fait l'erreur inverse de celle que j'avais fait dans ma première version (et que tu as soulignée hier, avant de voir mon nbs=1).
En effet, moi je n'incrémente le nombre de passages qu'après ledit passage, et seulement si l'expérience n'était pas terminée. C'est pour ça que je dois initialiser nbs à 1.
Dans ton cas, le nombre de passage est incrémenté dès le tirage. Donc lorsque l'on s'intéresse au premier prisonnier, son passage est déjà décompté. On est le premier jour, mais comme tu as initialisé ton compteur à 1 avant la boucle, celui-ci est déjà à 2. Il faut donc enlever le nTotal++ qui se trouve avant la boucle

[Médiat]

Dans ton cas, le nombre de passage est incrémenté dès le tirage. Donc lorsque l'on s'intéresse au premier prisonnier, son passage est déjà décompté. On est le premier jour, mais comme tu as initialisé ton compteur à 1 avant la boucle, celui-ci est déjà à 2. Il faut donc enlever le nTotal++ qui se trouve avant la boucle

Oui mais le compteur de prisonniers commence à 1 aussi puisque je considère que le premier jour a permis de compter le compteur.
Je me demande si la différence ne viens pas d'un truc tout bête d'intervalles : si les prisonniers sont appelés à l'aube de chaque jour, et que l'on commence à compter lors de l'appel du premier, le deuxième prisonnier (en admettant que ce ne soit pas le même qui est appelé) est appelé le jour 2, mais il ne s'est écoulé qu'un jour entre les deux ; j'ai pris la première option, peut-être as-tu pris la deuxième ?

[yat]

Oui mais le compteur de prisonniers commence à 1 aussi puisque je considère que le premier jour a permis de compter le compteur.

Je ne vois pas le rapport... le fait est que la première fois que tu entres dans ta boucle, tu choisis au hasard un prisonnier, et paf, on est déjà au jour 2, ce qui est gênant dans la mesure ou il s'agit du premier jour. S'il était possible que le jeu se termine dès le premier jour, ton programme renverrait 2 dans ce cas. Comme tu incrémentes avant de tester quoi que ce soit, il faut que tu initialises le nombre d'étapes à zéro au lieu de 1 au départ. Donc, j'insiste, l'erreur est le premier nTotal++

Je me demande si la différence ne viens pas d'un truc tout bête d'intervalles : si les prisonniers sont appelés à l'aube de chaque jour, et que l'on commence à compter lors de l'appel du premier, le deuxième prisonnier (en admettant que ce ne soit pas le même qui est appelé) est appelé le jour 2, mais il ne s'est écoulé qu'un jour entre les deux ; j'ai pris la première option, peut-être as-tu pris la deuxième ?

Le premier prisonnier qui entre dans le salon y entre au jour 1, le deuxième au jour 2, etc. Le but est de trouver au bout de combien de jours les prisonniers pourront sortir, c'est à dire le numéro du jour ou le compteur va entrer dans le salon et être en mesure de dire que tous les prisonniers sont déjà passés.

[invité576543]

Bonjour,

Je me demande s'il n'y a pas une approche au problème permettant d'aller plus vite, mais avec le bémol qu'il reste une probabilité infime d'erreur. L'idée est de jouer avec la loi des grands nombres...

Prenons n compteurs, n un paramètre à régler. Les non-compteurs se comportent comme usuel, il n'éteignent qu'une seule fois en tout en pour tout. Chaque compteur compte le nombre de fois qu'il éteint, ainsi que le nombre de fois qu'il est appelé (ou, variante, le nombre de fois consécutives qu'il a été appelé et trouvé la lumière allumée; ou les deux...).

Au bout d'un certain temps, au bout de k passages d'un compteur (ou k éteints consécutifs), k un paramètre à régler, et suffisamment grand pour que la probabilité que les 100-n non compteurs n'aient pas été comptés soit extrêmement faible, on passe dans le mode décompte des compteurs par un compteur-chef, qui n'a besoin alors que de compter jusqu'à n-1.

Je n'arrive à conclure sur des calculs formels, et la question est de savoir s'il y a une ou des valeurs de n et k tels que la proba d'échec soit, par exemple, de 10^-10 (ou autre valeur à discuter) et donnant un temps plus court que n=1.

Pour les matheux c'est peut-être inacceptable, mais on joue couramment sa vie sur des risques très faibles, en particulier en conduite routière. Il y a nécessairement une valeur de la proba d'échec en dessous de laquelle il n'y a pas grand sens pratique de la distinguer de 0...

Cordialement,

[Médiat]

Je ne vois pas le rapport... le fait est que la première fois que tu entres dans ta boucle, tu choisis au hasard un prisonnier, et paf, on est déjà au jour 2, ce qui est gênant dans la mesure ou il s'agit du premier jour.

J'ai ré-exécuté mon programme avec 2 prisonniers et je trouve une moyenne de 5 jours ce qui correspond bien à la réalité :
Jour 1 le compteur
En moyenne 2 jours pour l'autre
En moyenne 2 jours pour le compteur
Cela fait bien 5 jours...

Et 11,5 jours pour 3 prisonniers ce qui est juste à nouveau.

[invite35452583]

Oui mais si on introduit des solutions probabilistes et au vu des conditions de détention (impossibilité de savoir quel jour on est, isolement complet...), si je fais partie des 100 prisonnier, j'interviens "pas question d'une solution sûre qui dure 27 ans, proba d'être complètement décérébré=100%, le 1er qui compte 20 passages on sort ou on est fusillé" à vu de nez 3-4 ans (et ce serait déjà très long) devrait suffir pour une proba qui doit pas être loin de 99% (à vue de nez aussi).

[yat]

J'ai ré-exécuté mon programme avec 2 prisonniers et je trouve une moyenne de 5 jours ce qui correspond bien à la réalité :
Jour 1 le compteur
En moyenne 2 jours pour l'autre
En moyenne 2 jours pour le compteur
Cela fait bien 5 jours...

Et 11,5 jours pour 3 prisonniers ce qui est juste à nouveau.

Alors essaye avec un seul prisonnier : il entre dans le salon, dit que tout le monde est passé, et sort... mais ton programme te répondra 2 jours.

En plus, je ne comprends pas du tout ta description... d'ou sort ton "1 jour pour le compteur" ? Ca fait la troisième fois que tu y fais référence, je n'ai toujours pas compris ce que tu voulais dire. Avec l'énoncé, on a
2 jours pour le deuxième prisonnier
2 jours pour le compteur...
donc 4 jours.

[yat]

Oui mais si on introduit des solutions probabilistes et au vu des conditions de détention (impossibilité de savoir quel jour on est, isolement complet...), si je fais partie des 100 prisonnier, j'interviens "pas question d'une solution sûre qui dure 27 ans, proba d'être complètement décérébré=100%, le 1er qui compte 20 passages on sort ou on est fusillé" à vu de nez 3-4 ans (et ce serait déjà très long) devrait suffir pour une proba qui doit pas être loin de 99% (à vue de nez aussi).

J'ai fait ce egnre de tests ce matin... en comptant 20 passages, et sauf erreur de ma part, la durée moyenne est d'environ 1130 jours, avec environ 0,03% d'erreur. A 50 passages, je n'ai plus aucune erreur sur mes 4 millions de tests, et la durée passe à 3490 jours environ. On est proche de la probabilité de 10^-10, et la durée n'a pas grand chose de comparable avec les 29 ans de la méthode certaine.

[invite35452583]

J'ai fait ce egnre de tests ce matin... en comptant 20 passages, et sauf erreur de ma part, la durée moyenne est d'environ 1130 jours, avec environ 0,03% d'erreur. A 50 passages, je n'ai plus aucune erreur sur mes 4 millions de tests, et la durée passe à 3490 jours environ. On est proche de la probabilité de 10^-10, et la durée n'a pas grand chose de comparable avec les 29 ans de la méthode certaine.

99,97% de chance de s'en sortir avec une espérance de 3 ans 1 mois, je prends !

[Médiat]

En plus, je ne comprends pas du tout ta description... d'ou sort ton "1 jour pour le compteur" ? Ca fait la troisième fois que tu y fais référence, je n'ai toujours pas compris ce que tu voulais dire. Avec l'énoncé, on a
2 jours pour le deuxième prisonnier
2 jours pour le compteur...
donc 4 jours.

Ok, tu pars sur l'idée que l'état initial de la lampe est connu, et que je compteur est déclaré a priori. Je suis parti sur l'idée que l'état de la lampe n'était pas connu, et que le compteur était le prisonnier appelé le premier jour. Qu'il y ait un jour d'écart sur ces deux cas (mais ce n'est pas au choix) ne me surprend pas puisque cela reviens à dire que le compteur met la lampe dans un état connu, nous sommes donc d'accord.

[Médiat]

99,97% de chance de s'en sortir avec une espérance de 3 ans 1 mois, je prends !

Le problème avec les méthodes probabilistes c'est qu'elles reposent sur la "croyance" que le gardien va tirer les prisonniers au hasard, alors qu'il n'y a aucune garantie, et pire on n'a aucune idée de la probabilité que le gardien tire au hasard ; la probabilité finale est en fait 99,97% * P(aléatoire), le dernier facteur étant inconnu.
Dans la solution sure, cette probabilité inconnue n'intervient que dans le calcul de l'espérance, pas dans la certitude de réussite.

[yat]

Ok, tu pars sur l'idée que l'état initial de la lampe est connu, et que je compteur est déclaré a priori. Je suis parti sur l'idée que l'état de la lampe n'était pas connu, et que le compteur était le prisonnier appelé le premier jour. Qu'il y ait un jour d'écart sur ces deux cas (mais ce n'est pas au choix) ne me surprend pas puisque cela reviens à dire que le compteur met la lampe dans un état connu, nous sommes donc d'accord.

Ok, je comprends mieux la différence dans les résultats. Tu es quand même bien cavalier vis-à-vis de l'énoncé

[yat]

Le problème avec les méthodes probabilistes c'est qu'elles reposent sur la "croyance" que le gardien va tirer les prisonniers au hasard, alors qu'il n'y a aucune garantie

Quelle meilleure garantie que le fait que ça soit dit dans l'énoncé ?

[Médiat]

Ok, je comprends mieux la différence dans les résultats. Tu es quand même bien cavalier vis-à-vis de l'énoncé

J'ai pris ce fil en cours de route, et comme ce point n'est pas précisé dans le post initial, j'ai même lu un post ou l'hypothèse que l'on ne connaissait pas forcément l'état initial de la lampe était possible, et j'étais parti sur cette hypothèse qui est la plus contraignante (d'ailleurs elle coute un jour).

Quelle meilleure garantie que le fait que ça soit dit dans l'énoncé ?

Pour la même raison, il a même été évoqué un gardien vicieux qui n'appellerait jamais un prisonnier particulier.

Ceci-dit je pourrais te retourner le compliment (en toute cordalité et juste pour rire ) :

La solution consiste a trouver une methode qui soit 100 pourcent sure

[yat]

J'ai pris ce fil en cours de route, et comme ce point n'est pas précisé dans le post initial (...)

Oui, oui, l'énoncé initial était très incomplet, mais siris l'a complété quelques posts plus loin.

Ceci-dit je pourrais te retourner le compliment

C'est pas moi, c'est mmy !

(en toute cordalité et juste pour rire ) :

Ne tinquiète pas, ça va sans dire