Combinatoire

Olympiades mathématiques, énigmes et défis
Bramant52
Membre Relatif
Messages: 125
Enregistré le: 13 Aoû 2014, 17:06

Combinatoire

par Bramant52 » 13 Aoû 2014, 17:20

Bonjour,

15 boules sont numérotées de 1 à 15.

On cherche à savoir le nombre maximal de combinaisons de 5 boules qu'on peut créer sans que 2 combinaisons aient plus de 2 boules en commun ?

Merci



Bramant52
Membre Relatif
Messages: 125
Enregistré le: 13 Aoû 2014, 17:06

par Bramant52 » 13 Aoû 2014, 19:42

Pour 10 mon maximum est 6 :

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

Bramant52
Membre Relatif
Messages: 125
Enregistré le: 13 Aoû 2014, 17:06

par Bramant52 » 14 Aoû 2014, 15:03

Je suis arrivé à 24 combinaisons :

1,2,3,4,5
1,2,6,7,8
1,3,8,9,10
1,4,6,10,11
1,5,7,9,11
1,12,13,14,15
2,3,7,10,11
2,4,8,9,11
2,5,6,9,10
2,5,11,12,14
2,6,11,13,15
2,7,9,14,15
3,4,6,7,9
3,4,11,12,15
3,5,6,8,11
3,5,10,13,15
3,9,11,13,14
4,5,6,14,15
4,5,7,8,10
4,9,10,12,14
5,8,9,12,15
6,7,10,12,15
7,8,11,12,13
8,10,11,14,15

Peut-on faire mieux?

Bramant52
Membre Relatif
Messages: 125
Enregistré le: 13 Aoû 2014, 17:06

par Bramant52 » 15 Aoû 2014, 14:55

Aucune reponse!
Ah j`oublie c`est les vacances.
A dans un mois alors?

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 12:00

par fatal_error » 16 Aoû 2014, 07:35

bonjour,

A dans un mois alors?

peut etre bien, je suis tombé dessus, mais à part une approche un peu brute force j'ai rien d'autre.
la brute force c'est ici par exemple de
considérer une ligne indexée de 1 à 15, composée de 0 ou 1 (cinq 1 pour cinq boules tirées).

On prend k lignes, et on cherche à avoir toutes les lignes distinctes deux à deux (idem A.B <=2 avec A et B deux lignes différente, et . le produit scalaire usuel)

puis si on trouve pas de solution, on essaie avec k-1 lignes...

mais c'est pas très glorieux, dans
http://www.maths-forum.com/showthread.php?t=154625&page=1&highlight=L.A
ca ressemble un peu, on parle de plan projectif mais jbite rien, donc j'en sais rien, peut etre que ca te parlera plus sait-on jamais...
la vie est une fête :)

Nicolas.L
Membre Naturel
Messages: 79
Enregistré le: 07 Aoû 2014, 15:34

par Nicolas.L » 16 Aoû 2014, 09:40

J'ai aussi penser à faire un algorithme mais il faudrait faire un algo intelligent parce que brute force ça n'irait pas..

Il y a combinaison possible.. si on veut essayer toutes les combinaison de 25 combinaison ( dans le but d'améliorer le résultat de Bramant) il faut essayer combinaisons ( ce nombre est de l'odre de :triste: )
Bien sûr j'exagère car il est évident qu'il est innutile d'essayer toutes les combinaisons, mais je n'ai pas trop d'idée pour l'algorithme..

Bramant52
Membre Relatif
Messages: 125
Enregistré le: 13 Aoû 2014, 17:06

par Bramant52 » 16 Aoû 2014, 16:16

Merci pour toutes ces reponses.
Je viens de penser au tri croise des matrices.
Imaginons une matrice carre 3003*3003.
Notons 1 pour les intersections 0,1,2 et 5 puis 0 pour les intersections 3 et 4
Existe-t-il des algorithmes efficaces pour classer cette matrice de maniere a avoir un carre de 1,1, un carre de 1,0, un carre de 0,1 et enfin un carre de 0,0 ?
Si on arrive a regrouper les 1 on a la solution.
Bref, ce n`est qu`une idee. Je vais faire des essais sur (10,5) avec une matrice 252*252 pour voir. Je suppose que mon maximum de 6 est correct.

