Problème de Chaussettes

[Médiat]

Bonjour,

par exemple pour 4 qui correspond à 2 , 4

Ce n'est pas avec des exemples que j'ai un problème, mais avec le cas général
-----

[mike.p]

Bonjour,


Ce n'est pas avec des exemples que j'ai un problème, mais avec le cas général

Bonjour Mediat,

et comme ceci :

Etablissons :
= { les q diviseurs entiers de k sauf 1 }

la diversité linéaire =


Total d'une symétrie seule sans celle de ses multiples =


Total de la ligne =



?

[mike.p]

grosse correction

Total de la ligne =


le but était bien d'isoler chaque total pour lui appliquer son diviseur de circularité, sans quoi on retrouve le total linéaire

[mike.p]

Bonjour Mediat,

Je reprends proprement car il y avait encore une petite erreur assez repérable

Etablissons :
= { les q diviseurs entiers de k sauf 1 }
= { les q diviseurs entiers de k }

la diversité linéaire =


Total d'une symétrie seule sans le décompte de ses multiples =


Total de la ligne =


en effet, 1 doit être inclus dans le total pour inclure le sous ensemble sans symétrie

Ca donne pour n = 2
k=2 : 2
3: 4
4: 10
5: 26
6: 80
7: 246
8: 810
9: 2704
10: 9252
11: 32066
12: 112720
13: 400024
14: 1432860
15: 5170604

les problèmes d'arrondis commencent sur javascript/firefox avec k = 13

[Médiat]

Bonjour mike.p

Je ne dois pas bien comprendre vos résultats, si je tente de calculer pour n=2, je trouve -4.

D'autre part, en l'absence d'une démonstration, je ne suis pas (encore) persuadé que ce soit aussi simple, surtout dans les cas où k est "complexe" (mais difficile de faire des contrôles à cause de la volumétrie (pour k = 12 par exemple)) ...

[mike.p]

Bonjour Mediat,

2 n'est pas un multiple de 4. Il y a un changement d'index avec Dq.

En effet, il faut tout démontrer. J'en ai fait quelques unes et d'autres restent à effectuer. Sans cela, impossible d'avancer. Hier, j'ai revu les propriétés des générations de distributions symétriques. Heurement, j'escamote le calcul de la ligne 2 qui est complexe ( l'unique k-sette de n=1 est symétrique pour tout k ).

Cette complexité n'est rien à côté de celle de l'élimination des k-settes de p+2 à p+k que vous avez du traiter pour le linéaire et le circulaire à k premier. Là, il faut décomposer chaque valeur en somme et répérer les redondances ...

C'est ce qui rend ce problème si prenant : on pense toujours être à 5 min de la solution ...

[mike.p]

en effet, je me suis un peu emmêlé dans la définition des Dk

D'_k = { des diviseurs entiers de k , 1 et k inclus }

