Petit problème agaçant de combinatoire.

Olympiades mathématiques, énigmes et défis
Cauchy2010
Membre Relatif
Messages: 141
Enregistré le: 18 Juil 2015, 22:23

par Cauchy2010 » 25 Aoû 2015, 15:35

Mario2015 a écrit:Tu as eu suffisamment d`infos venant de ma part pour te construire une idee.
Or avec tout cela tu n`as pas contribue d`un iota a ta question!
Quant a mon age, cela importe peu.
Bonne chance dans tes recherches.
Moi, je me barre.
Je voulais envoyer un de mes 6 algos mais la tu ne me donne plus envie de le faire.
Demerde-toi si tu estimes avoir l`age de la debrouillardise.

Tu maîtrises l'art de l'esquive, c'est déjà une bonne chose, sur un sujet assez velu à propos duquel j'étais venu chercher des réponses, pas des liens HTML inutiles pour la plupart ! :++:
So long, mon pote ! :happy2:



Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 14:46

par Mario2015 » 25 Aoû 2015, 17:04

Et l`ingratitude en bonus!
Merci!
Des liens inutiles!!!???
Ah! bon?
J`ai fourni 2 algos en plus de ces liens.
Un algo manuel que j`utilise pour des n petits
Plus un algo programmable.
Et le vieux recoit des quasi-insultes!
Je retourne a mes veaux, vaches, cochons, etc....!

Cauchy2010
Membre Relatif
Messages: 141
Enregistré le: 18 Juil 2015, 22:23

par Cauchy2010 » 25 Aoû 2015, 17:22

Mario2015 a écrit:Et l`ingratitude en bonus!
Merci!
Des liens inutiles!!!???
Ah! bon?
J`ai fourni 2 algos en plus de ces liens.
Un algo manuel que j`utilise pour des n petits
Plus un algo programmable.
Et le vieux recoit des quasi-insultes!
Je retourne a mes veaux, vaches, cochons, etc....!

Suis sûrement plus vieux que toi ! Tu étais sur les barricades, en 1968 ?
Pas vu tes algos, mon pote ! Sont où ?

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 14:46

par Mario2015 » 25 Aoû 2015, 17:38

Mario2015 a écrit:Ma methode part de cette limite de 22.
22 combinaisons de 5 = 110 numeros
Comme il y en a 12 donc 110/12=9,16.
Mettons que je vais utiliser entre 9 fois et 10 fois chacun de mes nombres de 1 a 12.
J`inscris tous mes numeros en 10 exemplaires sur mon papier et je commence mon "sudoku".
Chaque fois j`utilise un nombre je le barre.
Je dessine un tableau de 22 lignes et 5 colonnes.
Et je commence a placer mes nuumeros sur mon tableau.
A cote sur excel j`ai ma liste de triplets.
Avec un programme graphique ce serait plus simple.
Chaque fois que je compose un quintuplet, je l`entre comme input le programme se chargera d`eliminer les triplets. Avec une possibilite de "reset".
Bref, je fais toute cette cuisine avec un stylo un papier + Excel.
C`est long laborieux mais l`aide d`un programme interactif ce serait plus amusant.
Mieux, on peut donner ce programme a 100 personnes, forcement certains trouveront peut-etre moins que 29.

En voila un! Le manuel

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 14:46

par Mario2015 » 25 Aoû 2015, 17:40

Mario2015 a écrit:Je pense avoir trouve un principe de solution.
Pour n=12 il y a 792 quintuplets
On a besoin de 22 quintuplets pour couvrir les 220 triplets.
L`idee est la suivante et elle peut etre programmee.
Si on partitionne au hasard l`ensemble des 792 quintuplets en sous-ensembles de 22 quintuplets. Il y en aurait 36 (36*22=792).
Chaque sous-ensemble de 22 quintuplets couvrirait un certain de nombre de triplets (certains seront absents d`autres seront dupliques). D`ou l`idee de faire des substitutions de quintuplets d`un sous-ensemble a un autre de telle sorte que les triplets soient uniformement couverts. L`ideal est d`aboutir a une repartition uniforme : chaque sous-ensemble de 22 couvrirait tous les 220 triplets. L`optimum serait une distribution avec le plus faible ecart-type. On aurait ainsi parmi ces 36 sous-ensemble, un sous-ensemble de 22 qui couvre le maximum de triplets comme point de depart.
Cela dit il y a un certain nombre de problemes a resoudre pour eviter les cycles lors des substitutions.


En voila un autre !!!

Les 5 autres algos (je ne compte pas le "manuel") je les garde pour moi.

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 14:46

par Mario2015 » 25 Aoû 2015, 17:45

Cela dit bonne chance dans tes recherches.
I`m fed up!

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 14:46

par Mario2015 » 25 Aoû 2015, 18:56

Mario2015 a écrit:Je pense avoir trouve un principe de solution.
Pour n=12 il y a 792 quintuplets
On a besoin de 22 quintuplets pour couvrir les 220 triplets.
L`idee est la suivante et elle peut etre programmee.
Si on partitionne au hasard l`ensemble des 792 quintuplets en sous-ensembles de 22 quintuplets. Il y en aurait 36 (36*22=792).
Chaque sous-ensemble de 22 quintuplets couvrirait un certain de nombre de triplets (certains seront absents d`autres seront dupliques). D`ou l`idee de faire des substitutions de quintuplets d`un sous-ensemble a un autre de telle sorte que les triplets soient uniformement couverts. L`ideal est d`aboutir a une repartition uniforme : chaque sous-ensemble de 22 couvrirait tous les 220 triplets. L`optimum serait une distribution avec le plus faible ecart-type. On aurait ainsi parmi ces 36 sous-ensemble, un sous-ensemble de 22 qui couvre le maximum de triplets comme point de depart.
Cela dit il y a un certain nombre de problemes a resoudre pour eviter les cycles lors des substitutions.


Cet algorithme repondrait, tres certainement, a l`une de mes questions :
quel est le nombre maximal de triplets couverts par 22 quintuplets?
Partant de cette valeur, il y a moyen d`aboutir a une valeur incompressible k (22<k<=29)

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 14:46

par Mario2015 » 28 Aoû 2015, 16:29

A celles et ceux qui veulent faire travailler leurs neurones "programmatiques" je livre un algorithme sympathique et sur.
On a 792 quintuplets pour n=12.
On les liste et on les numerote de 1 a 792.
On prend le premier quintuplet 1 et on cherche les quintuplets qui peuvent y etre associes sans qu`un triplet soit duplique. Il y en a 792-246=546.
On les associe a 1.
On aurait le nombre 1 avec sa liste de "compatibles".
On choisit parmi les 756 un quintuplet quelconque. Et on cherche parmi les 546 restants les quintuplets qui s`y associent dans duplication de triplets.
On aurait donc a ce niveau 3 quintuplets sans duplication.
On continue a grossir notre sous-ensemble jusqu`a epuisement (aucun de la liste restante n`est compatible.
Une fois que l`on obtient ce premier sous-ensemble. On raye ses elements (quintuplets de la liste des 792 quintuplets.
Et on refait la meme procedure jusqu`a partitionner l`ensemble des 792 quintuplets.
Ce qui est certain c`est que l`on aurait le maximum de triplets pouvant etre couverts par un certain nombre de quintuplets k.
k nous indique a coup sur le meilleur taux de couverture des 220 triplets.
A partir de la on procede a un ajout exhaustif des quintuplets un a un (je parle des combinaisons restantes) en verifiant la meilleure couverture possible.
Au bout du compte on aurait le maximum incompressible (29 peut-etre ou moins).
A vos codes!

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : catamat et 12 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite