Problème de Chaussettes

[Médiat]

@ansset

 Cliquez pour afficher

Donc vous proposez, 4 : 96,120,72,24,6
Ce qui est OK !

mais j'ai pourtant appliqué la même formule pour E(n,p) avec p non nul

C'est là qu'est le problème.

Vous y êtes presque

-----

[ansset]

@Mediat

 Cliquez pour afficher

non je ne propose pas 120, la formule proposée très tôt et validée me donne 126.
(6*5+11*6+8*3+3*2)
mais cela est sensé être 120.
bien sur , les multiplicateurs changent.
et j'ai vérifié mon tableur.

quand je dis la même formule, c'est en supprimant les termes en n,m avec m>n bien sur

[Médiat]

@ansset

 Cliquez pour afficher

la formule proposée très tôt et validée me donne 126.

Si la formule générale est juste mais que le résultat est faux, c'est parce que ... (j'ai beaucoup de mal à vous répondre sans trop en dire ...)

mais cela est sensé être 120.

Je le confirme

quand je dis la même formule, c'est en supprimant les termes en n,m avec m>n bien sur

Je n'avais pas de doute sur ce point

[mike.p]

Voilà ma seconde proposition, là je suis confiant ...

 Cliquez pour afficher

2 : 1, 0, 1, ( 2 )
3 : 5, 6, 3, 2, ( 16 )
4 : 96, 120, 72, 24, 6, ( 318 )
5 : 3528, 4320, 2460, 840, 180, 24, ( 11352 )
6 : 199620, 236880, 131400, 44400, 9900, 1440, 120, ( 623760 )
7 : 15908400, 18421200, 10039680, 3376800, 768600, 120960, 12600, 720, ( 48648960 )
8 : 1697149440, 1929070080, 1038219840, 348284160, 80438400, 13265280, 1552320, 120960, 5040, ( 5108105520 )
9 : 233631921600, 261750787200, 139556208960, 46739790720, 10911257280, 1856856960, 232848000, 21047040, 1270080, 40320, ( 694702028160 )

E(n) = ( (2n-1) ! / 2^(u-1) + (u-1)! ) /2 ;

E(n,0) = (n-1) (2n-3) ( E(n-1,0) - (n-2)! ) +
(n-1) (n-1) (n-2) ! +
(2n-3) E(n-1,1) +
E(n-1,2) ;


E(n,p) = ( 2n-p-1 ) * E(n-1,p-1) +
(p+ (2n-2-p) * (2n-3-p) /2 ) * E(n-1,p) +
(p+1) * ( 2n-2-p-1 )* E(n-1,p+1) +
(p+2) * (p+1) * E(n-1,p+2)/2 ) ;

si p=1 , retirer l'exclusion pour symétrie périodique : "(n-1) * (n-2) !" , soit "( n-1 ) !"

[ansset]

@Mediat

 Cliquez pour afficher

capito je crois,
dans la formule globale initiale:
"(2n-p-1)E(n-1,p-1) on recrée une paire dans un intervalle." ( dixit "me" )
sauf que dans le calcul de E(n,1) : E(n-1,0) est un cas singulier.
et donc cette partie de la formule est singulière
dans les 5 solutions de E(3,0), 2 sont cycliques et 3 non.
Or , les 2 cas cycliques ne créent que 3 solutions
les autres 6.
ainsi pour cette partie de E(4,1)
6*5=30 est faux à remplacer par
3*2+6*3=24
on retrouve donc 120 et non 126 .......au total pour E(4,1)

donc dans les calculs de E(n,1) il faut tenir compte du nb de cycles présents dans E(n-1,0), avec le même principe de calcul

de fait la singularité s'exprimait à deux endroits.

[Médiat]

@mike.p : , vous avez mis au jour la dernière subtilité ! (je n'ai pas dit mon dernier mot, si le sujet vous à amusé/intéressé, j'y reviendrai)

[Médiat]

@ansset : , c'est bien cela.

[Médiat]

Je suis en train de finaliser un petit document explicitant tous les calculs, dans le cas d'un étendage linéaire et circulaire ; afin de me relire j'ai envoyé la partie linéaire à un ami Arcturien, qui m'a répondu que mes calculs étaient faux, il est vrai que les Arcturiens ont 3 pieds, saurez-vous retrouver ses résultats ? (Je n'ai pas osé me poser la question pour un mille-pattes, il y a peut-être une formule générale à trouver ...)

Pour les Gastéropodes et les Dauphins, la question est facile.

