Problème de Chaussettes

[Médiat]

Bonjour,

Tout est dans le fichier : cc.pdf
Vous pouvez proposer tous les résultats que vous voulez, les résultats sur des cas particuliers permettant de "valider" les résultats généraux.
-----

[Médiat]

Une précision : les solutions obtenues à l'aide d'un programme sont les bienvenues, ne serait-ce que pour valider les formules obtenues par ailleurs

[Médiat]

Trop compliqué ?

[mike.p]

Bonjour,

c'est peut être très simple mais je ne vois pas encore ...

Sinon, pour une approche sans astuce particulière , j'ai 2 petites questions liées :

- l'image semble suggérer que les chaussettes droite et gauche sont identiques et donc que DG = GD ( à l'échelle d'une paire donc ). Est ce bien ça ?

- si A , B , C , D et E sont des paires pas nécessairement homogènes, doit on considérer que ABCDE = EDCBA ou bien compter 2 combinaisons ? Ou bien alors, faut il distinguer les paires homogènes des autres parce qu'une paire non homogène n'a pas de symétrie interne ?

[A voir en vidéo sur Futura]

[Médiat]

Bonjour,

- l'image semble suggérer que les chaussettes droite et gauche sont identiques et donc que DG = GD ( à l'échelle d'une paire donc ). Est ce bien ça ?

Oui (on pourrait se poser la même question avec des gants, mais ce serait un tout autre problème )

- si A , B , C , D et E sont des paires pas nécessairement homogènes, doit on considérer que ABCDE = EDCBA ou bien compter 2 combinaisons ? Ou bien alors, faut il distinguer les paires homogènes des autres parce qu'une paire non homogène n'a pas de symétrie interne ?