et dans le contexte fixe de k ,
D_x_k = D_x = { des multiples entiers du diviseur entier x de k appartenant à D'_k }

Pour 12 , ca donnerait :
D'_k = { 1, 2, 3, 4, 6, 12 }

D_1 = {1, 2, 3, 4, 6, 12}
D_2 = {2, 4, 6, 12},
D_3 = {3, 6, 12},
D_4 = {4, 12},
D_6 = {6, 12},
D_12 = {12}

Si c'était des nuplets , cela ferait + le premier - tous les autres, y compris pour D_1 qui devient le total sans symétrie, ce qui nous rapproche du calcul des E(n,0).

Dans le cas circulaire , on peut faire un crible pour trouver indépendamment toutes les valeurs d'une ligne :

- générer toutes les possibilités linéaires ( une petite fonction réentrante )
- pour chacune mesurer la symétrie maximale ( couleurs identiques quand on avance du pas de la symétrie )
- multiplier le poids de chaque occurence par le facteur de symétrie , compter les k-settes , totaliser
- diviser les totaux par k n

C'est lourd mais si vous avez un second pc qui ne fait rien ...

Pour les MC, je fais pareil sauf que ca ne donne que du relatif à peine significatif pour E(n,0). Cependant, quand ce sera résolu, je proposerai une idée rigolote.


Désolé pour ces multiples erreurs mais j'en commets beaucoup ... je ne sais même pas si nous aurions trouvé k=2 sans vos indications

[mike.p]

Bonsoir,

je propose un résultat pour k=4 ( sous spoiler pour l'encombrement )

 Cliquez pour afficher

2 : 9, 0, 1, ( somme=10 , calcul=10 - total nuPlets=2 et nuPlets/total config=0.2 )
3 : 2709, 176, 9, 2, ( somme=2896 , calcul=2896 - total nuPlets=200 et nuPlets/total config=0.06906077348066299 )
4 : 3811752, 126378, 3366, 96, 6, ( somme=3941598 , calcul=3941598 - total nuPlets=133422 et nuPlets/total config=0.03384972287889328 )
5 : 14975446986, 297318756, 4192596, 58140, 930, 24, ( somme=15277017432 , calcul=15277017432 - total nuPlets=305882208 et nuPlets/total config=0.02002237736269672 )
6 : 133505885320812, 1756690404660, 15243280404, 119361804, 981000, 9360, 120, ( somme=135277939358160 , calcul=135277939358160 - total nuPlets=1787539022400 et nuPlets/total config=0.013213825039627019 )
7 : 2352017063188923400, 21981126066131664, 128992215758616, 645627402288, 3170969460, 16724880, 100800, 720, ( somme=2374127830286012000 , calcul=2374127830286011400 - total nuPlets=22241060147967840 et nuPlets/total config=0.009368097144663206 )
8 : 7.4182275743219276e+22, 517459233795792600000, 2189579420344328400, 7597950902705232, 24718042042992, 81883804320, 292831920, 1169280, 5040, ( somme=7.470193217918653e+22 , calcul=7.470193217918656e+22 - total nuPlets=521861285772541760000 et nuPlets/total config=0.006985914159767114 )

Il y a des différences entre les sommes de lignes issues de 2 calculs différents à partir de n=7 mais cela tient surement à la longueur des nombres. L'algorithme ne me convient pas mais j'y travaille encore

[Médiat]

Bonjour,

bravo pour votre implication, je vous avoue que je suis un peu pris en ce moment et je n'ai pas beaucoup de temps à y consacrer.

Bonne continuation

Médiat

[mike.p]

Bonjour,

l'énigme circulaire , malgré pas mal d'efforts, me résiste sur un point, le calcul de E(n,0) pour sa partie issue de E(n-1,0). Je sais le contourner en utilisant la somme de la ligne qui a l'air fiable mais du coup je n'ai plus de "preuve", c'est à dire ce second calcul censé corroborer le calcul itératif. J'ai même douté de tout, y compris de ce qui est validé, mais sans succès ...

Diagrammes de génération de E(n,0) pour sa partie issue de E(n-1,0) quand k n'est pas premier
circlenupleta1.png
avant , après, pour k=3, k=4 , k=6

circlenupleta2.png
zoom sur k=6, en gris les combinaisons sans symétrie, en rouge les k-settes à exclure, les autres couleurs sont des symétries.

circlenupleta3.png
k=12

Seuls rouge et gris restent à calculer à ce stade d'avancement.


Dans mon document de reddition, je tâcherai d'expliquer clairement où j'ai échoué , et donc ce qu'il faut trouver pour proposer une solution de l'énigme ( par 2 méthodes ). Mais je tenterai un dernier baroud ce soir

NB : l'algo utilisé pour les premiers a l'air solide. Celui produit pour les premiers² m'est totalement incompréhensible, à priori il est faux ( 2 bugs doivent se compenser mais lesquels ? ) . Quant aux autres, nada ...

[mike.p]

Bonjour,

toujours à propos du cas circulaire , j'ai trouvé des erreurs ! La proposition pour k=4 de mon message précédent était fausse ! la somme de ligne était juste mais il y avait des erreurs sur E(n,0) et E(n,1) ...

Voici ma proposition finale :

pour rappel, une confirmation pour k = 3 ( spoiler pour l'encombrement ou ceux qui cherchent ). Le ratio est le nombre de k-settes rapporté au nombre de combinaisons.

 Cliquez pour afficher

2 : 3, 0, 1, ( 4 , 4 et ratio =0.5 )
3 : 138, 42, 6, 2, ( 188 , 188 et ratio =0.3191489361702128 )
4 : 24850, 5256, 636, 56, 6, ( 30804 , 30804 et ratio =0.218153486560187 )
5 : 9520592, 1543320, 137760, 9040, 480, 24, ( 11211216 , 11211216 et ratio =0.1648349295919372 )

k=4

 Cliquez pour afficher

2 : 9, 0, 1, ( 10 , 10 et ratio =0.2 )
3 : 2699, 186, 9, 2, ( 2896 , 2896 et ratio =0.07251381215469613 )
4 : 3806664, 131376, 3456, 96, 6, ( 3941598 , 3941598 et ratio =0.03516340326943539 )
5 : 14966144958, 306490920, 4321560, 59040, 930, 24, ( 15277017432 , 15277017432 et ratio =0.020639827204721618 )

k = 6

 Cliquez pour afficher

2 : 79, 0, 1, ( 80 , 80 et ratio =0.025 )
3 : 950303, 2736, 15, 2, ( 953056 , 953056 et ratio =0.0029085384279622603 )
4 : 96129120466, 68469048, 71436, 200, 6, ( 96197661156 , 96197661156 et ratio =0.0007132454487509183 )
5 : 45684265131875430, 11537204308680, 3254065680, 1671840, 2400, 24, ( 45695805591924056 , 45695805591924056 et ratio =0.0002526209422450833 )

k = 8 ( un cube )

 Cliquez pour afficher

2 : 809, 0, 1, ( 810 , 810 et ratio =0.0024691358024691358 )
3 : 394359191, 38562, 21, 2, ( 394397776 , 394397776 et ratio =0.00009789608955604253 )
4 : 3111246280310904, 37859422656, 1311696, 336, 6, ( 3111284141045598 , 3111284141045598 et ratio =0.000012169266889033106 )
5 : 1.914173635257417e+23, 497800729614196860, 2366259825360, 39362640, 4830, 24, ( 1.914178613288376e+23 , 1.9141786132883758e+23 et ratio =0.000002600621795668131 )

k = 12

 Cliquez pour afficher

2 : 112719, 0, 1, ( 112720 , 112720 et ratio =0.0000177430801987225 )
3 : 94020319102769, 8112396, 33, 2, ( 94020327215200 , 94020327215200 et ratio =8.628419236865281e-8 )
4 : 4.912693766922426e+24, 13538926238840160, 405621252, 704, 6, ( 4.912693780461352e+24 , 4.912693780461352e+24 et ratio =2.755906973874801e-9 )
5 : 5.49969719429471e+36, 1.1790465048060117e+27, 1252350699401883600, 17576959640, 13530, 24, ( 5.499697195473757e+36 , 5.499697195473759e+36 et ratio =2.1438389522264367e-10 )

Je reviendrai dans la journée poser un lien vers le code et publier les équations, ce qui ne sera pas une mince affaire car il faudra décrire 2 multinomes et la descente sur les diviseurs de k ...

La proposition pour le linéaire suit sous peu, pour peu qu'il n'y ait pas une grosse erreur dans les calculs. En combinatoires, même avec un double calcul , tout est possible ( ex, k = 4 ).

[Médiat]

Bonjour,

Je reviendrai dans la journée poser un lien vers le code et publier les équations, ce qui ne sera pas une mince affaire car il faudra décrire 2 multinomes et la descente sur les diviseurs de k ...

J'attends avec impatience

[mike.p]

Proposition de solution pour le cas circulaire.

Ce n'est ni simplifié , ni optimisé. Les expressions sont assez distinguables pour ne pas être numérotées.

Découpé en plusieurs posts pour la longueur
1 - Rappel du calcul de la somme de la ligne
2 - Calcul de E(n,0)
3 - Description de la fonction multinomiale m() pour les suppressions de k-settes
4 - Calcul de E(n,p)
5 - Diverses justifications et petites démo de validité des fonctions de génération à n+1

1 et 2 :

= { des diviseurs entiers de k , 1 et k inclus }

et dans le contexte fixe de k ,<br> { des multiples entiers du diviseur entier x de k appartenant à }

= { les q diviseurs entiers de k sauf 1 }<br> = { les q diviseurs entiers de k }

la diversité linéaire

la diversité linéaire de seule symétrie q sans celles de ses diviseurs :



Total de la ligne d'ordre n pour le cas k =

On relève les totaux des symétrie à n et à n-1 , linéaires et circulaires, utiles plus loin ( Lin comme linéaire et m1 comme moins 1 )









<br>

et l'expression du total de la ligne d'ordre n dans le cas k










L'expression de la fonction multinomiale m(p,q) est détaillée plus loin.

[mike.p]

Ca va être une vraie galère de passer de mathjax à tex et de cadrer. Je me suis trompé en découpant l'expression de E(n,0) trop longue, l'indice q n'est plus à la bonne place.
Bon, il a fallu 5 semaines et 13 pages, autant prendre une heure de plus ... Désolé pour l'auto pollution ...

[Médiat]

Bonjour,

Vous auriez un meilleur résultat en créant votre pdf avec un compilateur latex

[mike.p]

(suite )
la voici réarrangée pour cadrer :







fonction multinome m()

définissons les ensembles
= { ensemble des v-plets d'entiers A dont la somme vaut u }

et la function qui rend le nombre d'occurences des répétitions dans un v-plet de ces ensembles,

et , le composant d'indice i du v-plet A

formule stars and bars standard :


( implémentation sans prétention en javascript installée sur une page d'un site abandonné )

( @ Mediat : je viens de lire votre message. Mon éditeur de pdf Libreoffice utilise mathjax mais c'est surtout un problème de recadrage ici )

[mike.p]

(suite)










si p = 1


sinon


Ce calcul est très différent du calcul de la somme de la ligne bien qu'il partage avec certains éléments.

Voilà, c'est tout.

L'algorithme a recours a des partitions qu'il peut faire évoluer de n à n+1. Comme la couleur ajoutée ne peut pas rapprocher 2 chaussettes et que toutes les configurations précédentes étaient distinctes et appartenaient à des sous-ensembles disjoints, il n'y a pas de croisements et de génération en double. Je les ai toutes scrutées. S'il y en a une qui pose problème, je me suis préparé à en discuter, même plus formellement. En fait, c'est simple mais important pour ne pas faire de génération incontrôlable.

Le problème des symétries exposées dans les images précédemment était de fait résolu mais un bug ailleurs faisait douter de tout. On n'a pas à se préoccuper des découpages des symétries par source car nous en savons les totaux et seuls eux comptent dans le dénombrement.

Il y avait 2 autres écueils dans la généralisation.

Le cas particulier de n=1 où les symétries sont totales et n'appartiennent pas à la colonne des sans k-settes ! en effet, une k-sette seule porte toutes les symétries possibles de k. L'algo suppose que les symétries sont systématiquement sans k-sette. Bon, c'est de l'ajustement. Si on veut être méticuleux, il faut distinguer le cas. Sinon, on peut exceptionnellement calculer E(2,0) comme le total de 2 moins 1 ( puisque E(1,0)=0 et E(1,1)=1 quel que soit k ).

L'étonnante complexité de la suppression de k-settes dans les colonnes en comportant trop au départ. Je n'ai pas trouvé d'expression plus simple ( elle doit surement exister ) du multinome. Le nombre de chaussettes utilisées pour killer les k-settes en trop peut varier et le nombre de k-settes en trop varie de colonne en colonne. Au niveau le plus bas, on applique la solution standard du problème stars and bars ( wiki en parle bien ). Mais je ne vois pas de formule synthétique faisant l'impasse du crible basé sur les décompositions additives du nombre de chaussettes killers.

Enfin le petit programme ayant servi à la mise au point utilise une petite classe sur les quotients d'entiers ( sans prétention ) pour retarder le moment des multiplications et divisions finales. C'est en général peu performant pour les additions car il faut à chaque fois refaire une décomposition en premiers du résultat. Si par malheur l'élément intermédiaire est très gros pour une factorisation, les calculs peuvent devenir sinon complètement faux, pas du tout optimaux. A toutes fins utiles, le programme emporte une table avec tous les premiers de 2 à presque 100.000. J'aurais préféré utiliser une librairie au point mais elle aurait eu l'inconvénient de nécessiter une installation alors que là, il est facile de sauver le fichier indépendant sur le disque dur et de modifier l'algorithme pour l'améliorer ou aborder un problème très proche.

[Médiat]

Bonjur,

Je suis ce que vous faites, mais je suis gêné par quelques points

1) le vocabulaire (ce que vous appelez "diversité linéaire" est plutôt le "nombre de configurations linéaire de période q", ou peut-être ai-je mal compris)
2) certaines notations, comme des D et D' (D_k et D_x ne semble pas être la même chose)
3) des sommations sur une variable qui n'est pas dans la somme (les T)
4) l'utilisation d'objets complexes ("ensemble des v-plets d'entiers A dont la somme vaut u" ou "le nombre d'occurrences des répétitions dans un v-plet de ces ensembles"

Et, bien sûr, en tant que mathématicien, il me manque des démonstrations ()

En tout état de cause :

[mike.p]

Bonjour Mediat ,

1 ) J'ai fait de "diversité" un raccourci cool pour "dénombrement des configurations possibles" dans un contexte donné. De plus comme vous le remarquez, linéaire et circulaire sont parfois implicites, ce qui n'aide pas vraiment ... Non, la diversité n'est pas nécessairement linéaire, c'est une précision manquante.

2 ) un point à revoir ; en effet , à aller trop vite ( vantardise !!! ) pour montrer que c'était peut-être trouvé résultat, ce n'est pas toujours clair. En fait, le tout en une égalité est peut être une complication inutile qui explique mal la construction.

3 ) T(k,n,i) ? k et n sont contextuels, i est l'indice , T est une fonction définie plus haut.