[ansset]

ben une pause s'im "pause" pour moi.
vous direz à votre ami Arcturien qu'il a tous les remerciements de ma chère et tendre....

je me suis bien amusé en tout cas.
comme quoi un exposé simple peut receler des aspects bien plus fins.
c'est curieux, j'imaginai une solution linéaire plus simple, comme quoi .......

[mike.p]

@mike.p : , vous avez mis au jour la dernière subtilité ! (je n'ai pas dit mon dernier mot, si le sujet vous à amusé/intéressé, j'y reviendrai)

oui SVP ! quel dernier mot ?

mais est il encore possible que ce soit faux ? j'ai fait un montecarlo pour 12 et 13 en supposant que le total E(n) est juste et ça colle ...

en tous les cas , je vais parcourir tout le topic à la recherche de petites colles à ma portée !

MERCI encore

ps: maintenant, je vais ouvrir les spoilers d'Anset

[mike.p]

Je suis en train de finaliser un petit document explicitant tous les calculs, dans le cas d'un étendage linéaire et circulaire ; afin de me relire j'ai envoyé la partie linéaire à un ami Arcturien, qui m'a répondu que mes calculs étaient faux, il est vrai que les Arcturiens ont 3 pieds, saurez-vous retrouver ses résultats ? (Je n'ai pas osé me poser la question pour un mille-pattes, il y a peut-être une formule générale à trouver ...)

Pour les Gastéropodes et les Dauphins, la question est facile.

Voulez vous dire avec des triplets et nuplets au lieu de couples ? En faire une autre énigme ? chouette !

ps: Je n'ai pas pu uploader dans le forum mon javascript et sa page html ...

A ce soir peut-être !

[Médiat]

Voulez vous dire avec des triplets et nuplets au lieu de couples ? En faire une autre énigme ? chouette !

Oui, c'est bien cela et c'est bien là mon "dernier mot", vos précédents résultats sont tout à fait corrects.

[Médiat]

vous direz à votre ami Arcturien qu'il a tous les remerciements de ma chère et tendre....

L'idée de base était, bien sûr, d'aider votre "chère et tendre" à étendre les chaussettes au cas où ne l'aideriez pas vous-même

[Médiat]

Bonsoir,

ansset et mike.p ayant trouvé la solution, je poste immédiatement ce document, je n'ai pas eu le temps de le relire à fond, donc n'hésitez pas à le critiquer afin que je puisse l'améliorer.

ch.pdf

Un résultat intéressant : calculer l'espérance du nombre de paires dans le cas linéaire ...

[ansset]

vous tapez plus vite que ne tire Luky Luke !
Un petit point sur l'introduction de la règle dans le cas circulaire ou il n'est pas mentionné qu'on ne prend qu'un sens de rotation.
( même si cela semble aller de soi )
Cordialement.

[ansset]

Un résultat intéressant : calculer l'espérance du nombre de paires dans le cas linéaire ...

celle là je la garde pour ma "chère et tendre" en cas de bannissement définitif

[Médiat]

Un petit point sur l'introduction de la règle dans le cas circulaire ou il n'est pas mentionné qu'on ne prend qu'un sens de rotation.

Bonne remarque, je corrigerai.

[mike.p]

Bonsoir !

le pdf est ok et clair pour moi ... mais il me reste à refaire les calculs du linéaire dans le détail.

C'est parti pour les n-uplets sur ce même fil ? tant que c'est chaud ...

ou d'abord l'espérance du nombre de paires sur le total de configurations ? par un calcul direct ou bien une récurrence ?

ps : Cela m'aurait fait 0 dans un exam. Heureusement qu'il y a eu les signalements intermédiaires d'erreurs ...

[Médiat]

Bonsoir mike.p,

Le linéaire est beaucoup plus facile.

Sinon, on peut rester dans le même fil, et vous le faites comme vous le sentez.

Pour l'espérance une démonstration directe et astucieuse me plairait beaucoup, mais je ne l'ai pas ...

[mike.p]

Bonsoir Mediat,

il faut noter que pour les sommes P(n) des paires dans le cas circulaire, nous avons une relation de récurrence :
P(2)=2 et
P(n) = u ( 2n-3) P(n-1)

et nous savons déjà que la somme des configurations est ((2u-1)!/2^(u-1) + (u-1)! )/2

[mike.p]

Bonsoir Mediat,

décidément, je multiplie les erreurs de report ... j'ai utilisé indifféremment u ou n ( suis fautif mais ai pour complice cet écran minuscule ... )

