Combinaisons a placer dans un tableau

Bemo52 · 29-01-2014 17:35:07

Bonjour a toutes et a tous,

Je viens de m`inscrire.
Voici mon probleme.

J`ai un tableau 10x10.
Dans chaque case du tableau, je dois placer un ensemble de 5 numeros distincts {a,b,c,d,e}.
Les 5 numeros correspondent a une combinaison extraite a partir de 50 numeros (de 1 a 50). L`ordre des numeros est l`ordre naturel.
Je me dois de restecter 3 conditions :
1. Tous les numeros de 1 a 50 ne sont cites qu`une seule fois par colonne ou par ligne (comme au sudoku). Par consequent, l`intersection des ensembles de 5 numeros pris 2 a 2 (soit en colonne soit en ligne) est vide. Donc aucun element en commun.

2. Les 100 ensembles de 5 numeros sont distincts. Aucune combinaison n`est repetee.

3. Les 100 ensembles de 5 numeros pris 2 a 2, ont au plus 2 numeros en commun.

Il est fort possible que le probleme admette plusieurs solutions.
Cependant, une seule solution me satisferait.

Merci pour toute aide.

Bemo52 · 29-01-2014 21:23:17

Est-ce que vous avez deja rencontre de pareils problemes?
Si oui, pouvez-vous me fournir une documentation (sur internet) ou des references pour attaquer ce genre de probleme.
Hormis, une solution informatique je vois difficilement le bout du tunnel.

Merci

miq · 30-01-2014 09:41:26

Bonjour,

Effectivement je voie mal comment gérer ça autrement qu'informatiquement, mais certainement pas en fonçant tête baissée dans la force brute.

Déjà est-tu certain qu'il y ait une solution ?

T'as essayé de théoriser sur ce qui se passait par construction ?

Étude préalable:
Première ligne :
- Condition 1 horizontale impose un départ de 1 par pas de +1
[ 1 2 3 4 5] [ 6 7 8 9 10] [11 12 13 14 15] [16 17 18 19 20] ...

Seconde ligne :
- Condition 1 verticale impose un départ à 6
- Condition 3 impose un pas minimum de +3 (parce que +2 donnerait [6 8 10 ...] déjà contenus en ligne 1)
[ 6 9 12 15 18] [21 24 27 30 33] [36 39 42 45 48] [1 4 7 10 13] ...
mais est-ce que ce pas fonctionne partout sur cette ligne sans télescopage à cause des cycles ? (tests nécessaires)

On peut peut-être éviter ce (peut-être) problème de cycles en utilisant plutôt une solution verticalement initialisée comme:
[ 6 9 12 15 18] [ 11 14 17 20 23] [16 19 22 25 28] ...
Mais cette seconde solution se répartit-elle bien (notamment dans les passages de 50 à 1)? (tests nécessaires)

Ligne 3 :
Si on a un pas de +3 en ligne 2 un pas de +4 en ligne 3 devrait fonctionner sans recouvrement ni avec la ligne 1 ni avec la ligne 2.
[19 23 27 31 35] [39 43 47 1 5] ...
où encore
[19 23 27 31 35] [24 28 32 36 40] ...

Peut-on théoriser sur la taille des pas des lignes suivantes ?
une augmentation de +1 à chaque nouvelle ligne semble fonctionner sans recouvrement (tests)
si on commence avec un pas de 2 à la première ligne et qu'on augmente par pas de 1, trouves-t'on une solution systématique ?
Non. On a un problème avec 2, c'est qu'on va répéter 2 fois les pairs et oublier les impairs en allant de 2 à 50.
On a ce problème pour tous produits de sous ensembles de la décomposition en facteurs premiers de 50, soit [2, 5, 10, 25] mais aussi pour tous leurs multiples, (notamment tous les pairs)
Ok, alors si on prends comme pas successifs pour chaque ligne 1,3,7,9,11,13,17,19,21,23 ? (c'est presque un crible d'ératosthène.)

Reste le problème de la condition 1 verticale, rien ne garantis cette condition pour l'instant.
en colonne 1 on à [1 2 3 4 5] [6 9 12 15 18] [19 26 33 40 47] [48 7 16 25 34]...
On trouve peut-être une solution à cette colonne avec la suite de pas donnés, ou avec certains de ces pas et leurs successeurs. Si on en trouve une, alors on devrait avoir la grille complète en utilisant la deuxième option pour la seconde ligne, car la colonne 2 sera alors la colonne 1 dont chaque nombre sera additionné de +5.

Si on ne trouve pas de solution pour la colonne, il faudra essayer en décalant les premiers nombres de chaque élément de la colonne (par exemple [1 2 3 4 5][7 10 13 16 19]...). Cette solution nous donnerait aussi une grille complète.

Enfin, si ça ne fonctionne toujours pas, il faudra trouver un filtre moins sévère pour le pas de la seconde ligne, voire tester sans pas (avec des successions de permutations non recouvrantes de 5 parmi 50). Mais là on ne conserve pas la propriété de la ligne 2 solution 2 qui nous permettait de générer les autres colonnes par addition.

voilà les premiers tests en python:

#p pas
#x tableau horizontal
#y tableau vertical
#z profondeur des listes du tableau

# première ligne

px=5

pz=1

l1=[[1+(px*i+pz*k)%50 for k in range(5)] for i in range(10)]

# seconde ligne méthode 1

dec=6

px=15

pz=3

l2=[[(dec-1+px*i+pz*k)%50+1 for k in range(5)] for i in range(10)]

# seconde ligne méthode 2

dec=6

px=5

pz=3

l2b=[[(dec-1+px*i+pz*k)%50+1 for k in range(5)] for i in range(10)]

# test de la répartition horizontale des 50 nombres

def test1h(l):

    v=[k for i in l for k in i]

    v.sort()

    return v==[i for i in range(1,51)]

"""

>>> l1

[[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19, 20], [21, 22, 23, 24, 25], [26, 27, 28, 29, 30], [31, 32, 33, 34, 35], [36, 37, 38, 39, 40], [41, 42, 43, 44, 45], [46, 47, 48, 49, 50]]

>>> l2

[[6, 9, 12, 15, 18], [21, 24, 27, 30, 33], [36, 39, 42, 45, 48], [1, 4, 7, 10, 13], [16, 19, 22, 25, 28], [31, 34, 37, 40, 43], [46, 49, 2, 5, 8], [11, 14, 17, 20, 23], [26, 29, 32, 35, 38], [41, 44, 47, 50, 3]]

>>> l2b

[[6, 9, 12, 15, 18], [11, 14, 17, 20, 23], [16, 19, 22, 25, 28], [21, 24, 27, 30, 33], [26, 29, 32, 35, 38], [31, 34, 37, 40, 43], [36, 39, 42, 45, 48], [41, 44, 47, 50, 3], [46, 49, 2, 5, 8], [1, 4, 7, 10, 13]]

>>> test1h(l2)

True

>>> test1h(l2b)

True

"""

donc les 2 lignes 2 répondent à la condition 1, ce qui semble valider cette construction linéaire pour la suite.

Est-ce qu'on réponds à toutes les conditions ? Non, il faudrait encore vérifier que certains nombres ne tombent pas dans la même colonne quand les pas ne sont pas premiers entre eux.... (Cela dit un test dans la colonne 1 pourrait suffire si on la construit par la méthode des pas. cf propriété du passage par addition de +5 d'une colonne à l'autre.)

Dernière modification par miq (30-01-2014 09:57:08)

yoshi · 30-01-2014 09:48:45

Salut,

Bienvenue sur BibMath...
Peut-être faudrait-il regarder du côté des "carrés gréco-latins" et s'en inspirer ?
Voir :
http://www.bibmath.net/carres/index.php … uler_magie
http://fr.wikipedia.org/wiki/Carr%C3%A9 … A9co-latin
http://www.statsoft.fr/concepts-statist … latins.htm

@+

miq · 30-01-2014 10:17:18

En résumé, si solution avec des pas réguliers il y a, le problème se résume à trouver
-pour les 10 pas 1,3,7,9,11,13,17,19,21,23 (au delà de 50, c'est le même pas modulo 50, et entre 25 et 50 on a une symétrie.)
-une liste de 9 valeurs de départ (la première étant fixée à 1 pour éviter les solutions par translation)
-tels que dans une colonne de 10 cases on puisse mettre les 5 nombres tous modulo 50 [départ, départ+pas, départ+2pas, départ+3pas, départ+4pas] sans recouvrement de ceux-ci.
Si cette colonne existe les autres colonnes devraient se construire par +5 et respecter toutes les conditions données.

Dernière modification par miq (30-01-2014 10:43:39)

miq · 30-01-2014 10:41:05

voilà deux essais qui ne fonctionnent pas pour la colonne 1:

# colonne 1

pas=[1,3,7,9,11,13,17,19,21,23]

#avec px=5

px=5

[[(px*i+pz*k)%50+1 for k in range(5)] for i,pz in zip(range(10),pas)]

#avec dernière valeur du précédent +1

dec=1

res=[]

for i,pz in zip(range(10),pas):

    res.append([])

    for k in range(5):

        tmp=(dec-1+pz*k)%50+1

        res[-1].append(tmp)

    dec=tmp+1

Posons le problème comme un arbre :
+1 +3 +7
1 2 3 4 5 ___6 9 12 15 18 ____ 7 14 21 28 35 __...
\ \___ 8 15 22 29 36__...
\ \...
\__ 7 10 13 16 19 __...
\...

Il faut calculer les solutions de +3 dont le premier nombre est entre 6 et 38(=50-4*3) pour éviter le recouvrement d'un nombre de 1 à 5.
Pour +7 il faut aller de 6 (ou 7 selon le cas du +3) à 43(=50-7) ?
Il y a peut-être moyen de réduire drastiquement la taille de cet arbre en raisonnant sur les contraintes posées par le non recouvrement d'une feuille et de ses parents.

Dernière modification par miq (30-01-2014 10:41:54)

Bemo52 · 30-01-2014 13:09:45

Bonjour,

Merci a vous 2 pour les refrences et les tentatives de solution.
En fait, je ne sais pas si le probleme a une solution. Mon flair me dit qu`il en a un grand nombre.
En relisant ce qu`a ecrit Miq j`ai eu une idee.
Faisons comme si on avait a caser 3 series de numeros de 1 a 10 dans un tableau 10x10.
Faisons les remplacements suivants :
Pour chaque numero on a un couple correspondant le 1 correspond a 1-2 etc...
1ere serie :

