Petit problème agaçant de combinatoire.

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

Petit problème agaçant de combinatoire.

par Cauchy2010 » 13 Aoû 2015, 11:06

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



Avatar de l’utilisateur
CBMaths_prof
Membre Naturel
Messages: 66
Enregistré le: 01 Juil 2015, 20:37
Localisation: Nord (59)

par CBMaths_prof » 13 Aoû 2015, 13:05

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.
Image

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

par Cauchy2010 » 13 Aoû 2015, 13:57

CBMaths_prof a écrit: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 ?

Avatar de l’utilisateur
CBMaths_prof
Membre Naturel
Messages: 66
Enregistré le: 01 Juil 2015, 20:37
Localisation: Nord (59)

par CBMaths_prof » 13 Aoû 2015, 14:06

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) ?
Image

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

par Cauchy2010 » 13 Aoû 2015, 14:08

CBMaths_prof a écrit: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
Membre Relatif
Messages: 141
Enregistré le: 18 Juil 2015, 23:23

par Cauchy2010 » 13 Aoû 2015, 14:19

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

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

par Mario2015 » 13 Aoû 2015, 15:02

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
Membre Relatif
Messages: 141
Enregistré le: 18 Juil 2015, 23:23

par Cauchy2010 » 13 Aoû 2015, 15:19

Mario2015 a écrit: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
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 13 Aoû 2015, 15:39

Cauchy2010 a écrit: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
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 13 Aoû 2015, 15:45

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
Membre Relatif
Messages: 141
Enregistré le: 18 Juil 2015, 23:23

par Cauchy2010 » 13 Aoû 2015, 15:49

Mario2015 a écrit: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
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 13 Aoû 2015, 15:54

Cauchy2010 a écrit: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
Membre Relatif
Messages: 141
Enregistré le: 18 Juil 2015, 23:23

par Cauchy2010 » 13 Aoû 2015, 18:36

Mario2015 a écrit: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
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 13 Aoû 2015, 18:48

Cauchy2010 a écrit: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
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 13 Aoû 2015, 18:50

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

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

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

par Mario2015 » 13 Aoû 2015, 18:53

Ici tu as un programme pour les covering designs :

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

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

par Cauchy2010 » 13 Aoû 2015, 19:14

OK, merci !

nodjim
Membre Complexe
Messages: 3241
Enregistré le: 24 Avr 2009, 18:35

par nodjim » 14 Aoû 2015, 09:11

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
Membre Relatif
Messages: 141
Enregistré le: 18 Juil 2015, 23:23

par Cauchy2010 » 14 Aoû 2015, 12:51

nodjim a écrit: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
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 14 Aoû 2015, 16:22

nodjim a écrit: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.

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 5 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