Merci pour toute suggestion.

Bramant52
Membre Relatif
Messages: 125
Enregistré le: 13 Aoû 2014, 17:06

par Bramant52 » 16 Aoû 2014, 17:10

Desole y a une erreur dans mon raisonnement car il y a plusieurs possibilites de 6 combinaisons (42 en tout). On devrait avoir 42 carres de 6 le long de la diagonale ne comprenant que des 1.
Je parle du cas (10,5).

J`abandonne pour l`instant faute de temps.

Avatar de l’utilisateur
WillyCagnes
Membre Transcendant
Messages: 3754
Enregistré le: 21 Sep 2013, 19:58

par WillyCagnes » 17 Aoû 2014, 11:02

Bramant52 a écrit:Je suis arrivé à 24 combinaisons :

1,2,3,4,5
1,2,6,7,8
1,3,8,9,10
1,4,6,10,11
1,5,7,9,11
1,12,13,14,15
2,3,7,10,11
2,4,8,9,11
2,5,6,9,10
2,5,11,12,14
2,6,11,13,15
2,7,9,14,15
3,4,6,7,9
3,4,11,12,15
3,5,6,8,11
3,5,10,13,15
3,9,11,13,14
4,5,6,14,15
4,5,7,8,10
4,9,10,12,14
5,8,9,12,15
6,7,10,12,15
7,8,11,12,13
8,10,11,14,15

Peut-on faire mieux?


je reprends les 3 derniers nombres
1,2,3,4,5
1,6,3,4,5
1,7,3,4,5
1,8,3,4,5
1,9,3,4,5
1,10,3,4,5
1,11,3,4,5
1,12,3,4,5
1,13,3,4,5
1,14,3,4,5
1,15,3,4,5

meme logique pour la suite
1,2,6,7,8,
1,3,6,7,8
1,4,6,7,8
....

tu peux faire un programme pour trouver les autres combinaisons

Bramant52
Membre Relatif
Messages: 125
Enregistré le: 13 Aoû 2014, 17:06

par Bramant52 » 17 Aoû 2014, 13:51

Merci Wily sauf que je n`ai pas bien compris ou tu veux en venir.
En principe mes 24 combinaisons ont au moins une intersection de 3 numros avec toutes les 2979 autres (3003-24=2979).
Unique moyen pour elargir mes 24 combinaisons a plus : eliminer certaines et les remplacer par d`autres.
La solution je l`ai trouvee en fait. C`est un sorte de tri croise par la diagonale.
On cree notre matrice 3003*3003.
On commence a trier par la diagonale qui ne comprend que des 5.
Un programme interactif faciliterait la solution.
On deplace vers le haut une intersection de la diagonale de telle sorte qu`on elimine les 3 et 4 a l`interieur de notre sous-matrice carree recherchee.
La matrice solution ne contiendrait que des 5 sur la diagonale et que des 0,1 et 2 a l`interieur.
Le programme doit faire bouger simultanement en ligne et en colonne la combinaison deplacee.
Comment realiser cela je n`en sais rien pour l`instant.
Quand on deplace en diagonale le point i,j (i=j) de i et j a i-1 et j-1 le programme recalcule en meme temps les intersections entre 0 et j-1 et entre 0 et i-1 s`il trouve 3 ou 4 dans ces intervalles il remonte jusqu`a eliminer les 3 et 4.
Il fera de meme pour tous les points de la diagonale en commencant par le point (3003,3003).
C`est complique mais faisable je pense.

Bramant52
Membre Relatif
Messages: 125
Enregistré le: 13 Aoû 2014, 17:06

par Bramant52 » 17 Aoû 2014, 13:53

En principe on devrait avoisiner les 30 combinaisons pour (15,5).
J`en suis encore loin. M`en faut encore 6

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 12:00

par fatal_error » 17 Aoû 2014, 18:30

salut Bramant52,

On commence a trier par la diagonale qui ne comprend que des 5.

je comprends pas de quoi tu remplis tes matrices.
Je comprends pas non plus ce que représente tes 5