1 1 2
2 3 4
3 5 6
4 7 8
5 9 10
6 11 12
7 13 14
8 15 16
9 17 18
10 19 20

2eme serie :
1 21 22
2 23 24
3 25 26
4 27 28
5 29 30
6 31 32
7 33 34
8 35 36
9 37 38
10 39 40

3eme serie (numeros restants)

1 41
2 42
3 43
4 44
5 45
6 46
7 47
8 48
9 49
10 50

Le probleme reviendrait a resoudre chaque placement a part dans un premier temps.

Les 20 couples et les 10 restants.

Une fois cela fait on commence a intervertir de maniere a eviter des 3 et des numeros ensemble :

par exemple 1-2 et 23-24 ne figureront qu`une fois ensemble etc...

Qu`en pensez-vous?

Bemo52 · 30-01-2014 13:35:16

Je rajoute un detail de planning.
On commence d`abord par placer la 1ere serie de couples. Elle sera fixe (une sorte de point de depart). De preference, on evitera la rotation (+1).
Ensuite on placera la seconde serie de couples de maniere a eviter les doublons de 4 numeros en commun.
Enfin, il suffirait de placer les numeros restants de maniere a eviter les doublons de 3 numeros en commun.
J`espere que le tout sera coherent et tiendra la route.
Si on trouve une solution cela signifierait qu`il en existe un tres grand nombre par permutation des 50 numeros.

Merci.

Bemo52 · 30-01-2014 14:13:43

Je progresse apparement.
Si on represente la 1ere colonne comme etant la 1ere serie de couples et la seconde la seconde serie de couples, le probleme reviendrait a placer dans chacune des cases les 100 couples suivants sans aucune repetition
Je liste donc :
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
1 2
2 2
3 2
4 2
5 2
6 2
7 2
8 2
9 2
10 2
1 3
2 3
3 3
4 3
5 3
6 3
7 3
8 3
9 3
10 3
1 4
2 4
3 4
4 4
5 4
6 4
7 4
8 4
9 4
10 4
1 5
2 5
3 5
4 5
5 5
6 5
7 5
8 5
9 5
10 5
1 6
2 6
3 6
4 6
5 6
6 6
7 6
8 6
9 6
10 6
1 7
2 7
3 7
4 7
5 7
6 7
7 7
8 7
9 7
10 7
1 8
2 8
3 8
4 8
5 8
6 8
7 8
8 8
9 8
10 8
1 9
2 9
3 9
4 9
5 9
6 9
7 9
8 9
9 9
10 9
1 10
2 10
3 10
4 10
5 10
6 10
7 10
8 10
9 10
10 10

On serait assure de la non existence de doublons de 4 numeros.
On aurait alors les 4 premiers numeros de chaque 5-uplet.
A ce stade le probleme serait presque resolu car il suffit de completer (manuellement?) avec un 5eme numero (de 41 a 50).

Voila.
J`attends vos commentaires.

