Probabilités - Permutations et cycles stratégie

Posté par inp inp

Bonjour,

J'ai l'exercice suivant à résoudre mais je bloque complétement sur les questions notamment en ce qui concerne les permutations. Pouvez me corriger ce que j'ai pu faire et me débloquer pour le reste ?

Le problème est le suivant: il y a 100 joueurs numérotés de 1 à 100 et 100 boites également numérotées. Tous les nombres de 1 à 100 ont été répartis aléatoirement dans les boites (un nombre par boite). Chacun à leur tour, les joueurs auront le droit d'ouvrir 50 boites. Ils n'auront ensuite aucun moyen de communiquer avec les autres joueurs. Le but est que chaque joueur retrouve son propre numéro dans l'une des boites qu'il a ouverte. Si un joueur échoue, ils ont tous perdu. Notre objectif est de déterminer une stratégie pour le choix des boites qui optimise leurs chance de gagner.

1) Méthode naive: chaque joueur choisit aléatoirement les 50 boites qu'il va ouvrir.
a) Quelle est la probabilité pour un joueur de retrouver son numéro ? -> 1/2
b) Quelle est la proba que les joueurs gagnent ? ->(1/2)¹⁰⁰

2) Permutations et cycles:
Soit n 1 un entier. On appelle permutation toute bijection de l'ensemble {1,...,n} dans lui-même. On les note sous la forme:

1         2    ...       n-1      n
(1)   (2)   ...  (n-1)   (n)

Pour n= 100 une telle permutation permet de représenter la répartition des numéros dans les boites. On appelle cycle de taille k une bijection de la forme
a₁ --> a₂ --> a₃ --> ... --> a_k --> a₁

ou les a_i sont des nombres distincts. Par exemple la permutation:

1 2 3 4 5
3 2 4 1 5

est le cycle  1 --> 3 --> 4 --> 1 de longueur 3

Dans tout l'exercice n sera égale à 100 et on ne considèrera que les permutations de {1,...,100}

a) Quel est le nombre total de permutations possibles ? --> Je pense a 100!

b) Soient a ₁,...,a_k des nombres distincts. Combien y a t-il de cycles de longueur k contenant tous ces nombres a_i ? -> Je comprends la question mais je vois pas comment faire...

c) Soit k 51. Montrer que le nombre de permutations contenant un cycle de longueur k est (k-1)!(100-k)! = 100! / k

3) Nouvelle stratégie

On note la permutation associée à la répartition des nombres dans les boites. Chaque joueur va parcourir le cycle de la permutation qui démarre à la boite correspondant à son numéro. Par exemple le joueur 5 va commence par ouvrir la boite 5. Si celle-ci contient le numéro 34, il va ensuite ouvrir la boite 34... Il continue jusqua ce qu'il ait trouvé son numéro 5 ou qu'il ait ouvert 50 boites.

a) Soit p100. Justifier que le joueur p retrouve son numéro si et seulement si p est dans un cycle de longueur inférieur à 50.

b) En déduire sous quelle condition les joueurs vont gagner avec cette stratégie. Montrer que leur probabilité de gagner est alors

1- = 1 - 1/K

(les sommes allant jusqu'a 100)

c) Evaluer numériquement cette proba et la comparer à celle obtenue avec la méthode naive.

Merci d'avance

Posté par inp inp

Je pense que la réponse à la 2)b) est (100-k)! comment l'expliquer ?

Pour la 2)c) je sais démontrer l'égalite mais même question comment l'expliquer?

Pouvez m'aider également sur la partie 3)???

Posté par rhomari rhomari

2/b/ c'est plutot (k-1)!cest presque un arrangement sauf  qu'il faut remarquer que si on garde l ordre tournant inchangé (par ex (1-2-3-4-1)et (2-3-4-1-2)..represente le meme cycle ;on k possibilitéde representé le meme cycle en commencant par pour j=1..k)pour les questions 1/ et 2/a c est ok
je crois avec 2/b tu peux revoir 2/c
indice il y a C_{100}^k et on arrange les autres elements qui sont d effectif 100-k...

Posté par inp inp

Bonsoir

Effectivement rhomari je comprends mieux pourquoi c'est (k-1)! puisqu'on veut un cycle de longueur k, je ne  peux choisir l'image de a1 que parmi les (k-1) nombres a2,..,ak, car si cette image était a1 soit un cycle a1->a1 de longueur 1. Ensuite on itère : (k-2) choix pour l'image de a2, etc.

En revanche je ne comprends pas du tout la dernière stratégie peut-on m'aider ?