Je ne suis pas sûr de comprendre ce que vous voulez dire par "paire homogène ou non", mais si A, B, C, D et E sont des paires de chaussettes différentes (A est constituée des 2 chaussettes d'une même paire, différentes des paires B, C, D et E), alors ABCDE != EDCBA, mais ABCDE = BCDEA = CDEAB = DEABC ...

N'hésitez pas à me solliciter surtout si je n'ai pas bien compris votre question.

[mike.p]

Les chaussettes neuves droites et gauches ne sont pas toujours identiques !

donc
Ag Ad Bd Bg = Ad Ag Bg Bd

en permutant les 2eme et 3eme , soit l'AB central , on a toujours Ag Bd Ad Bg = Ad Bg Ag Bd.
Finalement, c'est plutôt AABB qui devient ABAB. Il était possible que la 1re égalité soit vraie mais pas la seconde.

Autrement dit, au lieu de chaussettes, on peut prendre des lettres ( propres à chaque paire ).

Je tenterai d'y répondre samedi ...

[Médiat]

Avec 2 paires il n'y a bien que 2 cas : AABB et ABAB

[ansset]

je suppose que ( c'est du Médiat ) donc j' y vais avec prudence.
S(n,n)=(n-1)!
S(n,n-1)=S(n,n)*(n-2)
( toussatousaa à grosses boulettes près )
après , je pense qu'une itération devient vite très lourde.
donc piste très incertaine.

[mike.p]

PP.iiiiii.PP.PP.i.PP..PP.iiiii

pour p paires, il y a (p-1)! façons de les disposer en cercle. Ensuite le restant est découpé en simples segments ( ii ) insérés entre les paires ( PP ). La taille de chaque segment va de 0 à 2(n-p) ( et leur somme faisant 2(n-p) ). Commencer par calculer E(n,0) et monter une récurrence à la façon d'une binomiale de Sterling 2e ? Il faudrait déjà exprimer correctement E'(a,0) quand a est indiféremment pair ou impair et pris parmi b chaussettes.
Il y a peut être ( et surement ) plus simple , une autre binomiale connue , c'est à creuser ...

[Médiat]

Bonjour ansset

S(n,n)=(n-1)!

Oui, en particulier S(3, 3) = 2

S(n,n-1)=S(n,n)*(n-2)

Je ne crois pas, mais comme je ne sais pas comment vous en êtes arrivé là, je ne peux pas commenter. Avez-vous calculé S(3, 2).


Précision : je n'ai pas trouvé cette énigme sur internet, donc il n'est pas impossible (), que je me sois planté à un moment ou à un autre (c'est pourquoi j'ai tenté de lancer des programmeurs sur le coup) ...

[Médiat]

PP.iiiiii.PP.PP.i.PP..PP.iiiii

pour p paires, il y a (p-1)! façons de les disposer en cercle.

Il me paraît impossible que n n'intervienne pas dans le positionnement des p paires parmi 2n positions

[ansset]

non, je me suis trompé.
l'idée pour S(n,n-1) est de perturber le bel arrangement S(n,n)
en supposant que dans une paire, les deux chaussettes sont identiques ( pas comme sur mes pieds )
mais je n'ai modifié( détruit ) qu'une seule paire possible.
donc plutôt
S(n,n-1)=s(n,n)*n*(n-2)
une paire possibles détruites parmi n et n-2 possibilités pour placer une chaussette "égarée" de cette paire.
j'essaye de raisonner dans le cas général, donc sans tenir compte du minimum n nécessaire.

[ansset]

bon, il faut surtout que j'évite d'aller trop vite.
c'est casse gueule

[Médiat]

Je comprends qu'à partir d'une position (n, n) (il y en a S(n, n)), vous choisissez une paire (il y a le choix parmi n), mais que fait-on de ces deux chaussettes (pourquoi n-2 façons ?) ?

[ansset]

j'en place une dans les n-2 trous sans casser une autre paire.
ha ça ne suffit pas , je peux aussi déplacer la deuxième effectivement avec aussi n-2 places.

[ansset]

du coup je me demande s'il n'est pas plus simple de partir de S(n,0) à calculer.
et de reconstruire les paires.
plutôt que de faire la démarche inverse.
c'est peut être équivalent ( dans la lourdeur )

[mike.p]

Il me paraît impossible que n n'intervienne pas dans le positionnement des p paires parmi 2n positions

c'est juste que cet algo passe par là ... n interviendra plus loin dans la taille du tas d'éléments restants, partitionné ( en fait ce sont des nuplets et certains peuvent être nuls pour marquer la contiguité ) entre les paires.

J'en profite : il est possible de remplacer les p paires par p chaussettes invisibles ( donc unitaires surtout ) pour supprimer les paires appariées du schéma ; leur diversité est dans ( p-1) ! Ou encore dire qu'on réduit le schéma initial par un objet commun aux "paires formées" et aux "chaussettes restantes". Afin de tenir compte du fait qu'une paire est un séparateur.
Ca permet de travailler sur un segment de taille 2n-p , c'est à dire 2(n-p) chaussettes de (n-p) couleurs + p invisibles.
Il reste à calculer cette variante de E(n,0) , c'est à dire E(2n-p,0) qui serait peut être redondante et à la base d'une récurrence.

[ansset]

je pense comprendre ton approche.
p paires associées et 2(n-p) places à prendre avec des "orphelines".
mais pourquoi ton segment 2n-p, ? ça m'échappe.

[mike.p]

c'est juste (n-p) paires + p invisibles, soit 2(n-p)+p

Ce qui ramène à un problème proche du graphe des cocktails c'est à dire E(n,0). Mais proche seulement car les invisibles peuvent se suivre et ils peuvent être plus de 2 ... D'autre part, se passer des invisibles et les faire glisser à la fin complique les choses car ils jouent aussi le rôle de séparateur : une couleur peut commencer avant une paire appariée et suivre après. Il faudrait reprendre le calcul classique de E(n,0) et voir comment exclure/inclure les invisibles

Pour @Mediat :
bien sûr la diversité des paires n'est pas rendue par ( p-1) ! ... désolé de cette erreur grossière , c'est le nombre d'arrangements de p paires parmi n couleurs divisé par p. Pas de pb pour qu'un tel produit de termes consécutifs soit divisible par leur nombre.

[ansset]

pas sur de comprendre ce que tu appelles "invisibles".
pour moi, pour p paires appareillées, il y a de 1 à 2(n-p) "espaces" disponibles pour les "orphelines".
chacun étant potentiellement de taille allant aussi de 1 à 2(n-p) , mais cela dépend du nb d'espaces.

[Médiat]

Bonjour,

J'ai un peu réfléchi à la proposition de mike.p, j'ai peur que cela ne fasse que compliquer les choses, puisqu'il faut placer les 2n-p objet en faisant attention que certains d'entre eux ne doivent pas être placés côte à côte, j'ai l'impression que cela ne fait que déplacer le problème ... A suivre néanmoins

[mike.p]

Salut,

c'est aussi ce que je me suis dit ce matin ... Mais les autres approches ont l'inconvenient de devoir tout reprendre alors que E(n,0) est un cas d'école dont les résultats sont disponibles ( et qu'il n'est pas facile de résoudre du 1er coup ). De plus,elle fait apparaitre des sommations E(q) dans les exclusions-inclusions. Il me reste à trouver une astruce pour incorporer mes invisibles qui règlent le problème du pseudo-partionnement et de la propriété de séparation qu'ont les paires.

Mais je suis persuadé que c'est la méthode du boeuf et qu'il y a une récurrence à pas de 2 quelque part.

[Médiat]

Bonjour,

Qu'appelez-vous E(n, 0) "dont les résultats sont disponibles" ?

[mike.p]

re Bonjour,

On pose E(n , p) = Nombre de façons d'étendre n paires de chaussettes de sorte que les deux
chaussettes de p de ces paires soient côte à côte

E(n,0) correspond donc aux nombre d'arrangements circulaires de n paires sans aucune paire appariée.

Dans le problèmes des cocktails, les paires de chaussettes sont des couples à disposer autour d'une table sans aucun couple réuni. Il y a le cas où madame et monsieur sont indistinguables et l'autre ( d'où ma 1ère question ).

Le calcul de la somme E(n) peut se faire directement, c'est le nombre de dispositions quelconques des chaussettes.

[Médiat]

Vous auriez une référence parce que chercher cocktail sur le net, c'est un coup à finir bourré rien qu'en lisant la liste des résultats .

La somme E(n) n'est effectivement pas très difficile à calculer (il y a quand même une subtilité)

[mike.p]

Normalement "cocktail party graph" devrait donner tous les résultats ...

pour E(n) , il faut repartir sur des unités et diviser par 2^n symétries ( 1 bit pour chaque couleur ) ?

[Médiat]

Non, c'est un peu plus subtil (ce n'est pas complètement faux, si à un moment vous en avez marre , je pourrais commencer par donner quelques indices ...

Le problème n'est pas très connu/médiatisé car à part quelques cas très particuliers, les séries obtenues ne sont pas sur OEIS.

[ansset]

salutations,
me suis rendu compte hier de la complexité combinatoire.
et sans avoir de référence pour ce type de résolution.
je me contente de vous lire maintenant en attendant de m'instruire un peu.
Cdt.

[mike.p]

Je comptais les arrangements circulaires de 2n chaussettes soit ( 2n -1 ) ! ; si monsieur a l'indicateur 0 et madame 1 , chaque combinaison est caractérisée par un nombre de n bits dont on ne veut qu'une. Il doit manquer une symétrie car ( 2n -1 ) ! n'est pas divisible par 2^n ...

>> langue au chat
Franchement non, et ce d'autant que je dois avoir la solution quelque part d'un problème similaire ( mais je ne cherche pas ).

Au moins jusqu'à dimanche ce serait cool. Je voudrais explorer ce samedi avant de me ruer sur les exclusions-inclusions ...

[Médiat]

ansset : je suis parti de 0 pour ce problème, ne vous en faites pas une montagne

mike.p : pas de problème, amusez-vous bien !