Probleme de combinatoire tres dur!

[Mario2015]

On tire au hasard 10.000 combinaisons de 5 parmi 50 comme a l`Euromillions.
On cherche parmi ces 10.000 quintuplets le plus grand nombre de quintuplets ayant EXACTEMENT 2 nombres en commun 2 a 2. On note ce nombre X.
On repete l`operation un grand nombre de fois (mettons 100.000 fois).
Quelle est la valeur moyenne de X ?

Merci.

[zygomatique]

salut

quintuplets ayant EXACTEMENT 2 nombres en commun 2 a 2

pas clair ... donne un exemple

[Mario2015]

salut



pas clair ... donne un exemple

1-2-3-4-5
1-2-7-8-9
1-2-10-11-12

Ces 3 combinaisons ont exactement 2 nombres en commun si on les prend 2 a 2

1-2-3-4-5 et 1-2-7-8-9
1-2-3-4-5 et 1-2-10-11-12
1-2-7-8-9 et 1-2-10-11-12

Ceci n`est qu`un exemple reduit a 3 combinaisons.

[Ben314]

Perso, j'ai pas compris non plus et l'exemple donné m'éclaire peu. En particulier, dans l'exemple, tu parle de "les prendre deux à deux" alors que dans l'énoncé original tu parle "du plud grand nombre de quintuplet tels que" donc,
- Ton X, c'est le nombre de quintuplet tels que... ou bien le nombre de couples de quintuplets tels que ... ?
- J'aurais tendance à considérer que ce qui t'intéresse, c'est le nombre de couples (ou de paires) de quintuplets tels que les deux quintuplets du couple ait exactement deux élément communs, mais cette interprétation ne colle pas du tout avec le mot "maximum" qu'il y a dans la phrase et qui dans ce cas ne veut rien dire.

[Mario2015]

Voila le probleme :
On tire 10.000 quintuplets.
Il s`agit d`extraire un sous-ensemble de quintuplets qui, pris 2 a 2, ont exactement 2 numeros en commun. Bien sur que l`on peut trouver au moins 2 quintuplets ayant 2 nombres en commun. On peut en trouver 3 et plus. Il y a un maximum que l`on ne peut pas depasser. D`ou la complexite du probleme. Supposons que ce sous-ensemble soit de 100 combinaisons. Sur les 10.000 -100=9900 restantes si l`on prend n`importe laquelle elle aurait 0,1,3,4 numeros en commun avec l`une de nos 100 combinaisons mais pas 2. On est suppose avoir atteint le maximum.

[Mario2015]

Je dois solutionner ce probleme de maniere definitive.
Cela fait plusieurs mois que j`avais propose le probleme.
Fatal_Error le modo avait apporte sa contribution et je l`en remercie.
Si j`arrive a avoir en temps raisonnable une solution ou un algorithme efficace pour un certain nombre de combinaisons engendrees au hasard (aux alentours de 1.500.000), je pourrai solutionner le probleme de ma vie. Je creerai une entreprise rien que pour cela si je suis certain que la solution a le merite d`exister d`abord et d`etre a ma portee en un temps raisonnable (une semaine de travail ordi).

[Mario2015]

Je relance ma question en anglais :

3-5-7-8-9
1-2-3-4-5
1-2-6-7-8
1-3-6-9-10
2-4-7-9-10
4-5-6-8-10

All the 6 quintuplets share exactly 2 numbers pairwise.
6 is the maximal number of quintuplets with the condition above you could extract from C(10,5)=252.
You can not find more than 6.

Now assume that instead of 10 numbers we try with 25 numbers. So C(25,5)=53130.
What is the maximal number of quintuplets such as they share exactly 2 numbers pairwise?

How to solve this challenge?

Merci

[Ben314]

Juste un mot pour préciser que, en tout cas pour moi, l'énoncé est maintenant clair, mais que je sais pas du tout par quel bout le prendre au niveau mathématique.
Déjà, rien qu'avec un "lot" de 10.000 combinaisons connues, je sais pas trop par quel bout il faudrait s'y prendre pour trouver le plus gros sous-ensemble tel que 2 quelconque des combinaisons de ce sous ensemble aient exactement deux éléments communs. Si on regarde ça comme un graphe où les sommet sont les 10.000 combinaisons et on met une arrêtes entre deux combinaisons lorsqu'elles ont 2 éléments communs, ça correspond a chercher le plus gros sous-graphe complet contenu dans le graphe de départ et ça évoque rien pour moi, mais vu le coté "classique" du problème, ça risque d'évoquer quelque chose a quelqu'un qui y connaitrait quelque chose en graphes...
En bref, je réfléchi (vaguement) a la question, mais sans aucune garantie concernant un éventuel début de piste...

