Répondre à la discussion
Page 1 sur 7 12 3 4 5 6 DernièreDernière
Affichage des résultats 1 à 30 sur 202

Problème de Chaussettes



  1. #1
    Médiat

    Problème de Chaussettes


    ------

    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.

    -----
    Dernière modification par Médiat ; 06/04/2016 à 07h22.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  2. Publicité
  3. #2
    Médiat

    Re : Problème de Chaussettes

    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
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  4. #3
    Médiat

    Re : Problème de Chaussettes

    Trop compliqué ?
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  5. #4
    mike.p

    Re : Problème de Chaussettes

    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 ?

  6. A voir en vidéo sur Futura
  7. #5
    Médiat

    Re : Problème de Chaussettes

    Bonjour,
    Citation Envoyé par mike.p Voir le message
    - 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 )

    Citation Envoyé par mike.p Voir le message
    - 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.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  8. #6
    mike.p

    Re : Problème de Chaussettes

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

  9. Publicité
  10. #7
    Médiat

    Re : Problème de Chaussettes

    Avec 2 paires il n'y a bien que 2 cas : AABB et ABAB
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  11. #8
    ansset
    Animateur Mathématiques

    Re : Problème de Chaussettes

    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.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  12. #9
    mike.p

    Re : Problème de Chaussettes

    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 ...
    Dernière modification par mike.p ; 07/04/2016 à 13h52.

  13. #10
    Médiat

    Re : Problème de Chaussettes

    Bonjour ansset
    Citation Envoyé par ansset Voir le message
    S(n,n)=(n-1)!
    Oui, en particulier S(3, 3) = 2

    Citation Envoyé par ansset Voir le message
    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) ...
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  14. #11
    Médiat

    Re : Problème de Chaussettes

    Citation Envoyé par mike.p Voir le message
    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
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  15. #12
    ansset
    Animateur Mathématiques

    Re : Problème de Chaussettes

    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.
    Dernière modification par ansset ; 07/04/2016 à 14h18.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  16. Publicité
  17. #13
    ansset
    Animateur Mathématiques

    Re : Problème de Chaussettes

    bon, il faut surtout que j'évite d'aller trop vite.
    c'est casse gueule
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  18. #14
    Médiat

    Re : Problème de Chaussettes

    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 ?) ?
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  19. #15
    ansset
    Animateur Mathématiques

    Re : Problème de Chaussettes

    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.
    Dernière modification par ansset ; 07/04/2016 à 14h47.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  20. #16
    ansset
    Animateur Mathématiques

    Re : Problème de Chaussettes

    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 )
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  21. #17
    mike.p

    Re : Problème de Chaussettes

    Citation Envoyé par Médiat Voir le message
    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.

  22. #18
    ansset
    Animateur Mathématiques

    Re : Problème de Chaussettes

    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.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  23. Publicité
  24. #19
    mike.p

    Re : Problème de Chaussettes

    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.

  25. #20
    ansset
    Animateur Mathématiques

    Re : Problème de Chaussettes

    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.
    Dernière modification par ansset ; 07/04/2016 à 17h14.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  26. #21
    Médiat

    Re : Problème de Chaussettes

    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
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  27. #22
    mike.p

    Re : Problème de Chaussettes

    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.

  28. #23
    Médiat

    Re : Problème de Chaussettes

    Bonjour,

    Qu'appelez-vous E(n, 0) "dont les résultats sont disponibles" ?
    Dernière modification par Médiat ; 08/04/2016 à 12h32.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  29. #24
    mike.p

    Re : Problème de Chaussettes

    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.

  30. Publicité
  31. #25
    Médiat

    Re : Problème de Chaussettes

    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é)
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  32. #26
    mike.p

    Re : Problème de Chaussettes

    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 ) ?
    Dernière modification par mike.p ; 08/04/2016 à 14h27.

  33. #27
    Médiat

    Re : Problème de Chaussettes

    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.
    Dernière modification par Médiat ; 08/04/2016 à 14h38.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  34. #28
    ansset
    Animateur Mathématiques

    Re : Problème de Chaussettes

    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.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  35. #29
    mike.p

    Re : Problème de Chaussettes

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

  36. #30
    Médiat

    Re : Problème de Chaussettes

    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 !
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

Page 1 sur 7 12 3 4 5 6 DernièreDernière

Discussions similaires

  1. Actualité - Des chaussettes qui utilisent de l'urine pour produire de l'électricité
    Par V5bot dans le forum Commentez les actus, dossiers et définitions
    Réponses: 4
    Dernier message: 16/12/2015, 08h06
  2. mon chien sent les chaussettes
    Par ptitpoint dans le forum Santé et médecine générale
    Réponses: 0
    Dernier message: 18/05/2009, 08h43
  3. Bientot des chaussettes en laine de mamouth ?
    Par acropole dans le forum Actualités
    Réponses: 2
    Dernier message: 23/11/2008, 15h49
  4. [identification] la mangeuse de chaussettes
    Par dolmen dans le forum Identification des espèces animales ou végétales
    Réponses: 6
    Dernier message: 27/11/2006, 20h02