Petit problème agaçant de combinatoire.

[fatal_error]

voir http://www.maths-forum.com/showthread.php?t=156862&page=3&highlight=maximum+clique

en particulier, https://ia601009.us.archive.org/22/items/arxiv-1109.5717/1109.5717.pdf (de 2006, dls-mc, il y a un code source github mais jle retrouve plus)

plus récémment, bitscan de pablo (que j'ai pas encore testé) (source code at biicode)

[Mario2015]

On peut arriver a moins de 29 puisque la barre theorique est a 22.
Je le prouverai en publiant mes combinaisons.
A bientot donc.

[Mario2015]

Le problème est que c'est une méthode "manuelle", sans logique sous-jacente et donc, non généralisable.
J'avais posé la question il y a quelque années à un brillant ENS Cachan, agrégé, informaticien en activité dans le privé, qui avait conclu que c'était un sujet dont la principale complication était de s'assurer de la minimalité de la solution.
Un autre brillant informaticien (en retraite) avait conçu une solution codée sous python que je peux poster, il pensait avoir trouvé le minimum minimorum (32 quintuplets) jusqu'au jour où il est "tombé" sur la solution avec 29 seulement publiée sur la toile. Il n'a pas encore compris comment le gars avait fait.
A l'analyse de son pgm, je m'étais aperçu que la solution dépendait du choix de la première grille.
D'où ma quête.
Et merci à Mario pour ses réponses.
Ma vraie question n'est pas tant de savoir comment faire pour sélectionner les bonnes grilles que de trouver la bonne technique pour dénombrer le nombre minimum de grilles satisfaisant la contrainte.
L'esprit reste encore supérieur à l'informatique.

On peut connaitre le nombre minimal de grilles par bornage successif (voir sur le forum les discussions anterieures).
La methode utilisee pour trouver 29 est "simulated annealing covering system"
http://www.ccrwest.org/cover/t_pages/t3/k5/C_12_5_3.html
On peut faire mieux que 29.
Pour (17,5,3) il n`y a pas de perte (Steiner system). Une perte de 7 sur 29 c`est enorme!

[Cauchy2010]

On peut arriver a moins de 29 puisque la barre theorique est a 22.
Je le prouverai en publiant mes combinaisons.
A bientot donc.

Pas théorique, seulement arithmétique au sens où tu divises 220 par 10, ce qui ne constitue en rien LA preuve indiscutable.
Je ne sais pas si je vivrais assez longtemps pour voir tes grilles.
Bon courage et reste modeste, ce qui n'est pas incompatible avec l'ambition ni le désir d'être meilleur parmi les meilleurs. Il y a encore des questions qui nous dominent, malgré les brillants esprits qui les ont examinées.
Deux exemples très populaires : la conjecture de Syracuse, la conjecture de Golbach.

[Mario2015]

Pas théorique, seulement arithmétique au sens où tu divises 220 par 10, ce qui ne constitue en rien LA preuve indiscutable.
Je ne sais pas si je vivrais assez longtemps pour voir tes grilles.
Bon courage et reste modeste, ce qui n'est pas incompatible avec l'ambition ni le désir d'être meilleur parmi les meilleurs. Il y a encore des questions qui nous dominent, malgré les brillants esprits qui les ont examinées.
Deux exemples très populaires : la conjecture de Syracuse, la conjecture de Golbach.

Les systemes Steiner atteignent cette barre theorique.
La liste se trouve sur La Jolla.

[Cauchy2010]

t'as le lien ?

[Mario2015]

http://www.ccrwest.org/cover/steiner.html

Si tu veux plus d`info sur le systeme Steiner google-le. Il y a pas mal de donnees et d`articles en anglais a ce sujet.

[Mario2015]

Bizarrement les idees pleuvent aujourd`hui!
Je suis tres optimiste et je pense que l`on peut trouver une solution definitive a ce probleme.
Je reviendrai bientot.

[Mario2015]

J`en suis a 5 algos pour resoudre ce foutu probleme.
Je finirai bien par trouver la solution.
Je pars me reposer dans un "cottage".
A la revoyure donc!

[Cauchy2010]

Comme le client pénible dans la série "Palace" à propos du directeur : "Je l'aurai, un jour, je l'aurai" !
Have fun !

[Ben314]

On peut arriver a moins de 29 puisque la barre theorique est a 22.
Je le prouverai en publiant mes combinaisons.
A bientot donc.

22 c'est clairement pas faisable vu qu'il faudrait que chaque triplet apparaissent dans un et un seul quintuplet.
Or, il y a 10 triplets de la forme (1,2,x) et les quintuplets (1,2,a,b,c) en "continent" 3 chacun. Comme 10 n'est pas divisible par 3, c'est foutu.

[nodjim]

J'avais vu ça. C'est sans doute la raison pour laquelle on sait faire un (3,5,17) optimal et pas un (3,5,12). Cela dit, 29 pour 22, ça semble améliorable.

[Cauchy2010]

22 c'est clairement pas faisable vu qu'il faudrait que chaque triplet apparaissent dans un et un seul quintuplet.
Or, il y a 10 triplets de la forme (1,2,x) et les quintuplets (1,2,a,b,c) en "continent" 3 chacun. Comme 10 n'est pas divisible par 3, c'est foutu.

Ite Missa est :++:

[Mario2015]

En fait, ce probleme n`est pas aussi agacant qu`il n`y parait.
Hormis enfoncer les portes ouvertes, rien de nouveau.
Peut-on prouver que 29 est le nombre de combinaisons incompressible pour n=12 couvrant tous les triplets?
28 ou 27 voire moins serait-ce un exploit?

[Mario2015]

Question subsidiaire : quel est le maximum de triplets que peuvent couvrir 22 quintuplets?
Il y en a 220 a couvrir au total.

[Mario2015]

He Cauchy2010,

On dirait que ce probleme ne t`agace plus.
Je viens de decouvrir un probleme de combinatoire fascinant.
J`y travaille.
A bientot.

[Cauchy2010]

He Cauchy2010,

On dirait que ce probleme ne t`agace plus.
Je viens de decouvrir un probleme de combinatoire fascinant.
J`y travaille.
A bientot.

ce n'est pas toi qui devait nous annoncer une bonne nouvelle ? :ptdr:

[Mario2015]

ce n'est pas toi qui devait nous annoncer une bonne nouvelle ? :ptdr:

Je te rappelle que sur cette question tu n`as rien apporte comme contribution hormis des infos que tout le monde connait ou des affirmations gratuites.
Relis-toi.
Bref, je continue ma route moi.
Plus je trouve de solutions plus je me dirige vers d`autres pistes.
J`en suis a mon 6eme algorithme pour solutionner ce probleme en particulier.
J`ai presque resolu le nombre optimal de combinaisons couvrant les k-uplets.
Je suis re-malade (O vieillesse ennemie!).

[Cauchy2010]

Je te rappelle que sur cette question tu n`as rien apporte comme contribution hormis des infos que tout le monde connait ou des affirmations gratuites.
Relis-toi.
Bref, je continue ma route moi.
Plus je trouve de solutions plus je me dirige vers d`autres pistes.
J`en suis a mon 6eme algorithme pour solutionner ce probleme en particulier.
J`ai presque resolu le nombre optimal de combinaisons couvrant les k-uplets.
Je suis re-malade (O vieillesse ennemie!).

Puis je te rappeler que dans ce sujet, c'est moi qui suis le demandeur, pas celui qui réponds à ses propres questions ? :zen:
Tu as quel âge ? A lire tes posts, j'avoue te donner (non, prêter,c'est plus juste) 20 ans au maximum :ptdr:

[Mario2015]

Puis je te rappeler que dans ce sujet, c'est moi qui suis le demandeur, pas celui qui réponds à ses propres questions ? :zen:
Tu as quel âge ? A lire tes posts, j'avoue te donner (non, prêter,c'est plus juste) 20 ans au maximum :ptdr:

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.