Merci.

Bemo52 · 30-01-2014 17:06:50

Resalut,

Je suis arrive a placer 60 sur 100 sauf que cela devient de plus en plus difficile car certains couples ne sont pas placables.
Je me repose un peu et je reprendrai plus tard : il me faudrait intervertir certains pour faire de la place aux autres.
J`en suis la pour le moment :

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

miq · 30-01-2014 17:33:12

je ne comprends pas trop ce que tu tentes de faire dans les derniers posts. Je suis en train d'essayer de coder un générateur linéaire de l'arbre.
Un truc qui me construise directement (en passant par tranches de 5 avec chacune un des pas que j'ai listé tantôt):
[1,2,3,4,5,6,9,12,15,18,7,14,21,28,35,8,17,26,...]
puis ici il détecterait que le suivant, 35 existe déjà et donc enchaînerait sur:
[1,2,3,4,5,6,9,12,15,18,7,14,21,28,35,9
et s'il arrive à invalider 50 comme premier élément de bloc, qu'il défasse le bloc précédent pour le remplacer par le même +1

Mais je doit bientôt y aller, je ne sais pas si je pourrais le finir ce soir.

Dernière modification par miq (30-01-2014 17:33:32)

Bemo52 · 30-01-2014 20:12:03

Je suis sur le point de solutionner le probleme. Ma strategie de solution etait bonne.
Grace a un internaute que je remercie beaucoup et qui m`a fait connaitre les carres greco-latins (je ne connaissais que les latins), j`ai pu solutionner les 2 etapes evoquees plus a savoir placer les couples de la 1ere et de la seconde serie.
Des que ce sera fini, je posterai la solution (il y en a plusieurs assurement).

Merci pour tout.

miq · 31-01-2014 00:10:04

Bon, ma méthode ne trouve pas de solution, ou alors je me suis planté dans mon algo, mais elle a du mal à dépasser le placement de 25 nombres. Adieu méthode des pas.

Ta solution est erronée, 47 se retrouve en dernière colonne première et seconde case. 50 n'est pas représenté dans cette dernière colonne, 47 est représenté deux fois dans l'avant dernière colonne, première et dernière case, et 45 y est représenté deux fois aussi, seconde et troisième case. De même pour 50, en cases 4 et 7...

Bemo52 · 31-01-2014 00:10:30

Desole pour mon erreur.
Je dois completer les "x" par les valeurs de 41 a 50.
Mon probleme n`est pas encore resolu.
Il suffit de placer les 100 4-uplets + x dans un tableau 10x10 dans leur ordre.
Colonne 1 : 1 a 10
Colonne 2 : 11 a 20 etc...

