Sauver les mathématiciens

Posté par terom21 terom21

bonjour à tous cet question a été poser au en cours sur les chaine de markov :
*on a 100 mathématiciens kidnapés par un dicateur .
* le dicateur enferme les 100 mathématiciens dans une piéce A,  et met 100 tiroirs (dans une piéce B) qui contiennent chacun  un nom d'un mathématicien ( biensur les noms des mathematiciens kidnapés ).chaque mahématiciens a le droit d'ouvrir 50 tiroirs , si il trouve son nom, le mathematicien est placé dans une piece C , et le tiroir est fermé avec le nom dedans (tirage avec remise !!); Si tout les mathématiciens arrivent à trouver leur nom , ils seront relaché . Si l'un des mathématiciens ne trouve pas sont nom , ils seront tous tuer

la probabilité de survie des mathématiciens est = 1-log(2) (mais ça ne sert pas a grand chose , je pense ).
Alors sauvons les mathématiciens ..

Posté par Camélia Camélia

Bonjour

D'abord, quelle est la question?

Ensuite, quelques précisions... Si le matheux ne pas son nom, que devient-il? Les suivants savent-ils ce qui s'est passé? Se connaissent-ils par leur nom?

Posté par terom21 terom21

bonjour Camélia
*la question est comment sauver tout les mathématiciens ?? en gros trouver une stratégie pour sauver tout les mathématiciens !!
* on a 100 tiroirs et 100 mathématiciens , mais chaque mathématiciens n'a le droit de chercher son nom que parmi 50 tiroirs qu'il va choisir lui méme , si un mathématiciens ne trouve pas ils seront tous tuer , il n'y a aucun moyen de communication entre les mathématiciens .

Posté par terom21 terom21

