Combinaisons !

[lapuce798]

Bonjour à tous,
Après plusieurs heures de recherche, j'ai besoin d'aide afin de dénombrer quelques combinaisons de 5 valeurs (sans remise) parmi 48 valeurs différentes sans jamais avoir deux fois la même combinaison de deux valeurs.

exemple sur des valeurs entre 1 et 48 :
1, 2, 3, 4, 5 ne pourrait pas être compatible avec 1, 2, 6, 7, 8 puisque la combinaison 1 avec 2 a déjà été employé précédemment.

J'espère avoir été claire !
En espérant avoir de l'aide,
Merci !!!

[pascal16]

1, 2, 3, 4, 5 et 6,1, 2, 3, 4 sont-ils compatibles ?

[lapuce798]

Bonjour Pascal,
Merci pour ton aide mais celle-ci ne me permet pas d'avancer dans ma réflexion.
En effet, tu prends en compte l'ensemble des possibilités soient 1.712.304.
Je cherche à n'avoir jamais deux fois la combinaison utilisant les mêmes valeurs comme l'exemple précité dans l'énoncé.
Je vais faire un autre exemple :
1 2 3 4 5 et totalement différent de 6 7 8 9 10 ou encore de 11 12 13 14 15
cependant 1 2 3 4 6 ou encore 1 2 3 4 7 sont des combinaisons qui comportent quatre fois les mêmes valeurs.

[lapuce798]

1, 2, 3, 4, 5 et 6,1, 2, 3, 4 sont-ils compatibles ?

Sachant que dans tes deux combinaisons 1, 2, 3 et 4 sont présents, ces deux combinaisons ne sont pas compatibles. En effet, les combinaisons 1 2, 1 3, 1 4, 2 3, 2 4 et 3 4 sont présentes à deux reprises !

Merci encore pour le temps consacré à mon problème !

[pascal16]

j'ai fait un test : les nombres à 3 chiffres pour 5 valeurs de 1 à 5.
j'ai 9 solutions : 123 132 142 152 241 251 345 354 431
partir de 60 et enlever des cas : pas facile, certains ciffres sont éluminés par plusieurs combinaisons.
j'ai fait un espèce de crible, il a fallu que je marque les combinaisons que j'avais passé.
Il faut peut-être dénombrer pas "où je peux mettre ma première combinaison, où je peux mettre ma seconde.."

[lapuce798]

Peux-tu m'expliquer pourquoi tu as pris des nombres à trois chiffres ayant à ma disposition des valeurs de 1 à 48 donc a un ou deux chiffres.
De plus, dans tes 9 solutions, 132 et 123 comportent trois combinaisons identiques 1 2, 13 et 23
Pourquoi partir de 60 ?
Je ne comprends pas le sens de la dernière phrase...
Je sens que j'ai encore du pain sur la planche !!!

[pascal16]

avec comme exemple :
1, 2, 3, 4, 5 ne pourrait pas être compatible avec 9, 2, 1, 7, 8 puisque la combinaison 1 avec 2 a déjà été employé précédemment.
ça aurait donné tous les sous-cas d'un coup

poussons le vice
et 1, 2, 3, 4, 5 avec 9, 2, 7, 1, 8 compatible ou pas ? (sinon, ça simplifie tout)

[lapuce798]

pas compatible puisque la combinaison 1 avec 2 et employé dans 1 2 3 4 5 mais aussi dans 9 2 7 1 8

En espérant que ca simplifie tout parce que je n'arrive pas à te suivre (mais te fais confiance ! )

[pascal16]

Je ne trouve aucune astuce, mis à part le dénombrement à la main , j'ai 62.

[lapuce798]

Merci Pascal
Comment as-tu fait ton dénombrement à la main alors ?

[Lostounet]

En fait si j'ai bien compris: si on reprend l'exemple miniature avec 9 chiffres et qu'on choisisse 3 nombres parmi 9. Bien entendu je suis pas certain de ma réponse mais une tentative.


On peut former (3 parmi 9) triplets donc 9×8×7/6=42 triplets

Mais attention, si on considère un de ces triplets par exemple (1 2 3) celui-ci empêche d'avoir dans un autre triplet (1;2) (2;3) et (1;3) donc chaque fois qu'on prend un autre triplet on doit supprimer tous ceux qui continennent ces trois paires:

1 2 4
1 2 5
1 2 6/7/8/9 ne conviennent plus

Ni
4 2 3
5 2 3
Etc... donc 18 triplets ne conviennent plus.

Il en reste 42-18=24

On prend un des triplets, et rebelotte 18 autres ne conviennent plus.

Il reste 6 triplets: en tout 8 triplets conviennent

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

Qui en voit d'autres? :p j'ai une erreur?

[lapuce798]

Merci Lostounet de t'intéresser à mon problème. J'arrive à suivre le raisonnement jusqu'à "Ni 4 2 3, 5 2 3". Tu as bien saisi mon problème. Après je ne suis pas capable de valider tes propos. Je trouve juste étonnant que le 1 soit utilisé 4 fois contrairement au 8 et 9 utilisé 1 seul fois mais je ne suis absolument pas sûre de la pertinence de mes propos !!!