7 8 31 32 x
13 14 21 22 x
17 18 25 26 x
1 2 29 30 x
5 6 23 24 x
11 12 33 34 x
15 16 27 28 x
9 10 37 38 x
3 4 35 36 x
19 20 39 40 x
9 10 33 34 x
17 18 27 28 x
3 4 31 32 x
7 8 25 26 x
13 14 35 36 x
19 20 29 30 x
11 12 37 38 x
5 6 39 40 x
1 2 21 22 x
15 16 23 24 x
11 12 35 36 x
5 6 33 34 x
9 10 27 28 x
15 16 39 40 x
1 2 31 32 x
13 14 37 38 x
7 8 21 22 x
3 4 23 24 x
19 20 25 26 x
17 18 29 30 x
13 14 39 40 x
11 12 29 30 x
19 20 21 22 x
3 4 33 34 x
15 16 37 38 x
9 10 23 24 x
5 6 25 26 x
1 2 27 28 x
17 18 31 32 x
7 8 35 36 x
15 16 21 22 x
1 2 23 24 x
5 6 35 36 x
19 20 37 38 x
11 12 25 26 x
7 8 27 28 x
3 4 29 30 x
17 18 33 34 x
9 10 39 40 x
13 14 31 32 x
19 20 23 24 x
7 8 39 40 x
1 2 37 38 x
13 14 27 28 x
9 10 29 30 x
5 6 31 32 x
17 18 35 36 x
11 12 21 22 x
15 16 33 34 x
3 4 25 26 x
1 2 25 26 x
3 4 37 38 x
15 16 29 30 x
11 12 31 32 x
7 8 33 34 x
17 18 39 40 x
13 14 23 24 x
19 20 35 36 x
5 6 27 28 x
9 10 21 22 x
3 4 27 28 x
19 20 31 32 x
13 14 33 34 x
9 10 35 36 x
17 18 21 22 x
15 16 25 26 x
1 2 39 40 x
7 8 29 30 x
11 12 23 24 x
5 6 37 38 x
5 6 29 30 x
15 16 35 36 x
11 12 39 40 x
17 18 23 24 x
19 20 27 28 x
3 4 21 22 x
9 10 31 32 x
13 14 25 26 x
7 8 37 38 x
1 2 33 34 x
17 18 37 38 x
9 10 25 26 x
7 8 23 24 x
5 6 21 22 x
3 4 39 40 x
1 2 35 36 x
19 20 33 34 x
15 16 31 32 x
13 14 29 30 x
11 12 27 28 x

