Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#1 30-05-2011 13:01:47
- mathieu64
- Membre
- Inscription : 06-11-2009
- Messages : 192
prisonniers
J'ai trouvé un problème sur le net, je sais pas si c'est classique mais la stratégie est assez sympa:
Un tyran retient prisonniers 2n mathématiciens. Il leur propose le « jeu »
suivant. Il dispose 2n boîtes numérotées dans une pièce, et place le nom de chaque
mathématicien dans une des boîtes. Il les fait entrer à tour de rôle et leur demande
d’ouvrir n boîtes. S’ils trouvent tous leur nom dans une des boîtes qu’ils ont ouvertes,
ils sont tous libérés. Si au moins un ne trouve pas son nom, ils sont tous exécutés. Ils ont
le droit de se concerter une fois avant de commencer, mais plus ensuite.
Montrer qu’il existe une stratégie leur laissant plus de 30% de chances de survie.
Si vous voulez la solution elle est à l'adresse:
http://boumbo.toonywood.org/sandrine/pa … ations.pdf
Bonne journée
Hors ligne
#2 30-05-2011 15:52:50
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : prisonniers
Bonjour,
Non rassure-toi, ce n'est ni classique, ni facile loin de là (il est même plutôt très difficile) ...
Barbichu, un p'tit djeûne (par rapport à moi) très prometteur (en fait, les promesses ont été tenues) nous avait fourni l'an dernier une "horreur" assez voisine, dont je ne donne que le texte et pas la page où la trouver, pour ne pas déflorer le sujet : il y a eu de nouveaux inscrits très portés sur la réflexion de haute volée ces derniers mois...
Je vais étudier de plus près ce que ça implique que ce soit des noms et non des numéros comme ci-dessous
Bonjour,
pour compenser mon hyperactivité au niveau des énigmes ces temps-ci, à mon tour de vous en poser.Dans un petit pays, un tyran décide d'emprisonner ses 100 mathématiciens dans une cellule, il leur attribue alors à chacun un numéro entre 1 et 100, tous différents.
Il leur propose alors un défi pour rester en vie. Dans une salle à l'autre bout de la prison, il dispose 100 coffres, dans lesquels sont contenus des numéros de 1 à 100, à raison d'un seul par coffre et tel que tout numéro se trouve dans un coffre.
Les mathématiciens passeront chacun leur tour dans la salle des coffres et ils auront 50 essais chacun pour trouver leur numéro. Lorsqu'un mathématicien trouve son numéro, il va dans une nouvelle cellule en attendant que les autres passent, sans aucun moyen de communication avec eux, mais s'il ne le trouve pas, alors tous les mathématiciens seront exécutés.
(NB : ils n'ont pas le droit de laisser les coffres ouverts, ni de déplacer les numéros, ni de mettre des annotations, où que ce soit)
Ils ont la nuit pour trouver une stratégie qui leur donnera le plus de chances de survie.* En supposant que la distribution des numéros dans les coffres soit tirée de manière équiprobable, trouver une stratégie qui donne au mathématiciens plus de 30% de chances de survie.
* Si on ne suppose plus cette distribution uniforme, que faire ?
Bonne chance
++
@+
[EDIT]Il me semble que l'énoncé ci-dessus est plus précis, puisque la question est double : en cas de répartition équiprobable ou non...
Quant au numéro plutôt que le nom, je n'arrive pas à me décider : nom ou numéro ça ne devrait pas changer grand chose, si on décide que le mathématicien Tartempion portera le nom x, avec 1 <=x<=2n...
Dernière modification par yoshi (30-05-2011 15:57:22)
Hors ligne
#5 30-05-2011 20:46:13
- jpp
- Membre
- Inscription : 31-12-2010
- Messages : 1 170
Re : prisonniers
Bonsoir
Personnellement, si j'en ai le droit , j'opterais pour la stratégie suivante:
je n'ai pas vu qu'il était interdit de déplacer les coffres. sinon ma stratégie tombe à l'eau.
s'ils ont un minimum de temps de réflexion ils copient tous la meme liste : dupont ->n°1,durant->n°2
martin->n°3....duval->n°2n
ainsi , dupont , le n°1 rentre dans la salle des coffres et ouvre n coffres qu'il aligne dans le meme
ordre que les noms figurants sur leur liste et en laissant les places des noms manquants
il a donc 50/100 de chance. avant de quitter la pièce,
il place les n derniers coffres à la suite des n premiers examinés.
ensuite le second , au pire ouvre les n-1 derniers qu'il va intercaler correctement dans les n premiers
puisque sur la liste , à chaque nom , on a affecté un numéro.
mais s'il a ouvert le coffre "Durant -> n°2" , Durant le saura
quand vient le tour de Durant, il va bien entendu ouvrir son coffre puis (n-1)coffres
parmi les n derniers lorsque le premier est passé il laisse au second la configuration suivante:
dupont. durant. ---- titi ---- ---- toto. tata ---- ect.... n(tyty)(n+1).(n+2)....2n
si bien que si le premier a tiré les 2 premiers noms , le second saura retrouver son nom.
il bouchera les trous dans les rangs et pourra meme placer le dernier sans l'ouvrir. et tous les autres
sauront retrouver leur coffre.
finalement plus n est grand plus leur chance se rapproche de 50/100 par valeur inférieure
Dernière modification par jpp (30-05-2011 20:54:12)
Hors ligne
#8 30-05-2011 22:34:15
- mathieu64
- Membre
- Inscription : 06-11-2009
- Messages : 192
Re : prisonniers
En effet ça change complétement la proba de 30%. Mais pour n peu élevé je vais regarder mais j'imagine que ça l'affecte pas beaucoup. En tout cas on peut dire que les prisonniers n'ont pas le droit de changer l'ordre des boites
Dernière modification par mathieu64 (30-05-2011 22:40:53)
Hors ligne
#9 31-05-2011 09:52:41
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : prisonniers
Re,
L'ami Barbichu avait écrit en son temps, en réponse à des supputations diverses :
Je précise un point qui semble vous chagriner : on considère que les coffres ne seront pas mélangés d'une visite à l'autre.
C'est déjà assez "aléatoire" comme ça, si en plus, l'ordre des coffres changeait d'une visite à l'autre par le fait des gardiens...
Par contre, si les prisonniers pouvaient changer l'ordre des boîtes, ça changerait beaucoup de choses.
Donc non, les boîtes restent là où elles sont, personne n'y touche, sauf les prisonniers pour les ouvrir et les refermer.
@+
Hors ligne