je voulais dire :

il faut noter que pour les sommes P(n) des paires dans le cas circulaire, nous avons une relation de récurrence :
P(2)=2 et
P(n) = n ( 2n-3) P(n-1)

tandis nous savons déjà que la somme des configurations est ((2n-1)!/2^(n-1) + (n-1)! )/2

ps : on devrait pouvoir laborieusement montrer que le nombre de paires tend vers le nombre de configurations

[ansset]

salut mike.p
ce sujet t'a semble t il bien amusé.
on ne t'arrête plus. ( c'est un compliment respectueux )
mon ps : je ne comprend pas le tien ; nb de paires/nb de configurations. ?
Cdt

[Médiat]

Bonjour mike.p

P(2)=2 et
P(n) = n ( 2n-3) P(n-1)

tandis nous savons déjà que la somme des configurations est ((2n-1)!/2^(n-1) + (n-1)! )/2

ps : on devrait pouvoir laborieusement montrer que le nombre de paires tend vers le nombre de configurations

En écrivant P(n) = n(2n-2)!/2^(n-1), la limite est facile à calculer

Bonjour ansset
mike.p appelle "nombre de paires", le nombre de paires de chaussettes appariées dans l'ensemble des configurations possibles (dans le cas linéaire le résultat est sympa).

[Médiat]

Je viens de trouver, le résultat simple et plaisant, que "Nombre de paires Cas Linéaire(n)" = (2n-1)* "Nombre de paires Cas Circulaire(n)", puisque que (2n-1), c'est le nombre de rotations laissant une solution circulaire invariante, dans la mesure où les configurations périodiques n'interviennent pas (il y a forcément 0 paires), il n'y a pas à les prendre en compte.

Evidemment cette relation permet de calculer facilement le nombre de paires dans le cas linéaire, et d'établir que l'espérance d'avoir une paire appariée quand on étend n'importe quel nombre de paires de chaussettes au hasard est de 1 paire.

[mike.p]

Bonjour tous

En écrivant P(n) = n(2n-2)!/2^(n-1), la limite est facile à calculer

je ne comprends pas bien comment en profiter mais je vais travailler la question

Là je pensais au nombre d'éléments nuP=3 et 4. C'est une bonne prise de tête mais heureusement que nous avons commencé par 2 ! J'espère faire une proposition , surtout si je peux y travailler ce soir.

@Anset,
nous avons bien fait la paire sur ce sujet mais ça a été laborieux. Sans de bienveillants conseils, nous serions encore sûrs de nos premiers résultats faux. Ressaisissons nous ! Je suis sûr que Mediat va passer en dimension 2 et 3 avant la fin du fil. L'air de rien, le sujet peut aider à modéliser certaines idées en physique ...

merci à vous 2 pour cette expérience sympa sur FS. Je découvre qu'on peut vraiment s'amuser, peu importe le résultat si on finit par le comprendre.

[ansset]

nous avons bien fait la paire sur ce sujet mais ça a été laborieux. Sans de bienveillants conseils, nous serions encore sûrs de nos premiers résultats faux. Ressaisissons nous ! Je suis sûr que Mediat va passer en dimension 2 et 3 avant la fin du fil. L'air de rien, le sujet peut aider à modéliser certaines idées en physique ...
.

c'est certain.
le piège initial étant de voir un énoncé très simple.
mais ici, avec la preuve que le se cache dans les détails.
et aussi très stimulant de "jouer" à plusieurs.
merci.

[mike.p]

Bonsoir tous,

pour généraliser aux nuplets, il faut remplacer quelques paramètres par d'autres valeurs. Appelons j la taille du nuplet. Restons dans le contexte circulaire pour l'instant car l'autre se déduira par des suppressions d'éléments dans les expressions.

Je propose de traiter séparément les 4 sous-calculs et de les valider un à un :

E(n,0) = somme des nuplets sans couleur complète contigue.

E(n,p) = somme des nuplets avec p occurences de couleurs complètes contigues.

E(n) = somme des nuplets de longueur n

P(n) = somme des occurences de couleurs complètes contigues tous nuplets

Si vous êtes d'accord pour le découpage, je commence par le calcul le plus facile , celui de E(n) pour tout j.

 Cliquez pour afficher

Reprenons le calcul pour des paires et généralisons le pour les nuplets de longueur j.

Quelques paramètres parceque le 2 du nombre d'éléments dans une paire se confond avec le 2 du nombre d'arrangements des éléments d'une paire.