Je suis fatigue et j`ai du mal a me concentrer sur les "x".
A demain et merci.

miq · 31-01-2014 00:26:11

j'ai relu ce que tu fait et voilà comment tu devrait le noter :
A=1 2
B=3 4
C=5 6
D=7 8
E=9 10
etc jusqu'à delta pour 50.

Le problème est donc de placer 3 lettres dans 10*10 cases sans que celle-ci ne se recoupent deux à deux dans une case, et que chacune soit une fois et une seule dans chaque ligne et colonne.
en taille 3 c'est impossible: on peut placer les deux séries de nombre, une horizontalement et l'autre verticalement puis les décaler sur les lignes suivantes, mais la troisième ne peut plus être placée.
AD BE CF
BF CD AE
CE AF BD
si ADG en 1.1, alors G en seconde ligne ne peut pas être en colonne 1, ni en colonne 2 (D) ni en colonne 3 (A) et le problème est symétrique avec les autres valeurs.
reste à généraliser à la taille 10 ou à trouver une solution de taille 10...

Bemo52 · 31-01-2014 00:46:03

miq a écrit :

j'ai relu ce que tu fait et voilà comment tu devrait le noter :
A=1 2
B=3 4
C=5 6
D=7 8
E=9 10
etc jusqu'à delta pour 50.
Le problème est donc de placer 3 lettres dans 10*10 cases sans que celle-ci ne se recoupent deux à deux dans une case, et que chacune soit une fois et une seule dans chaque ligne et colonne.
en taille 3 c'est impossible: on peut placer les deux séries de nombre, une horizontalement et l'autre verticalement puis les décaler sur les lignes suivantes, mais la troisième ne peut plus être placée.
AD BE CF
BF CD AE
CE AF BD
si ADG en 1.1, alors G en seconde ligne ne peut pas être en colonne 1, ni en colonne 2 (D) ni en colonne 3 (A) et le problème est symétrique avec les autres valeurs.
reste à généraliser à la taille 10 ou à trouver une solution de taille 10...

N`oublie pas que ce sont combinaisons de 5 et pas de 6 numeros.
Mon idee tient la route :
Placer les couples (lire plus haut) d`abord.
Je l`ai fait.
Il me reste a resoudre une sorte de sudoku (10 au lieu de 9).
Sur chaque ligne je dois placer les numeros de 41 a 50. Idem en colonne.
La contrainte est d`eviter qu`un couple ne soit associe au meme numero 2 fois, ce qui donnerait 2 fois 3 numeros (on cherche 2 et moins en commun entre les 5-uplets).
Je resoudrai cela dans moins de 2 jours (je serai occupe ailleurs demain).

