Probabilités - Permutations et cycles stratégies

[invite5be156de]

[/TEX]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)100

2) Permutations et cycles:
Soit n >(ou égal) 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
sigma(1) | sigma(2) | ... | sigma(n-1) | sigma(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 ai 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 trop expliquer, c'est (k-1)! mais bon pourquoi...

c) Soit k >(ou égal) 51. Montrer que le nombre de permutations contenant un cycle de longueur k est

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 p <(ou égal)100. 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



(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
-----

[invite986312212]

pour b) tu peux utiliser le même raisonnement que pour a) mais puisque tu veux un cycle de longueur k, tu ne peux choisir l'image de a1 que parmi les (k-1) nombres a2,..,ak, car si cette image était a1 tu aurais un cycle a1->a1 de longueur 1. Ensuite tu itères : (k-2) choix pour l'image de a2, etc.

[invite5be156de]

Merci ambrosio pour ta réponse, ca clarifie bien m'a pensé je comprends mieux.

Quelqu'un pourrait-il m'expliquer la question 2)c) , j'arrive aisément a démontrer l'égalité mais je ne sais pas l'expliquer ?

Pour la partie 3 par contre c'est le flou...