P.S. Si, il y a quand même un truc toujours pas clair : dans la version de départ (français), tu demandais la valeur moyenne du truc quand on prenait 10.000 combinaisons parmi les C(50,5) possibles alors que dans la version anglaise, tu demande la valeur maximale du même truc quand on prend toutes les combinaisons possibles : ce n'est évidement pas du tout le même problème. Donc, c'est quoi qui t'intéresse en fait ?

[Mario2015]

Juste un mot pour préciser que, en tout cas pour moi, l'énoncé est maintenant clair, mais que je sais pas du tout par quel bout le prendre au niveau mathématique.
Déjà, rien qu'avec un "lot" de 10.000 combinaisons connues, je sais pas trop par quel bout il faudrait s'y prendre pour trouver le plus gros sous-ensemble tel que 2 quelconque des combinaisons de ce sous ensemble aient exactement deux éléments communs. Si on regarde ça comme un graphe où les sommet sont les 10.000 combinaisons et on met une arrêtes entre deux combinaisons lorsqu'elles ont 2 éléments communs, ça correspond a chercher le plus gros sous-graphe complet contenu dans le graphe de départ et ça évoque rien pour moi, mais vu le coté "classique" du problème, ça risque d'évoquer quelque chose a quelqu'un qui y connaitrait quelque chose en graphes...
En bref, je réfléchi (vaguement) a la question, mais sans aucune garantie concernant un éventuel début de piste...

P.S. Si, il y a quand même un truc toujours pas clair : dans la version de départ (français), tu demandais la valeur moyenne du truc quand on prenait 10.000 combinaisons parmi les C(50,5) possibles alors que dans la version anglaise, tu demande la valeur maximale du même truc quand on prend toutes les combinaisons possibles : ce n'est évidement pas du tout le même problème. Donc, c'est quoi qui t'intéresse en fait ?

Pour 50 numeros ce n`est pas faisable c`est tres complexe car il s`agit de plus de 2000000 de combinaisons (C(50,5)). Avec 10.000 on peut trouver une solution s`approchant de la valeur maximale.
Avec 25 on peut solutionner de maniere exhaustive.

Merci pour le debut de reflexion.

[Mario2015]

En fait, on peut travailler sur des ensembles < 12 de maniere exhaustive en cherchant les maximums tel que les quintuplets aient respectivement 0,1,2,3,4,5 en commun.
Ensuite on peut degager une idee sur la distribution.
Pour 25 par exemple on a exactement 5 quintuplets ayant 0 en commun et une seule ayant 5 "en commun" (avec elle-meme. Le reste (1 en commun 2 en commun etc..) je ne sais pas.

[Ben314]

A mon sens, ce n'est pas un problème de "faisable" ou "pas faisable", c'est surtout un problème que les deux questions n'ont pas grand rapport l'une avec l'autre : dans un cas, c'est assez clairement un problème de proba et dans l'autre, plutôt un problème de théorie des graphes. Donc je suis a peu prés persuadé que de solutionner un des deux problèmes n'aura a peu prés aucune incidence sur l'autre.
En tout cas moi, les vagues idées qui me viennent concernant la façon d'évaluer la valeur de la moyenne sur un échantillon de combinaisons n'ont aucun rapport avec celles qui me viennent concernant la valeur du max sur l'ensemble total des combinaisons (deuxième question qui, a froid, me semble plus abordable mathématiquement que la première qui, quand à elle, pourrait éventuellement être l'objet de simulations informatiques). De plus, je ne vois pas vraiment ce que la réponse numérique a une des question pourrait donner comme information concernant la deuxième question.

Donc je redemande : c'est laquelle de question qui t'intéresse en fait ?

[Mario2015]

A mon sens, ce n'est pas un problème de "faisable" ou "pas faisable", c'est surtout un problème que les deux questions n'ont pas grand rapport l'une avec l'autre : dans un cas, c'est assez clairement un problème de proba et dans l'autre, plutôt un problème de théorie des graphes. Donc je suis a peu prés persuadé que de solutionner un des deux problèmes n'aura a peu prés aucune incidence sur l'autre.
En tout cas moi, les vagues idées qui me viennent concernant la façon d'évaluer la valeur de la moyenne sur un échantillon de combinaisons n'ont aucun rapport avec celles qui me viennent concernant la valeur du max sur l'ensemble total des combinaisons (deuxième question qui, a froid, me semble plus abordable mathématiquement que la première qui, quand à elle, pourrait éventuellement être l'objet de simulations informatiques). De plus, je ne vois pas vraiment ce que la réponse numérique a une des question pourrait donner comme information concernant la deuxième question.

