Petit problème agaçant de combinatoire.

[Cauchy2010]

j'ai décidé de ne plus fréquenter ce forum.
A ciao, bonsoir !

[CBMaths_prof]

Bonjour Cauchy,

Est-ce que tu peux développer ton exemple ? Ca a l'air intéressant mais je n'ai pas très bien compris de ce qu'il en retourne.

[Cauchy2010]

Bonjour Cauchy,

Est-ce que tu peux développer ton exemple ? Ca a l'air intéressant mais je n'ai pas très bien compris de ce qu'il en retourne.

Salut,
tu prends les entiers compris entre 1 et 12.
Il existe 792 5-combinaisons.
IL existe 220 3-combinaisons.

Quel est le plus petit nombre de 5-combinaisons à choisir permettant de retrouver toutes les 220 3-combinaisons ?

[CBMaths_prof]

Les combinaisons sont ordonnées ou peu importe ?

C'est-à-dire "est-ce que (1,2,3,4,5) est équivalent à (5,4,3,2,1) ?"

Et est-ce qu'on a le droit au répétition (1,2,1,3,1) ?

[Cauchy2010]

Les combinaisons sont ordonnées ou peu importe ?

C'est-à-dire "est-ce que (1,2,3,4,5) est équivalent à (5,4,3,2,1) ?"

Et est-ce qu'on a le droit au répétition (1,2,1,3,1) ?

Peu importe ! Mais comme c''est une combinaison, il n'y a pas de répétition.

[Cauchy2010]

Un premier résultat aurait donné 32, mais ...

[Mario2015]

29 est possible.
Jette un coup d`oeil ici

http://www.ccrwest.org/cover/t_pages/t3/k5/C_12_5_3.html

Il y a plusieurs methodes pour y arriver.

[Cauchy2010]

29 est possible.
Jette un coup d`oeil ici

http://www.ccrwest.org/cover/t_pages/t3/k5/C_12_5_3.html

Il y a plusieurs methodes pour y arriver.

OK, merci, mais comment fait-on ?

[Mario2015]

OK, merci, mais comment fait-on ?

Si tu lis l`anglais tu peux retrouver toutes les methodes en les cherchant sur google.
La reference que je t`ai donne signale les methodes utilisees devant chaque liste avec le nom du createur de la liste. La methode utilisee pour retrouver les 29 : "simulated annealing covering system". Il y en a 6 ou 7 je crois.
Tape covering system sur google.

[Mario2015]

Les tables de la Jolla ne sont pas forcement les meilleures.

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

On peut trouver mieux que 29 bien sur. Si tu trouves mieux tu peux les envoyer au site La Jolla qui les publiera avec ton nom et ta methode.

[Cauchy2010]

Les tables de la Jolla ne sont pas forcement les meilleures.

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

On peut trouver mieux que 29 bien sur. Si tu trouves mieux tu peux les envoyer au site La Jolla qui les publiera avec ton nom et ta methode.

Justement, je veux comprendre la conception intellectuelle de la méthode !

[Mario2015]

Justement, je veux comprendre la conception intellectuelle de la méthode !

Il y en a pusieurs (y a meme des methodes geometriques) et rien ne t`empeche d`en inventer une nouvelle plus efficace.
Le domaine vu sa complexite est ouvert.

[Cauchy2010]

Il y en a pusieurs (y a meme des methodes geometriques) et rien ne t`empeche d`en inventer une nouvelle plus efficace.
Le domaine vu sa complexite est ouvert.

Les connais-tu ?

[Mario2015]

Les connais-tu ?

Je connais leur existence (certaines utilisent la theorie des graphes, la geometrie 2D, etc...). Pour les avoir toutes c`est impossible car chaque chercheur peut en une sienne. Il suffit de lire les listes de La Jolla et les denombrer.
Moi, ma methode je l`ai developpee sur des n<20 car je le fais en utilisant stylo et papier + tests sur Excel.
Je ne suis pas programmeur malheureusement. Autrement, je serai alle plus vite en introduisant le concept d`algorithme interactif ou le manipulateur introduit des donnees au fur et a mesure et l`ordi fait le travail demande. Ce concept est la meilleure solution pour solutionner des problemes complexes comme le voyageur de commerce par exemple (je reussis 50 villes en 10 minutes).

[Mario2015]

Ici tu en as une par exemple lex cover basee sur la theorie des graphes :

http://homepages.cwi.nl/~lex/files/agt1.pdf

[Mario2015]

Ici tu as un programme pour les covering designs :

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

[Cauchy2010]

OK, merci !

[nodjim]

Ce qui est sûr, c'est qu'on ne peut pas faire mieux que 22, c'est 220/10 (car il y a 10 triplets dans un quintuplet).

[Cauchy2010]

Ce qui est sûr, c'est qu'on ne peut pas faire mieux que 22, c'est 220/10 (car il y a 10 triplets dans un quintuplet).

Merci de cette information, mais en effet, c'est le premier calcul qu'on fait tous :lol3:
Je reste quand même sur ma faim, j'aimerais bien trouver un raisonnement mathématique pour y arriver ! :mur:

[Mario2015]

Ce qui est sûr, c'est qu'on ne peut pas faire mieux que 22, c'est 220/10 (car il y a 10 triplets dans un quintuplet).

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.