miq · 31-01-2014 00:54:08

la première colonne est évidente.
la seconde colonne est un décalage de la première, d'un cran pour la première lettre pour l'unicité de ligne, de 2 crans pour la seconde pour l'unicité de BL et de 3 crans pour la troisième pour les unicités de BV et MW
la troisième colonne est un décalage de la première, de 2 crans pour la première lettre (unicité dans la ligne), de 1 cran pour la seconde ligne, et pour la troisième, ni U(col1), ni V(LV), ni W(CW), ni X(col2), ni Y(CY), Z
voilà le principe, mais j'ai peur qu'il n'y ait pas de solutions à cause de l'unicité des couples associés à la troisième variable (la cinquième avec une contrainte de 2 identiques max)

Après j'ai pris le partit de décaler les lignes entières, peut-être que la solution nécessite un mélange plus irrégulier dans les colonnes.

AKU BMX CLZ DPV ERd FNW G
BLV CNY DMa EQW FSU GOX H
CMW DOZ ENb FRX GTV HPY I
DNX EPa FOc GSY HKW IQZ J
EOY FQb GPd HTZ ILX JRa A
FPZ GRc HQU IKa JMY ASb B
GQa HSd IRV JLb ANZ BTc C
HRb ITU JSW AMc BOa CKd D
ISc JKV ATX BNd CPb DLU E
JTd ALW BKY COU DQc EMV F

au stade calculé, aucune lettre ne convient pour aller avec un G en première ligne.
Après, j'ai pris la première solution de décalage que j'ai trouvée pour chaque lettre de chaque colonne. Il faudrait parcourir l'arbre de toutes les solutions et de leurs conséquences pour être sûr.

Dernière modification par miq (31-01-2014 01:08:10)

Bemo52 · 31-01-2014 00:55:25

Tableau a completer : il faut placer les numeros de 41 a 50 dans chacune des 5emes colonnes.
Les placer selon les contraintes citees plus haut.
Imprime-le et essaie de completer comme un sudoku traditionnel.