j'ai oublier de dire aussi
1: les mathematiciens peuvent ouvrir les tiroirs un a un (ie: ils n'ouvrent pas simultanement les  50 tiroirs), et donc peuvent utiliser le nom ecrit dans un des tiroirs pour choisir le suivant
2: les noms sont places au hasard dans les tiroirs, uniformement sur toutes les permutations possibles

Posté par terom21 terom21

autre précision : les mathématiciens savent juste si le précédent à trouver ou non son nom.

Posté par terom21 terom21

j'ai encore oublier : les mathématiciens se connaissent par leur nom

Posté par Drysss Drysss

Tout les mathématiciens ouvrent le 1 jusqu'à ce que qqn trouve ensuite tout le monde ouvre le 2 ect...
Et ainsi jusqu'au 100.
Le pire scénario comme nombre de tirage totale est : 100+99+98+97+....+1 <
100*101/2. Or c'est à peu près le même que le nombre de tirages que peuvent effectuer les mathématiciens. (à une 50aine près).

Posté par bc92 bc92

Bonjour,
Je connais cette énigme, pas très facile et bien intéressante.
J'en redonne ci-dessous un énoncé complet et précis tel que je le connais (un peu long) :

Dans un cachot sont entassés 100 détenus
qui se connaissent tous par leur prénom (pas d'homonymes).

Un geolier inflexible va venir les chercher un par un, à sa guise.

Il prendra donc un détenu pour l'emmener dans une salle où sont alignés
100 boites numérotées de 1 à 100.

Chaque boite contient un et un seul nom de détenu écrit à
l'intérieur.

Le détenu peut aller regarder dans au plus 50 boites.
Le gardien note s'il arrive a  trouver la boite contenant son propre nom,
apres quoi il le conduit dans une autre cellule, en isolement,
remet la salle  pile poil dans l'état initial et va chercher un autre détenu quand ça lui chante...

Ainsi de suite jusqu'a ce que les 100 détenus soient passés.

ils seront TOUS exécutés, sauf s'ils ont TOUS trouvé leur nom... Un seul échec les condamne tous.

Alors qu'ils se lamentent tous sur sur leurs chances de survie un détenu se lève d'un bond et dit: Hep les gars, j'ai une idee, nous avons au moins 30% de chance de vivre !
Quelle est cette idée?

NOTE : les prisonniers peuvent se concerter tant qu'ils veulent avant le début, mais une fois le premier prisonnier au travail, il n'y a aucune communication de quelque sorte ou par quelque moyen que ce soit, entre ceux qui sont déjà passés et ceux qui restent, ni par l'intermédiaire du gardien. Les prisonniers ne savent absolument pas ce qu'ont fait les précédents.

Bruno

Posté par bc92 bc92

Post scriptum

"Les prisonniers ne savent absolument pas ce qu'ont fait les précédents"

Comprendre "à part que les précédents sont censés avoir suivi la stratégie décidée d'avance, même si le fait qu'ils l'aient fait ou pas ne change rien à la conduite à tenir par ceux dont le tour arrive."

B.

Posté par terom21 terom21

bc92 est ce que tu une idée sur la stratégie à adopter ?

Posté par carpediem carpediem

salut

je ne comprends pas trop:
si le 1e mathématicien ouvre 50 boites sans trouver son nom alors c'est perdu....

Posté par bc92 bc92

Voici la solution telle que je l'avais notée :


SOLUTION:

Il n'y a aucune communication possible sur les résultats, aussi le succès est-il purement affaire de stratégie convenue au préalable.

Les détenus se concertent et s'attribuent à chacun un numéro n de 1 à 100
(le plus difficile sera d'apprendre par coeur les 100 associations. l'ordre alphabétique est suggéré, mais la permutation choisie n'a aucune importance).

Dès lors : chaque casier i est associé au numéro c(i) équivalent au nom qu'il contient. Cette substitution i - c(i) a été définie par le gardien ou ses chefs, et transformée par la permutation nom-numéro choisie par les détenus.
par exemple le prisonnier que le collège a numéroté 67 a pour nom Toto et son casier est le N° 78. c(67)=78.

Stratégie: le détenu k commence par le casier k, il y trouve un nom correspondant à c(k) et va au casier numéroté c(k), etc.
Il trouve ainsi successivement les noms correspondant à
c(k), c^2(k),.....,c^50(k)

Il suffit donc que, dans la substitution (1...100)-->(c(1)...c(100)), la permutation la plus longue concerne au plus 50 numéros, pour que k figure dans la chaine c(k), c^2(k),.....,c^50(k), et que le prisonnier k gagne son coup. Et il en ira nécessairement de même pour tous les prisonniers.

Attention l'énoncé ci-dessus n'est pas tout à fait intuitif, on s'en convaincra mieux en regardant ce qui se passe avec 4 prisonniers et deux tirages chacun. En particulier, dans un cycle de longueur 50 exactement, le nom lu dans le 50e casier est c^50(k) = k soit le nom du prisonnier. En fait c'est le 51e de la chaine commençant par k.

Le succès est assuré si le remplissage des casiers respecte cette condition. Par contre, l'échec est assuré avec cette stratégie si le remplissage des casiers comporte un cycle supérieur à 50.

Le reste est affaire de dénombrement. Généralisons en considérant 2n prisonniers pouvant ouvrir chacun n casiers.

Il y a au plus une  permutation de k éléments, k > n, dans une substitution de 2n éléments.
Pour obtenir une telle permutation, il faut tirer k éléments parmi 2n, soit C(2n,k) possibilités. C(2n,k) = (2n)!/k!/(2n-k)!
Une fois les k éléments choisis, le nombre de permutations entre eux est égal à (k-1)! [le montrer].
Enfin, les possibilités de ranger les (2n-k) éléments restants sont de (2n-k)!

Le nombre de substitutions défavorables est donc:
Somme(k=n+1 à 2n) ((k-1)! (2n-k)! C(2n,k)) = Somme((2n)! / k)
Alors que le nombre total de substitutions de 2n éléments est (2n)!

substitutions défavorables signifie qu'elles n'assurent pas le succès à coup sûr, et même qu'elles assurent l'insuccès à coup sûr puisqu'avec la stratégie choisie chaque prisonnier découvre son nom au bout du cycle.

Donc la probabilité de succès p vérifie :
p = 1- Somme (k=n+1,2n, (1/k))

En notant H(n) la somme partielle de la série harmonique,
p = 1 - (H(2n) - H(n)) = p(n)
Comme H(2n) - H(n) est décroissante, p(n) est décroissante et
p > lim [1 - H(2n) - H(n)] = 1 - Ln(2)
La convergence de H(2n) - H(n) vers Ln (2) est classique, car
H(n) = Ln(n) + gamma + o(1) avec gamma la cte d'Euler.

Et effectivement, 1 - Ln(2) = 0,307 supérieur à 30%.

================

Voilà. Bruno

Posté par jocelyn jocelyn

Je déterre un peu le post parce que j'ai quelques soucis à comprendre !



Je ne vois pas la signification de la dernière phrase, pourquoi les ranger ?

Et enfin je ne comprend pas pourquoi le prisonnier k retrouve son numéro si et seulement si p est dans un cycle de longueur inférieure à 50. Il pourrait très bien tomber dessus dans un cycle de longueur supérieure à 50 non ?

Merci d'avance !

Posté par jocelyn jocelyn

S'il vous plait !

Posté par jocelyn jocelyn

Ya quelqu'un ?