On deplace vers le haut une intersection de la diagonale de telle sorte qu`on elimine les 3 et 4 a l`interieur de notre sous-matrice carree recherchee.

je comprends pas ce que tu appèles une intersection de la diagonale
je comprends pas non plus à quoi correspondent les 3 et 4, ni ce que tu appeles l'interieur de la sous matrice carrée recherchée

Peut etre peux tu faire un exemple simple avec des lignes de taille 10 et un ensemble de solution de 4 lignes, pour avoir une idée?

de manière générale, ta méthode est probablement efficace, mais je pense pas qu'elle te donne la meilleure solution, je pense que tu vas trouver un optimum local mais pas forcément global
la vie est une fête :)

Bramant52
Membre Relatif
Messages: 125
Enregistré le: 13 Aoû 2014, 17:06

par Bramant52 » 17 Aoû 2014, 21:52

fatal_error a écrit:salut Bramant52,


je comprends pas de quoi tu remplis tes matrices.
Je comprends pas non plus ce que représente tes 5


je comprends pas ce que tu appèles une intersection de la diagonale
je comprends pas non plus à quoi correspondent les 3 et 4, ni ce que tu appeles l'interieur de la sous matrice carrée recherchée

Peut etre peux tu faire un exemple simple avec des lignes de taille 10 et un ensemble de solution de 4 lignes, pour avoir une idée?

de manière générale, ta méthode est probablement efficace, mais je pense pas qu'elle te donne la meilleure solution, je pense que tu vas trouver un optimum local mais pas forcément global


Les 5,4,3,2,1 et 0 sont les elements en commun.

ligne 1 (1,2,3,4,5) colonne 2 (1,2,3,4,6) 4 elements en commun donc 4 etc....
Forcement ligne 3 colonne 3 sera egale a 5 et par extension ligne i colonne j (i=j) sera toujours egale 5.

Bramant52
Membre Relatif
Messages: 125
Enregistré le: 13 Aoû 2014, 17:06

par Bramant52 » 17 Aoû 2014, 22:01

une portion de matrice comme exemple

5 1 2 0
1 5 0 3
2 0 5 4
0 3 5 5

la sous matrice
5 1 2
1 5 0
2 0 5