http://hpics.li/49323d1

Bemo52 · 31-01-2014 00:57:39

Jette un coup d`oeil au tableau et tu saisiras ce dont je parle.

miq · 31-01-2014 01:12:16

oui, et on a ajouté une autre contrainte aussi avec cette méthode, c'est que les solutions n'ont pas nécessairement besoin d'être partitionnées en sous-segments de 2. Rien ne dit que cette contrainte supplémentaire ne réduit pas les possibilités de solutions.

miq · 31-01-2014 08:31:17

En fait ton tableau est un carré bilatin auquel on veut ajouter une troisième variable. C'est la même chose que j'ai détaillé mais en construisant au fur et à mesure le niveau 3 au lieu de le faire après avoir fini le niveau 2.
Ta méthode part d'une sous solution possible, un des carrés bilatin 10 existant. Si elle ne fonctionne pas il faudrait tester les autres bilatins 10 possibles.

Dernière modification par miq (31-01-2014 08:57:21)

yoshi · 31-01-2014 11:15:00

Salut,

miq a écrit :

En fait ton tableau est un carré bilatin

Bilatin est l'autre nom (originel) du carré gréco-latin, petite précision pour Bemo52.
Cf les deux liens que j'ai déjà donné :
http://www.bibmath.net/carres/index.php … uler_magie
http://fr.wikipedia.org/wiki/Carr%C3%A9 … A9co-latin

J'ai encore trouvé ça :
http://images.math.cnrs.fr/spip.php?pag … ument=5165
visiblement inspiré de cette création (p 15) :
http://www-irma.u-strasbg.fr/~maudin/ExposeRennes.pdf
Peut-être "suffirait"-il de rajouter la couleur du 1er à la grisaille du 2nd ?

@+

Bemo52 · 31-01-2014 12:11:49

Merci pour toutes les contributions.
Avec ma methode, je debouche sur l`irrespect d`une condition : les 100 combinaisons prises 2 a 2 partagent au plus 3 numeros (et non 2 comme demandes).
Je liste :

7 8 31 32 41
13 14 21 22 42
17 18 25 26 43
1 2 29 30 44
5 6 23 24 45
11 12 33 34 46
15 16 27 28 47
9 10 37 38 48
3 4 35 36 49
19 20 39 40 50
9 10 33 34 48
17 18 27 28 43
3 4 31 32 49
7 8 25 26 41
13 14 35 36 42
19 20 29 30 50
11 12 37 38 46
5 6 39 40 45
1 2 21 22 44
15 16 23 24 47
11 12 35 36 46
5 6 33 34 45
9 10 27 28 48
15 16 39 40 47
1 2 31 32 44
13 14 37 38 42
7 8 21 22 41
3 4 23 24 49
19 20 25 26 50
17 18 29 30 43
13 14 39 40 42
11 12 29 30 46
19 20 21 22 50
3 4 33 34 49
15 16 37 38 47
9 10 23 24 48
5 6 25 26 45
1 2 27 28 44
17 18 31 32 43
7 8 35 36 41
15 16 21 22 47
1 2 23 24 44
5 6 35 36 45
19 20 37 38 50
11 12 25 26 46
7 8 27 28 41
3 4 29 30 49
17 18 33 34 43
9 10 39 40 48
13 14 31 32 42
19 20 23 24 50
7 8 39 40 41
1 2 37 38 44
13 14 27 28 42
9 10 29 30 48
5 6 31 32 45
17 18 35 36 43
11 12 21 22 46
15 16 33 34 47
3 4 25 26 49
1 2 25 26 44
3 4 37 38 49
15 16 29 30 47
11 12 31 32 46
7 8 33 34 41
17 18 39 40 43
13 14 23 24 42
19 20 35 36 50
5 6 27 28 45
9 10 21 22 48
3 4 27 28 49
19 20 31 32 50
13 14 33 34 42
9 10 35 36 48
17 18 21 22 43
15 16 25 26 47
1 2 39 40 44
7 8 29 30 41
11 12 23 24 46
5 6 37 38 45
5 6 29 30 45
15 16 35 36 47
11 12 39 40 46
17 18 23 24 43
19 20 27 28 50
3 4 21 22 49
9 10 31 32 48
13 14 25 26 42
7 8 37 38 41
1 2 33 34 44
17 18 37 38 43
9 10 25 26 48
7 8 23 24 41
5 6 21 22 45
3 4 39 40 49
1 2 35 36 44
19 20 33 34 50
15 16 31 32 47
13 14 29 30 42
11 12 27 28 46

Ma methode ne marche donc pas pour l`instant.
Un peu de repos et on abordera de nouveau sous un nouvel angle.

