Petite question innocente

[L.A.]

Bonjour à tous et à toutes.

Est-ce que vous connaitriez une matrice de format 43x43 constituée de 0 et de 1, dans laquelle toute ligne et toute colonne contient exactement 7 coefficients 1 (et donc 36 coefficients 0), et telle que, quand on compare deux lignes ou deux colonnes distinctes, elles ont exactement un coefficient 1 en commun ?

Si oui, est-ce que vous en connaitriez une qui soit symétrique ?

C'est une vraie question, je n'ai pas la réponse... Merci d'avance pour toute suggestion qui ferait avancer le schmilblick :zen:

[Cliffe]

Tu as besoin d'avoir une démonstration ?

[L.A.]

Tu as besoin d'avoir une démonstration ?

Bof, pas dans un premier temps, le résultat serait déjà interessant en soi, mais si tu as une méthode de construction qui se généralise aux tailles supérieures, ou une preuve qu'une telle matrice n'existe pas et qui se généralise éventuellement, ça m'intéresse aussi bien sûr :zen:

[Cliffe]

Tu peux coder un petit prg pour tester toutes les solutions possibles.

[L.A.]

Certes, même si le terme "petit programme" me semble un peu galvaudé (le nombre de matrices à examiner étant de l'ordre de 2^(43*43)). Comme j'aimerais vraiment être fixé sur l'existence ou pas de cette matrice, ça vaut peut-être le coup, mais je n'ai aucune idée de la durée du calcul (une heure, une demi-journée, un mois ?).

J'avais pensé à un programme un peu plus futé mais qui n'a pas atteint le but recherché :
- on remplit la première ligne de la matrice par [111111100...0]
- pour remplir les lignes suivantes, on examine les coefficients de gauche à droite : si un coefficient a déjà 7 fois "1" au-dessus de lui, on lui affecte "0" et on passe au suivant, sinon on lui affecte "1" et on place des "0" dans la ligne courante en dessous de chaque "1" de chacune des lignes qui contient un "1" au dessus du coefficient courant, puis on passe au suivant.
- on passe à la ligne suivante lorsque la ligne est pleine ou dès que 7 coefficients "1" ont été crées.

Visiblement la matrice construite ainsi est toujours symétrique (ce que je trouve déjà remarquable a priori :hein: ) mais certaines lignes et colonnes contiennent moins de 7 fois "1".

[Cliffe]

Ta pas un exemple de taille plus petite (10 x 10) ? Pour voir le temps de calcul.

[L.A.]

Je précise un peu le contexte : si est un entier et , je m'intéresse aux matrices nxn dont les lignes et colonnes sont formées de m fois "1" et (n-m) fois "0" et qui vérifient la contition que j'ai donnée.

Par exemple pour m=3, n=7


Si m-1 est une puissance d'un nombre premier, on a toujours une telle matrice en considérant le plan projectif (qui est de cardinal n) : on numérote ses points et ses droites et on pose

On a même une matrice symétrique en choisissant une bonne numérotation.

Le premier cas qui ne rentre pas dans ce cadre est donc m=7, n=43.

J'essaierai la méthode "bourrin" demain mais ça me semble déjà très très lourd (le nombre de tests par matrice est aussi assez conséquent).

[Cliffe]

Si tu pose les éléments de ta matrice :

[CENTER]








[/CENTER]

(tu peux ajouter les contraintes de symétries)

ta plus qu'à utiliser un solveur non linéaire (Excel) pour résoudre. Jsuis curieux de voir le temps de résolution.

[Matt_01]

Essaye un algorithme de ce type :
On s'intéresse seulement aux colonnes de chaque valeur (on prend donc la première ligne égale à (1,2,3,4,5,6,7), ce qui correspond aux 7 premières colonnes).
Et on construit la ligne suivante par :
On considère la première ligne et on recherche la valeur dans cette ligne ayant le moins d’occurrence dans l'ensemble des lignes, et on met cette valeur dans la ligne.
Ensuite on supprime les éléments de la première ligne des candidats potentiels et on passe à la seconde etc etc ...

Concretement ca donnerait :
On a un tableau T de taille 43 qui stocke les occurrences et on démarre de la matrice A de taille 43x7.
Pour i allant de 1 à 43 faire
U=[1 ... 43] (l'ensemble des valeurs qu'on peut donner).
k=1 (représente le nombre de la ligne que l'on veut trouver)
Pour j allant de 1 à 43 ou k>7 faire
S'il existe v dans la ligne j tq v appartient à U alors :
on choisit v égal à celui d'occurrence minimale dans T (on prend le plus petit si on a le choix).
on fait T(v)=T(v)+1
et A(i,k)=v
sinon rien

On vire tous les éléments des lignes contenant v de U.
finsi
k=k+1
fin pour
Si on ressort en n'ayant pas rempli totalement la ligne, on la remplit avec les éléments de U de plus petite occurrence.
fin pour



Pour m = 3 ca donne :

1 2 3
1 4 5
2 4 6
3 5 6
1 6 7
2 5 7
3 4 7


Je ne sais pas si cela fonctionne pour des valeurs de m plus grande, mais ca se tente !

[Cliffe]

m = 5 :

Code: Tout sélectionner

1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1
1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0
0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0
1 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0
1 0 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0 0 1 1 0 1 0 0 0 0 0 0
0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0
0 1 1 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 1
0 0 1 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1
0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 0
0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0
0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0
1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0
0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0
0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0
0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1
0 1 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 0 0 0

Apparemment c'est pas possible pour m = 7.

[L.A.]

Je crois aussi que ce genre de décomposition peux fonctionner pas trop mal (m=5, n=21, je ne l'ai vérifiée qu'à vue de nez mais je pense que la matrice est bonne)



mais pour le moment je n'arrive à rien pour m=7... serait-on en droit d'envisager d'en tirer certaines conjectures ? :doh:

Par permutations, on peut se ramener à la forme ci-dessus exceptée la région des 9 sous-matrices 4x4 en bas à droite, là où tout se joue. Grosso modo, il s'agit ensuite de d'y faire rentrer 9 matrices de permutation qui évitent les diagonales de zéros, et qui s'évitent aussi l'une l'autre. On ne doit avoir nulle part quatre coefficients "1" qui forment un rectangle.

Autre piste, on peut dire aussi certaines choses sur les valeurs propres de ces matrices (en considérant le produit avec leur transposée qui est particulièrement simple).

Affaire à suivre... merci pour votre aide, en tout cas :zen:

[Cliffe]

Tu t'amuse à faire ça a la main ?? :p

J'ai utiliser Cplex perso.


Avec les contraintes de symétries :

Code: Tout sélectionner

0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 0 0
0 0 1 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0
0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 1
1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0
0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1
0 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0
1 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0
1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0
0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0
0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 0 1 1 0 1 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 1 0
0 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0
1 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1
0 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1
1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0

[Cliffe]

m = 6 :

Code: Tout sélectionner

0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1
0 0 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0
0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0
0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0
0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0
0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0
1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 1 0 0 0 0 0
0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1
0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1
0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 1 0
1 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0
1 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1
0 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0
0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 1 1 0 0

[CENTER] [/CENTER]

[L.A.]

Tu t'amuse à faire ça a la main ?? :p

Oui, on ressent quand même plus facilement les choses que quand on attend qu'un ordi le fasse à sa place :zen: et puis j'ai un peu de mal à considérer un résultat comme solidement établi si tout ce qu'on a fait c'est constater qu'un programme ne termine pas... (à ce compte-la n'importe quel programme mal bâti et qui renvoie une erreur pourrait être considéré comme une preuve !).

Attention, je ne dénigre pas ce que tu as fait, au contraire, comme je n'ai pas l'habitude de me jeter tout de suite sur la programmation, tu abordes le problèlme sous un autre angle et c'est pas plus mal et même très bien.

Une autre question intéressante serait de savoir si toutes les matrices possibles pour m,n fixés se déduisent l'une de l'autre par permutations des lignes et des colonnes, ou pas...

[beagle]

"Une autre question intéressante serait de savoir si toutes les matrices possibles pour m,n fixés se déduisent l'une de l'autre par permutations des lignes et des colonnes, ou pas..."

a priori non, puisque pour un mème hemi-cadre du nxn (qs ta propre construction), tu as de multiples solutions différentes de ton carré (m-1)²x((m-1)²

[Cliffe]

c'est constater qu'un programme ne termine pas...

Il termine ... et me retourne qu'il n'a pas trouvé de solution.

[L.A.]

Il termine ... et me retourne qu'il n'a pas trouvé de solution.

C'est noté.

a priori non, puisque pour un mème hemi-cadre du nxn (qs ta propre construction), tu as de multiples solutions différentes de ton carré (m-1)²x((m-1)²

Pas si sûr qu'elles se déduisent pas les unes par permutations, même si le chemin peut être long (cf Rubiks cube). Attends un peu, je vais te trouver des exemples...

[beagle]

Pas si sûr qu'elles se déduisent pas les unes par permutations, même si le chemin peut être long (cf Rubiks cube). Attends un peu, je vais te trouver des exemples...

effectivement , sur ton m=5 on peut facilement permuter le machin en gardant le mème cadre.
faut voir si cela vient du carré de base 5-1=4
voir si sur du 6-1 ou 8-1 on garde ces possibilités, car les 4k sont hachement symétricasable, donc pliables et dépliables, les impairs premiers sont plus sauvages ...

[beagle]

essai:
00100000100100000001
00010000010010010000
00001100000001001000
10000010000000100100
01000001001000000010
.....
01000000010010000010
00100100000001000001
00010010000000110000
00001001001000001000
10000000100100000100
.............
00010001000000101000
00001000101000000100
10000000010100000010
01000100000010000001
00100010000001010000
.............
00001010000001000100
10000001000000100010
01000000101000000001
00100000010100010000
00010100000010001000
...............

[beagle]

essai2:
00100010000001000001
00010100000000100100
00001000100100010000
10000000010010001000
01000001001000000010
..............
00010000010010001000
00001001000001010000
01000100000000100010
00100010001000000001
10000000100100000100
..............
01000001000000100010
10000000100010000001
00010000011000001000
00001100000100000100
00100010000001010000
...............
00001000100100000100
00100000011000000010
10000010000001000001
01000001000000110000
00010100000010001000
..............