Les paires de chaussettes

[Ben314]

Salut,
Un problème tiré du site "diophante" et sur lequel je suis un peu sec (pour le moment) :
Quelle est la probabilité que, lorsque l'on étend un nombre N tendant vers l'infini de paires de chaussettes sur une corde à linge, il n'y ait pas deux chaussettes d'une même paire qui soient côte à côte ?
(il est évidement sous entendu que toutes les disposition possibles pour les paires de chaussettes sur la corde à linge sont équiprobables)

[Doraki]

J'ai pas de preuve complète pour le moment mais exp(-1/2) ne devrait pas être loin.

[Ben314]

Perso, je trouve plutôt exp(-1) comme limite des avec
mais j'ai pas de preuve non plus . . .

[Doraki]

Ah hier soir j'ai mal lu l'énoncé, j'ai cru qu'on les attachait par paires du coup je dois recommencer à zéro lol.
Mais si j'estimais exp(-1/2) en retirant la moitié des contraintes, je devrais pencher vers exp(-1) en rajoutant la deuxième moitié.

J'ai (avec le principe d'inclusion-exclusion)


p(0) = 1
p(1) = 0
p(2) = 1/3
p(3) = 1/3
p(4) = 12/35

Le problème maintenant c'est de vérifier qu'on puisse intervertir limite et somme infinie, ce qui donnerait

[Doraki]

Si je ne me trompe pas , pour tout k, la suite des k-ièmes termes est croissante en valeur absolue,
donc on peut couper la somme selon la parité de k et appliquer le théorème de convergence monotone.

[Ben314]

Effectivement, ça marche bien comme ça.
Au départ j'avais bien pensé à utiliser le principe d'inclusion-exclusion sauf que j'ai trouvé rapidement une formule de récurrence (c.f. post précédent) et je me suis obstiné dessus sans résultat.
D'ailleurs, ça m’intéresserais de voir s'il y a moyen de trouver, (en fonction de et ) la limite de la suite définie par

[GaBuZoMeu]

Bonsoir,