Merci.

Bemo52 · 31-01-2014 12:59:52

Je pense finalement que ma methode peut repondre a la contrainte au plus 2 elements en commun.
Cela demandera du temps car je le fais manuellement.

Bemo52 · 31-01-2014 13:04:07

miq a écrit :

oui, et on a ajouté une autre contrainte aussi avec cette méthode, c'est que les solutions n'ont pas nécessairement besoin d'être partitionnées en sous-segments de 2. Rien ne dit que cette contrainte supplémentaire ne réduit pas les possibilités de solutions.

Oui. C`est vrai que ma methode reduit le nombre de solutions en passant par le decoupage des 50 numeros en couples.
Avec la methode force brute ce serait plus fastidieux je pense.
Je suis optimiste pour le moment.
J`y arriverai.
Je laisse decanter un ou 2 jours.

Forum de mathématiques - Bibm@th.net

#1 29-01-2014 17:35:07

Combinaisons a placer dans un tableau

#2 29-01-2014 21:23:17

Re : Combinaisons a placer dans un tableau

#3 30-01-2014 09:41:26

Re : Combinaisons a placer dans un tableau

#4 30-01-2014 09:48:45

Re : Combinaisons a placer dans un tableau

#5 30-01-2014 10:17:18

Re : Combinaisons a placer dans un tableau

#6 30-01-2014 10:41:05

Re : Combinaisons a placer dans un tableau

#7 30-01-2014 13:09:45

Re : Combinaisons a placer dans un tableau

#8 30-01-2014 13:35:16

Re : Combinaisons a placer dans un tableau

#9 30-01-2014 14:13:43

Re : Combinaisons a placer dans un tableau

#10 30-01-2014 17:06:50

Re : Combinaisons a placer dans un tableau

#11 30-01-2014 17:33:12

Re : Combinaisons a placer dans un tableau

#12 30-01-2014 20:12:03

Re : Combinaisons a placer dans un tableau

#13 31-01-2014 00:10:04

Re : Combinaisons a placer dans un tableau

#14 31-01-2014 00:10:30

Re : Combinaisons a placer dans un tableau

#15 31-01-2014 00:26:11

Re : Combinaisons a placer dans un tableau

#16 31-01-2014 00:46:03

Re : Combinaisons a placer dans un tableau

#17 31-01-2014 00:54:08

Re : Combinaisons a placer dans un tableau

#18 31-01-2014 00:55:25

Re : Combinaisons a placer dans un tableau

#19 31-01-2014 00:57:39

Re : Combinaisons a placer dans un tableau

#20 31-01-2014 01:12:16

Re : Combinaisons a placer dans un tableau

#21 31-01-2014 08:31:17

Re : Combinaisons a placer dans un tableau

#22 31-01-2014 11:15:00

Re : Combinaisons a placer dans un tableau

#23 31-01-2014 12:11:49

Re : Combinaisons a placer dans un tableau

#24 31-01-2014 12:59:52

Re : Combinaisons a placer dans un tableau

#25 31-01-2014 13:04:07

Re : Combinaisons a placer dans un tableau

Pied de page des forums