4 ) Il fallait éviter l'algo de leur production mais à trop réduire , il manque un pas. Je voulais exprimer: constituons la liste de v-plets ayant telles caractéristiques et appliquons à travers leurs composants, les calculs qui suivent ...


Pour les démos, voulez vous dire l'explication du pourquoi de chaque élément des expressions ou bien une méthode de validation supplémentaire ? La formulation que je prépare, plus proche de l'algo utilisé, devrait faciliter la première option. Peut être dans un pdf pour ne pas encombrer ... J'ai par le passé publié des calculs pour le fun qui se sont perdus dans les liens morts sans aucun lecteur connu ( genre le pb de Steiner ), ça fait hésiter. Demain je publierai une formule du circulaire qui permettra la discussion de sa validité.

A propos du cas linéaire. Il semble que l'algo de partionnement par symétrie pourrait donner ici les résultats directement sans génération depuis n-1 , en prenant comme critère de découpage, "possède au moins p ksettes". Ensuite, on déduit ce qui est inclus pour retrouver les "possède exactement p ksettes". Pour cela, on suppose que les symétries sont sans effet particulier dans le linéaire et bien entendu que n éléments offrent n+1 points d'insertion au lieu des n du circulaire. Trop facile, il doit y avoir un bug ...

Amis joueurs, si vous cherchez la solution de votre côté, n'arrêtez surtout pas. Il y a surement plus simple et plus élégant. Et puis, venez partager vos trouvailles

[Médiat]

3 ) T(k,n,i) ? k et n sont contextuels, i est l'indice , T est une fonction définie plus haut.

Justement, dans le message 193 i n'apparaît pas.

A propos du cas linéaire.

Pour moi ce cas est résolu, vous n'êtes pas d'accord ?

[mike.p]

bien vu ! l'indice est q ! merci !!
mais ce message #193 était très malheureux. E(n,0) y est complètement faux.

Pour moi ce cas est résolu, vous n'êtes pas d'accord ?

Oui mais par vous je n'ai pas encore été télécharger le pdf pour lire la solution ! c'était prévu après au moins une proposition ...

[mike.p]

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.

Pièce jointe 311575

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

Bonsoir Mediat,

Une explication bien claire, un modèle de réponse. J'ai compris ce que vous attendez ! j'étais dans le registre énigme effort minimum résultat maximum ... Ok, c'est entendu. Je devrais aussi afficher les résultats sous forme numérique longue ( 256 chiffres significatifs , à faire ) ou sous forme de facteurs ( déjà possible ).