Je comprends parfaitement la méthode de comptage par la formule de Poincaré.
On note l'événement "les chaussettes de la -ème paire sont côte à côte et pour partie de .
Le nombre d'étendages dans , pour de cardinal , est effectivement : on compte le nombre de façons d'arranger les 2n-2k chaussettes des paires pas dans et les paires dans (ceci explique le , puis pour chaque paire dans on a deux choix pour l'ordre des chaussettes de la paire (ceci explique le ).
Les étendages favorables sont ceux du complémentaire de la réunion des pour de 1 à , et la formule du crible de Poincaré donne bien la formule écrite par Doraki plus haut. Le passage à la limite quand qui donne ne pose pas de problème.

Par contre, je ne comprends absolument pas la relation de récurrence de Ben. Est-il possible d'avoir une explication ?

[Ben314]

En fait ce que je compte, c'est le nombre An de façon de relier 2 à 2 les 2n cases d'une ligne de longueur 2n.
Si on ne pose aucune contrainte, il y a (2n)!/(2^n.n!) façons de procéder.
Si on impose de ne jamais relier deux cases voisines, on peut procéder par récurrence en regardant ce qu'il se passe si on enlève le lien partant de la première case. Si la case d’arrivée du lien est entourée par deux cases non reliées, en enlevant ce lien (partant de la première case ) on obtient une situation cohérente à l'ordre n-1. Si les deux case qui entourent la case d'arrivée sont reliées mais que les suivantes ne le sont pas, on obtient une situation cohérente d'ordre n-2, etc . . .
Après calculs on en déduit une formule donnant An en fonction des Ak k<n et en soustrayant deux telles formules à l'ordre n et n+1 on en déduit une formule donnant An en fonction de A(n-1) et A(n-2) qui conduit à la formule que je donne sur les proba.
Je peut, si besoin est, renter plus dans les détails, mais là, j'ai pas le temps . . .

[GaBuZoMeu]

D'accord, merci. J'en étais resté dans mes réflexions à l'étape où la récurrence fait intervenir toutes les étapes antérieures. Je vais revoir avec tes indications.
J'ai fait aussi une petite simulation en python, en comptant, parmi 1000 étendages d'une lessive de 100 paires de chaussettes, combien il y en a sans paire côte à côte.

Code: Tout sélectionner

import random as rd

n=100
Lessive=[(i,j) for i in range(n) for j in range(2)]

def Etendage() :
    favorable=1
    derniere = -1
    Aetendre=Lessive.copy()
    while len(Aetendre)>0 :
        chaussette=rd.choice(Aetendre)
        if chaussette[0]!=derniere :
            derniere=chaussette[0]
            Aetendre.remove(chaussette)
        else :
            favorable=0
            break
    return favorable

for j in range(20) :
    favorable=0
    for i in range(1000) :
        favorable+=Etendage()
    print(favorable)

371
358
371
351
359
348
369
371
373
356
366
350
360
381
365
372
358
357
368
370

[GaBuZoMeu]

J'ai vu la récurrence. Si l'on appelle le nombre de "bonnes" partitions en paires (paires de non voisins) de , on a , et en enlevant la paire qui contient comme tu le fais, on obtient

d'où l'on tire par soustraction
.
Cette suite est connue dans OEIS : https://oeis.org/A278990.
On en déduit bien
.

[GaBuZoMeu]

Re,

Mon programme de simulation est un peu lambin. C'est parce que je lui fais à chaque étape choisir une chaussette dans le bac de ce qui reste à étendre.

En voici une version améliorée et commentée.

Code: Tout sélectionner

import random as rd

n=100
Lessive=[(i,j) for i in range(n) for j in range(2)]
# La lessive compte n paires de chaussettes
# chaque chaussette est repérée par le couple (i,j) :
# i est le numéro de la paire, j vaut 0 ou 1 (gauche et droite, si on veut)

def Etendage() :
    favorable=1
    # reste à 1 si pas de paire côte à côte, mis a 0 sinon.
    derniere = -1
    # n° de la paire de la dernière chaussette étendue
    Aetendre=Lessive.copy()
    rd.shuffle(Aetendre)
    # on mélange la lessive pour obtenir une liste d'ordre aléatoire
    # (la liste à étendre)
    while len(Aetendre)>0 :
        # tant qu'il reste des chaussettes dans la liste à étendre
        chaussette=Aetendre.pop()
        # on enlève la dernière chaussette de la liste à étendre
        # et on la met sur le fil
        if chaussette[0]!=derniere :
            derniere=chaussette[0]
        # si le n° de la paire de la dernière chaussette étendue
        # est différent de celui de la chaussette qu'on est en train
        # d'étendre, on actualise ce n° et on continue
        else :
            favorable=0
            break
        # si c'est le même, on met favorable à 0 et on arrête
        # car on a trouvé une paire côte à côte.
    return favorable

Avec ce code on peut sans trop attendre faire 1000 étendages de 1000 paires en notant le nombres de bons étendages :
349
355
380
345
366
373
369
371
376
372
374
356
383
403
341
373
351
392
381
372

J'ai commenté le code pour faciliter la compréhension d'un lecteur assidu qui avait interprété le précédent code de travers. Il n'est pas évident qu'il comprendra mieux cette fois-ci.
Ce même lecteur assidu s'est lancé dans une simulation erronée : pour l'étendage il tire au hasard (de manière uniforme) le n° de la paire de la prochaine chaussette. Ça ne va bien sûr pas du tout. Si on part avec 10 paires numérotées de 0 à 9 et qu'on tire une première chaussette de la paire n° 0, alors pour la deuxième chaussette on n'aura plus qu'une chance sur 19 (et pas une chance sur 10) de tirer de nouveau une chaussette de la paire n°0 : dans le bac à étendre qui contient 19 chaussettes, il n'en reste plus qu'une de n°0 ! Avec ce genre de simulation conçue de travers, pas étonnant qu'on ne trouve pas de résultat conforme à ce qui a été démontré dans ce fil !

[GaBuZoMeu]

Il n'est pas évident qu'il comprendra mieux cette fois-ci.

Il n'a toujours pas compris ...

[Ben314]

Pour le cas général avec , vu la linéarité, il suffit de regarder le cas déjà étudié (avec une limite égale à exp(-1)) ainsi que le cas .
Sauf erreur, dans le deuxième cas, la limite est SinHyp(1).