[Ben314]

Salut,
J'ai pas trop tout lu en détail, mais si j'ai bien compris, le but du jeu est de trouver UN (2) ensemble de sous ensemble (1) à k éléments de {1,2,3,...,n} tels que 2 sous ensembles quelconques de l'ensemble aient au plus un élément en commun.

Le (1) : je suis pas sûr de capter complètement vu qu, juste çi dessus, lostounet empoie explicitement le mot "triplets" mais par contre, au final vu ce qu'il écrit, ça donne l'impression qu'il raisonne plutôt sur les sous ensembles à 3 éléments que sur les triplets...

Le (2) là, à mon sens, c'est un VRAI problème : de ce que j'ai lu en diagonale au dessus, ça m'a donné l'impression que vous faisiez comme si de tels ensembles (de sous ensembles) il n'y en avait qu'un (à isomorphisme prés ou un truc du même genre) alors qu'à froid, je vois pas franchement pourquoi deux tels ensembles (de sous ensembles) "maximaux" auraient forcément le même ombre d'éléments (où "maximaux" veut évidement dire qu'on ne peut plus rien rajouter sans déroger à la contrainte fixée).
Par exemple, ça donne l'impression que Lostounet, dans sa liste, a commencer par prendre "tout ce qui était possible et qui contient un 1" et je vois pas trop comment justifier que c'est forcément comme ça qu'on va obtenir le plus grand ensemble possible (en terme de cardinalité).

[pascal16]

peut être qu'au niveau lycée, qu'un dénombrement soit supposé être le dénombrement est suffisant.
C'est pour cela que trouver une façon logique de dénombrer permet de faire les deux en mêm temps. Mais j'en ai pas trouvé.
On peut dire aussi que c'est le nombre de parties à 5 éléments différents telles que pour 2 ensembles A et B de 5 éléments < 2

[Ben314]

peut être qu'au niveau lycée, qu'un dénombrement soit supposé être le dénombrement est suffisant.

Ben....
Sauf que justement, si la question posée est bien celle que je donne dans le post. précédent, il s'agit pas du tout de "dénombrement" qui signifie qu'on des objets parfaitement déterminés et qu'il faut en trouver le nombre.
Là, si je te dit "est-ce que 1,3,5,7 fait parti des trucs que je doit compter ou pas ?", ben on peut pas répondre : ça va dépendre de quels sont les autres qu'on a déjà choisi (ou qu'on va choisir ensuite).
C'est pour ça que j'ai mis en gras le UN du début de l'autre post. : pour "dénombrer" quelque chose, il faut pouvoir parler de LE quelque chose...

P.S. Et vu que justement c'est pas du dénombrement mais quelque chose de bien bien plus compliqué que ça, je pense que tu te trompe concernant ton "au niveau Lycée" dans le sens que ce n'est pas un problème scolaire.

[Lostounet]

Sinon Ben penses-tu qu'en s'y prenant différemment (que moi) on puisse trouver plus de combinaisons (donc pas forcément les mêmes)

[Ben314]

Sinon Ben penses-tu qu'en s'y prenant différemment (que moi) on puisse trouver plus de combinaisons (donc pas forcément les mêmes)

Honnêtement, j'en sais rien.
Je pencherais (légèrement) du coté "on peut pas faire mieux", mais sans aucune certitude.
Si j'ai du temps je regarderais, mais il y aussi celui avec les triangles dans le plan qui est exactement du même tonneau sur lequel j'ai (un peu) réfléchi sans arriver à quoi que ce soit :
enigmes/geometrie-denombrement-t183471.html

[Lostounet]

Ça fait vraiment peur quand tu dis des choses comme ça (que tu n'es pas arrivé à faire l'exo).

[Ben314]

Sinon, pour se faire une idée du schmilblick, tu peut faire un programme sur l'ordi. à qui tu donne un N et un K et qui cherche une liste de sous ensemble à K éléments de {1..N} sans avoir deux sous ensembles ayant plus d'un point commun, mais en procédant "au hasard" : C'est à dire en dressant la liste des binom(N,K) sous parties, puis en les tirant les une après les autres au hasard (en les enlevant de le liste bien sûr) et en les rajoutant éventuellement à une autre liste (les "admis") si elle n'entre pas en "conflit" avec une déjà admise.

Ensuite tu lance le bidule une bonne centaine de fois avec le même N et le même K et ça te donnera déjà une idée en regardant s'il trouve toujours le même nombre "d'admis" à la fin ou pas.

Ça fait vraiment peur quand tu dis des choses comme ça (que tu n'es pas arrivé à faire l'exo).

Oui, mais ce type d'exo. j'attaque systématiquement par la partie "la plus dure" (mais la plus amusante), à savoir "comment va-t-on faire pour prouver l'optimitude de la solution proposée".

[lapuce798]

Merci pour toutes vos réponses !
J'adore réfléchir sur le domaine des probabilités et des statistiques et le fait de ne pas trouver la réponse me titille un peu
En tout cas si vous prenez le temps de réfléchir, je serai très heureuse d'apprendre de vos essais (en espérant pouvoir les comprendre !
Bonne soirée