Donc je redemande : c'est laquelle de question qui t'intéresse en fait ?

La seconde d`abord mais aussi la premiere. A mon humble avis les 2 sont liees mais cela est un autre probleme que j`eviterai d`aborder pour l`instant.
Ces questions ne sont qu`une etape pour solutionner un autre probleme.
Bref, mes idees sont confuses en ce moment.

[Ben314]

A mon humble avis les 2 sont liees mais cela est un autre probleme que j`eviterai d`aborder pour l`instant.

Je pense qu'effectivement, ça n'a pas grande importance pour le moment. De toute façon, mon opinion sur ce point (contraire a la tienne) n'est vraiment qu'un "vague a priori" donc y'a pas grand chose comme matière a débat.
Concernant le problème du max sur l'ensemble des combinaisons, j'essayerais bien de regarder (pour les petites valeurs) la structure du graphe formé des combinaisons et dont les arrêtes matérialisent les couples de combinaisons ayant exactement deux nombres en commun. Ce graphe est clairement très symétrique et il y a éventuellement une façon de le représenter qui donne des idées sur la taille de son plus grand sous graphe connexe.

[Mario2015]

Pour ce probleme je pense que c`est regle.
J`ai trouve l`algorithme solution.
J`attends juste l`implementation puisque je ne suis pas programmeur.
On verra dans quelques semaines.

[Mario2015]

Je vous livre l`algorithme en anglais.
Pas le temps de le traduire. Je suis tres las.
Faites-en ce que vous voulez et ameliorez-le surtout car c`est juste un concept de base.

The algorithm start from 2 facts :
1 Let us note m the maximal number of combinations sharing 2 numbers pairwise. If m is in fact the maximal number reachable then any subset of the set of combinations sharing 2 numbers pairwise will he the same property.
2-Among all the quintuplets C(25,5) there are many sets of size m having the same property (sharing 2 numbers pairwise).

Starting from the 2 facts here is how the algorithm will work.
It will by steps.
First step : building sets of 2 combinations sharing 2 numbers pairwise.
We list all the quintuplets.
We start from the first quintuplet and we try to find the next one sharing 2 pairwise. We got the first subset of 2 quintuplets.
We do the same process for the remaining until the last quintuplet.
So in this step will obtain some number of subsets with 2 quintuplets and others with 1 quintuplet.
Second step : We restart from the new configuration trying to find subsets to be associated to from subsets of 4 quintuplets or three.
Third step : same process to form biggest subsets ....
We continue the steps doing the same process until no association is possible.
At this stage : the 53130 (C(25,5)) quintuplets will be partitionned in subsets of different sizes.
The biggest one could be of the size m but we are not 100% sure.
Here comes the final and definitive step : we take the biggest set and we start checking the set with all the remaining individual quintuplets. Some quintuplets will maybe be added to give us finally what we are looking for : the maximal number of quintuplets sharing 2 numbers pairwise.

Let me be clear :
-I did not implement the algorithm so there are maybe some minor problems to fix.
-I assume that there is a high probability to reach the solution using my algorithm. I have no proof for that.

The best way to know if it works is to implement it and to run it for 10<n<18. It will be manageable for sure.

[Mario2015]

Je pense qu'effectivement, ça n'a pas grande importance pour le moment. De toute façon, mon opinion sur ce point (contraire a la tienne) n'est vraiment qu'un "vague a priori" donc y'a pas grand chose comme matière a débat.
Concernant le problème du max sur l'ensemble des combinaisons, j'essayerais bien de regarder (pour les petites valeurs) la structure du graphe formé des combinaisons et dont les arrêtes matérialisent les couples de combinaisons ayant exactement deux nombres en commun. Ce graphe est clairement très symétrique et il y a éventuellement une façon de le représenter qui donne des idées sur la taille de son plus grand sous graphe connexe.

Salut,

Alors les graphes cela donne quoi finalement?

[Mario2015]

Sur un autre forum quelqu`un a poste des preuves mathematiques.
Pour n=25 on ne peut pas exceder 26 quintuplets (25+1) ayant exactement 2 nombres en commun.