Nous étions convenus que lorsque j=2 , alors



Reprenons en détail

E(n) =
(
(
2n ! // somme de toutes les configs linéaires
- (2^n) ( n!) // somme de toutes les configs linéaires périodiques quand elles sont circulaires
)
/ (2^n) // suppression de la distinction des chaussettes de même couleur
)
/ 2n // circularité des configs restantes, donc non périodiques
+
(
n! // somme de toutes les configs périodiques directement indistinguées
/n // circularité des périodiques
)

autrement sur une ligne :



ce qui donne après simplification et regroupement

E_2(n) = ((2n-1)!/2^(n-1) + (n-1)! )/2

notons 2 la taille du nuplet et 2' le nombre d'arrangement de ce nuplet ( cette paire ) : 2x1 = 2
E_2(n) = ( ( (2n) ! - ( 2'^n) ( n !) ) /( 2n (2'^n) ) + n!/n

Il n'y a plus qu'à généraliser 2 en j et 2' en j!

E_j( n ) = ( (jn)! - (j!)^(n) (n)!)/ ( jn*(j!)^(n) ) + (n)!/n
E_j( n ) = ( (jn)! - (j!)^(n) (n)!)/( jn*(j!)^(n) ) + (n)!/n
E_j( n ) = (jn)!/jn*(j!)^(n) - (j!)^(n) (n)!/jn*(j!)^(n) + (n)!/n
E_j( n ) = (jn-1)!/(j!)^(n) - (n-1)!/j + (n-1)!



ou en ligne
E_j( n ) = (jn-1)!/(j!)^(n) - (n-1)! (j-1)/j

pour par exemple 3 et 4 , cela donne





ou en ligne
E_3(n) = ( 3n-1)! / 6^n + 2/3 (n-1)!
E_4(n) = ( 4n-1)! / 24^n + 3/4 (n-1)!
etc

Validez vous cette proposition pour tout j > 1 ?

[Médiat]

Bonjour,

Je vous propose les notations suivantes :
= nombre de pieds (donc on manipule des -uplets, que l'on appellera des -ssettes (c'est crétin mais ça me fait rire))
= nombre de -settes à étendre
= nombre de -settes dont toutes les chaussettes sont côte à côte (on continuera de parler de -settes appariées malgré l'abus de langage)
Nombre d'étendages linéaires de -settes dont appariées
Nombre d'étendages linéaires de -settes ; celui-là il est facile
Nombre d'étendages circulaires de -settes dont appariées
Nombre d'étendages circulaires de -settes

Vous le faites dans l'ordre où vous voulez, mais le cas linéaire est beaucoup plus simple.

Vos calculs ne me paraissent pas corrects (avec j=4 et n= 2 vous trouvez 9.5), pour une raison qui met le doigt sur la complexité supplémentaire : pour n = 4, les solutions périodiques peuvent être 2-périodiques ou 4 périodiques (alors, dans le cas général ...)

[mike.p]

Bonjour Mediat,

en effet, je l'ai constaté en faisant C(0)...
Par contre le reste passe plus facilement que prévu.

A ce soir

[mike.p]

Bonjour Mediat,

Evidemment cette relation permet de calculer facilement le nombre de paires dans le cas linéaire, et d'établir que l'espérance d'avoir une paire appariée quand on étend n'importe quel nombre de paires de chaussettes au hasard est de 1 paire.

Pour un étendage circulaire , le résultat est plus proche du modèle linéaire que du circulaire. Il faut, en plus, compter l'appariement du dernier avec le premier mais ne pas considrer les configurations réduites. Elles sont des classes ad hoc ne résultant pas d'un aléas avec équiprobabilité en amont.

La fonction de probabilité, doit pour simuler l'étendage d'un tas de chaussettes , donner des poids différents aux configurations selon le nombre d'équivalentes. Par exemple , dans le cas des paires en circulaire , une configuration périodique sera tirée 2 fois plus que qu'une autre non périodique. Un tirage basé sur l'aléas primaire du tas de chaussettes ne produira pas des configurations toutes équiprobables.

On devrait s'attendre à retrouver le résultat du linéaire légèrement décalé puisqu'il y a de temps en temps un appariement en plus. C'est un calcul à tenter en partant de la solution du linéaire.

Je reprends un peu ce soir et beaucoup demain le problème de la généralisation du circulaire avec n>2 et premier en espérant que nous serons nombreux à tenter de résoudre cette suite de l'énigme !