remplit les conditions sans tri croise.
Le but du tri croise est de reclasser vers le haut les lignes et colonnes ne comprenant que des 5, 0, 1, et 2.
La c`est facile il suffit de supprimer simultanement la ligne 4 colonne 4
Je peux le faire a la main par interversion si je pouvais imprimer un tableau de 3003 sur 3003.

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

par nodjim » 18 Aoû 2014, 08:06

Il y a C(n,3) triplets, et un quintet contient 10 triplets. Dans l'ensemble des quintets solutions, chaque triplet n'apparait qu'une fois au mieux, sinon on serait en désaccord avec l'énoncé. Le nb max de quintets solutions est donc limité par C(n,3)/10.
Pour 12 quintets théoriques avec 10 nb, on en trouve 6.
Pour 45 quintets théoriques avec 45 nb, on en trouve 24.

il serait interessant de poursuivre le décompte au dela et en deça de 15 pour savoir si le nb max vaut environ C(n,3)/20.

Groucho
Membre Naturel
Messages: 67
Enregistré le: 14 Mai 2014, 13:19

par Groucho » 18 Aoû 2014, 08:26

Tu as envisagé une solution plus sophistiquée. Avec d'autres contraintes de même style, ça peut marcher. Voici un exemple

Tu as cette fois ci 25 (au lieu de 15) boules, et tu veux des combinaisons de 5 boules telles que 2 combinaisons n'aient pas plus de 2 éléments en commun.

Tu considère , le corps à 5 éléments, et P le plan affine sur ce corps (c'est à dire ). Cet ensemble indexe tes boules.

Pour a, b, c dans , on considère l'ensemble des éléments (x,y) de P satisfaisant (dans , évidemment). Il y en a exactement 5 éléments dans cet ensemble et 2 tels ensembles n'ont pas plus de 2 points en commun. Ce qui donne 125 combinaisons.

On peut surement trouver d'autres exemples. Avec le plan projectif sur le corps à 4 éléments peut être, mais ça semble plus compliqué. Je vais essayer avec Z/pq, où p et q sont premiers, just for fun.

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 12:00

par fatal_error » 18 Aoû 2014, 08:58

Je n'ai toujours pas compris le but de ton algorithme.
Tir croisé n'est pas non plus un algorithme documenté sur le net, je présume que c'est une appellation de ton cru :D
Les 5,4,3,2,1 et 0 sont les elements en commun.

en quoi sont-ce des éléments commun

ligne 1 (1,2,3,4,5) colonne 2 (1,2,3,4,6) 4 elements en commun donc 4 etc....

comment la colonne peut elle commencer par 1 alors que l'element a la ligne 1, colonne 2 est le nombre 2.
4 elements en commun donc 4 etc...
ne veut rien dire

Forcement ligne 3 colonne 3 sera egale a 5 et par extension ligne i colonne j (i=j) sera toujours egale 5.

je vois pas en quoi c'est forcé, ligne 3 colonne 3 pour moi ca veut rien dire.
C'est comme dire tartiflette patate.

C'est peut etre clair dans ta tete, mais si t'arrives pas à partager tes idées (ptet chui lent, que beagle m'éclair, ce style ressemble :we: ), ben tu risques de faire ton trip tout seul :/

Mis à part, on peut formuler le problème sous prog linéaire.
Soit une matrice binaire A de 15 colonnes et n lignes.
n=5 parmi 15=3003
A représente la liste de toutes les pioches possibles.
Pour toute ligne de la matrice, la somme des coeff de cette ligne vaut 5. (idem on a pioché que 5 nombres).
soit l_i une ligne de cette matrice, l_j une autre.
On note l_i.l_j=a_ij. ('.' le produit scalaire). On veut a_ij= 16 //on active la comparaison du produit scalaire l_il_j si on met les lignes i et j dans l'ensemble des solutions. Cette inégalité est vraie que si x_i et x_j valent 1
8*x_i+8*x_j+a_ij <= 16+2 //x_i et x_j valent 1 donc 8x_i+8x_j == 16
finpour
x_i dans {0,1}
finpour[/CODE]

enfin bon, je suis pas sur que ca converge en un temps acceptable (comme ca a été fait remarqué par Nicolas.j)

edit:pas vu les posts de nodjim et groucho
la vie est une fête :)

Nicolas.L
Membre Naturel
Messages: 79
Enregistré le: 07 Aoû 2014, 15:34

par Nicolas.L » 18 Aoû 2014, 09:00

nodjim, je n'ai pas bien compris ton intervention, qu'est-ce que tu appelle quintet et triplet ? J'avais essayer une étude théorique mais je n'ai rien trouvé de mon côté :triste:

Edit : en fait je crois que j'ai compris, quand tu dit qu'un quintet contient 10 triplet c'est parce que ?

Groucho
Membre Naturel
Messages: 67
Enregistré le: 14 Mai 2014, 13:19

par Groucho » 18 Aoû 2014, 10:15

nodjim a écrit:
il serait interessant de poursuivre le décompte au dela et en deça de 15 pour savoir si le nb max vaut environ C(n,3)/20.


Je n'ai pas vraiment suivi votre discussion, aussi je ne suis pas sur de ce que tu veux dire. Mais, est ce que ton hypothèse n'est pas en contradiction avec mon précédent message où je trouve 125 combinaisons avec 25 boules ?

Nicolas.L
Membre Naturel
Messages: 79
Enregistré le: 07 Aoû 2014, 15:34

par Nicolas.L » 18 Aoû 2014, 11:18

Groucho a écrit:Je n'ai pas vraiment suivi votre discussion, aussi je ne suis pas sur de ce que tu veux dire. Mais, est ce que ton hypothèse n'est pas en contradiction avec mon précédent message où je trouve 125 combinaisons avec 25 boules ?


En fait nodjim a montré que le nombre de combinaison est majoré par mais a remarqué que ce majorant n'est pas atteint, et il a fait l'hypothèse que le nombre de combinaison était en fait "proche" de ce qui semble en effet contredit par ton resultat

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

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