Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
158 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 
Ce problème a été posé à l'origine sur le forum du site par Robert. Pierre RENFER a apporté la solution et a prolongé la question par une jolie conjecture qu'il a finalement aussi résolue. Voici l'article qu'il nous envoie.

LES CHAUSSETTES

On accroche sur un fil d'étendage n paires de chaussettes de  n couleurs distinctes, deux chaussettes d'une même paire étant indiscernables

Combien existe-t-il de rangements sans que deux chaussettes d'une même paire ne soient  voisines?

Si l'on accroche les chaussettes au hasard, quelle est la probablité  pour que deux chaussettes d'une même paire ne soient pas voisines?

Quelle est la limite de  , quand n tend vers ?

SOLUTION

1)   Une première relation de récurrence

Soit  le nombre de rangements possibles.

Soit  le nombre de répartitions des paires indépendamment du choix de leurs couleurs.

A partir d'une telle répartition, il suffit ensuite pour obtenir un rangement, de déterminer les couleurs des paires

Comme il y a n! façons de choisir les couleurs :

Par exemple :  

  •       ( La seule répartion possible est l'alternance des deux couleurs )
  •      ( Il y a deux façons de choisir la couleur initiale )
  •       ( ABACBC , ABCABC, ABCACB , ABCBAC, ABCBCA )
  •       ( Dans chacun des cinq  cas, il y a six façons de colorer A,B,C )

On obtient une relation de récurrence pour les      de la façon suivante :

Soit A la chaussette en première place; l'autre chaussette A de la même paire peut être entourée ou non de deux chaussettes d'une même paire

-         Si elle n'est pas entourée de deux chaussettes d'une même paire ( cas le plus général et l

      plus facile ), alors il y a  façons de choisir sa place et l'on obtient en supprimant les

      deux chaussettes A une répartition de  paires  :

      Le nombre de telles possibilités est donc :

-     Si elle est  entourée de deux chaussettes d'une même paire B et si le bloc BAB n'est pas

      entouré de deux chaussettes d'une même paire, alors il y a  façons de choisir sa place

      et l'on obtient en supprimant les deux chaussettes A et les deux chaussettes B une répartition

      de  paires  :

      Le nombre de telles possibilités est donc :

-         Si le bloc BAB est  entourée de deux chaussettes d'une même paire C et si le bloc CBABC

       n'est pas entouré de deux chaussettes d'une même paire, alors il y a  façons de

       choisir sa place et l'on obtient en supprimant les chaussettes A, B et C une répartition de

       paires  :

      Le nombre de telles possibilités est donc :

En continuant ainsi l'étude des cas successifs, on obtient finalement avec la convention  :

Le premier terme peut se décomposer en :    et donc :

En commençant par la fin, on peut encore écrire la relation sous la forme

       ( )

2)  Une deuxième relation de récurrence

     On introduit la série entière :

     ( Il n'est pas nécessaire de se tracasser sur le rayon de convergence si l'on utilise les séries

      entières formelles ).

     La relation ( ) peut s'écrire :

     Pour  , le premier membre est le coefficient devant  de f(x)-1 .

     Dans le second membre, le premier terme est le coefficient devant  de  .

      est le coefficient devant  de , donc le coefficient devant  de  .

      est le coefficient devant  de , donc le coefficient devant  de  .

     La relation ( ) se traduit donc par l'équation différentielle :

         ou      

     La dernière forme de l'équation différentielle permet d'obtenir la relation :

   ,              ( )

    

     On peut remarquer que la relation ( ) peut être démontrée directement par récurrence, à partir

     de la relation  ( ) , sans passer par l'équation différentielle.

3)   Calcul de la probabilité

Le nombre total de rangements est

( On divise par  car pour chacune des n paires l'échange des deux chaussettes de la paire ne modifie pas le rangement ).

Donc  :

( Le dernier dénominateur est le produit de tous les facteurs impairs de 3 à (2n-1)

En divisant par ce dénominateur les deux membres de la relation ( ) , on obtient

La suite  est donc croissante.

Comme par ailleurs elle est majorée par 1, elle converge

Sit k un entier tel que :  ,

Soit  l'événement : "Aux deux places consécutives numéro k et numéro (k+1) sont rangés deux chaussettes d'une même paire".

Alors la réunion  est l'événement contraire de celui qu'on étudie.

La probabilité de cette réunion est  , mais on peut aussi la calculer par la formule du crible de Poincaré (Saint Patron du site) :

    ,    avec 

Dans la somme  les termes sont nuls s'il existe des indices consécutifs parmi les indices  et les autres termes ont pour valeur commune :

( En effet  est la probabilité d'obtenir immédiatement à droite de la chaussette de rang   l'autre chaussette de la même paire, puis  est la probabilité d'obtenir immédiatement à droite de la chaussette de rang   l'autre chaussette de la même paire, etc… ).

Pour calculer le nombre de termes non nuls de , c'est-à-dire le nombre de façons de choisir  k indices   sans indices consécutifs parmi eux, on peut retrancher 1 à l'indice  , 2 à l'indice  , 3 à l'indice , … , (k-1) à l'indice  . On est ainsi ramené à compter le nombre de façons de choisir k indices entre 1 et (2n-k) sans contraintes : ce nombre est  .

La formule du crible donne donc

  et :

    

5)  Calcul de la limite

Soit p la limite de la suite


En posant  , on a :

Or       et   

     Si l'on choisit un entier  , on peut écrire :  

Et  :    et  

Donc en passant à la limite qand n tend vers  , on obtient :

   , pour tout entier naturel m

En passant à la limite qand m tend vers  , on conclut que

Solution trouvée et rédigée par Pierre RENFER

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page