Trouver les bonnes combinaisons

Rudy · May 2006

Bonjour,

Pourquoi PROBA ? (je m'adresse aux modérateurs)
En mettant PROBA vous allez faire fuir ceux qui n'aime pas les probabilités.
Or, pour moi, ce problème ne relève pas des probabilités, donc vous lui donnez peu de chance d'être résolu (je ne saurais toutefois pas en donner la probabilité exacte :-)
Cela dit, on peut franchement supprimer mon premier post puisque mon problème est reformulé plus précisément ici.

Je reformule donc mon problème (qui est directement lié à un autre problème célèbre, beaucoup plus concret celui-là).

A partir des trois lettres AOZ je cherche tous les n-uplets formés avec répétitions, auxquels je retire le n-uplet qui n'est formé qu'avec des O. Pour n=3, il y a donc 26 possibilités (voir plus loin). Ensuite mon problème est de connaître pour chaque n le nombre max de n-uplets que je peux mettre en colonne telle que celle-ci présente alors elle-même n colonnes possédant chacune le même nombre de A et de Z.

Par exemple, pour n=3 nous avons les 26 triplets suivants :

AAA ZAA OAA
AAZ ZAZ OAZ
AAO ZAO OAO
AZA ZZA OZA
AZZ ZZZ OZZ
AZO ZZO OZO
AOA ZOA OOA
AOZ ZOZ OOZ
AOO ZOO

Et il se fait que nous pouvons y extraire au maximum 12 triplets, comme en voici un exemple :

AAZ
AAO
AZA
ZAA
ZAO
ZOZ
AOZ
ZOO
OZZ
OZA
OZO
OOA

Où l'on peut constater que chacune des 3 colonnes possède le même nombre de A et de Z (ici 4A et 4Z).
Quel est donc le lien entre ce nombre max de n-uplets et n lui-même ?

A+
Rudy

Rudy · May 2006

Bonjour,

Pourquoi PROBA ? (je m'adresse aux modérateurs)
En mettant PROBA vous allez faire fuir ceux qui n'aime pas les probabilités.
Or, pour moi, ce problème ne relève pas des probabilités, donc vous lui donnez peu de chance d'être résolu (je ne saurais toutefois pas en donner la probabilité exacte :-)
Cela dit, on peut franchement supprimer mon premier post puisque mon problème est reformulé plus précisément ici.

Je reformule donc mon problème (qui est directement lié à un autre problème célèbre, beaucoup plus concret celui-là).

A partir des trois lettres AOZ je cherche tous les n-uplets formés avec répétitions, auxquels je retire le n-uplet qui n'est formé qu'avec des O. Pour n=3, il y a donc 26 possibilités (voir plus loin). Ensuite mon problème est de connaître pour chaque n le nombre max de n-uplets que je peux mettre en colonne telle que celle-ci présente alors elle-même n colonnes possédant chacune le même nombre de A et de Z.

Par exemple, pour n=3 nous avons les 26 triplets suivants :

AAA ZAA OAA
AAZ ZAZ OAZ
AAO ZAO OAO
AZA ZZA OZA
AZZ ZZZ OZZ
AZO ZZO OZO
AOA ZOA OOA
AOZ ZOZ OOZ
AOO ZOO

Et il se fait que nous pouvons y extraire au maximum 12 triplets, comme en voici un exemple :

AAZ
AAO
AZA
ZAA
ZAO
ZOZ
AOZ
ZOO
OZZ
OZA
OZO
OOA

Où l'on peut constater que chacune des 3 colonnes possède le même nombre de A et de Z (ici 4A et 4Z).
Quel est donc le lien entre ce nombre max de n-uplets et n lui-même ?

A+
Rudy

Alain Debreil · May 2006

Bonsoir Rudy

<< Pourquoi PROBA ? (je m'adresse aux modérateurs) >>

J'ai mis Proba, parceque cela me semble être un exercice de dénombrement !

<< En mettant PROBA vous allez faire fuir ceux qui n'aime pas les probabilités.
Or, pour moi, ce problème ne relève pas des probabilités, donc vous lui donnez peu de chance d'être résolu >>

Tu laisses sous-entendre que les personnes appréciant les probabilités ne sont pas capables de résoudre ton problème ?

Bref que proposes-tu comme thème ?

Alain

Alain Debreil · May 2006

Bonsoir Rudy

<< Pourquoi PROBA ? (je m'adresse aux modérateurs) >>

J'ai mis Proba, parceque cela me semble être un exercice de dénombrement !

<< En mettant PROBA vous allez faire fuir ceux qui n'aime pas les probabilités.
Or, pour moi, ce problème ne relève pas des probabilités, donc vous lui donnez peu de chance d'être résolu >>

Tu laisses sous-entendre que les personnes appréciant les probabilités ne sont pas capables de résoudre ton problème ?

Bref que proposes-tu comme thème ?

Alain

Rudy · May 2006

C'est vrai qu'il n'est pas simple ce problème. Et en plus j'ai oublié une restriction : parmi les n-uplets trouvés il ne peut pas y en avoir deux symétriques. J'appelle symétriques les n-uplets suivants :
AOZ et ZOA
OAZZ et OZAA ...
Où le Z se substitue au A et inversément. Le O reste O.

Je demande juste une idée que je porrais exploiter.

Rudy

Rudy · May 2006

<< En mettant PROBA vous allez faire fuir ceux qui n'aiment pas les probabilités.
Or, pour moi, ce problème ne relève pas des probabilités, donc vous lui donnez peu de chance d'être résolu >>

Tu laisses sous-entendre que les personnes appréciant les probabilités ne sont pas capables de résoudre ton problème ? (Alain plus haut)

Bien sûr que non, je laisse simplement entendre que l'on se prive inutilement de ceux (tout de même nombreux) qui n'aiment pas trop les proba.

Voilà ;-)

[Soit, je retire le thème ! AD]

Rudy · May 2006

Bonjour, revoici mon problème mieux formulé.

Voici la liste des 26 triplets formés avec les lettres A, O et Z (avec répétition). En fait, il y en a 27 mais nous avons enlevé le triplet ZZZ.

AAA ZAA OAA
AAZ ZAZ OAZ
AAO ZAO OAO
AZA ZZA OZA
AZZ ZZZ OZZ
AZO ZZO OZO
AOA ZOA OOA
AOZ ZOZ OOZ
AOO ZOO

Voici ces triplets disposés par paires de triplets symétriques :

AAA et ZZZ
AAZ et ZZA
AAO et ZZO
AZA et ZAZ
AZZ et ZAA
AZO et ZAO
AOA et ZOZ
AOZ et ZOA
AOO et ZOO
OAA et OZZ
OAZ et OZA
OAO et OZO
OOA et OOZ On aura compris que dans mon esprit pour trouver le n-uplet symétrique à un n-uplet donné, il faudra y remplacer le A par Z et le Z par A, tout en laissant le O à sa place.

A partir de là, je dois trouver le maximum de triplets dans cett liste, dont deux d’entre eux ne sont jamais symétriques et qui répondent à la condition donnée plus loin. Par exemple, je retiendrai les triplets suivants :

...... et ......
AAZ et ......
AAO et ......
AZA et ......
...... et ZAA
...... et ZAO
...... et ZOZ
AOZ et ......
...... et ZOO
...... et OZZ
...... et OZA
...... et OZO
OOA et ......

J'ai donc retenu :

AAZ
AAO
AZA
ZAA
ZAO
ZOZ
AOZ
ZOO
OZZ
OZA
OZO
OOA
parce que l'on peut constater ci-dessus que chaque colonne y possède le même nombre de A que de Z.

Quelle méthode me permettrait de résoudre ce problème et qui me dit qu'il n'existe pas une liste de 13 triplets qui fasse aussi l'affaire ?
Pareil avec les n-uplets formés des trois même lettres (avec répétition).

Rudy

Domi · May 2006

Bonjour Rudy,

je ne suis pas sûr d'avoir bien compris ton problème . Soit dit en passant , j'aurais plutôt disposé les n-uplets en ligne pour une plus grande lisibilité :

AAAZZZAZOOOO : 4A , 4O et 4Z
AAZAAOOOZZZO : 4A , 4O et 4Z
ZOAAOZZOZAOA : 4A , 4O et 4Z

Veux-tu que sur chacune de tes colonnes ( lignes pour moi ) il y ait toujours le même nombre de A et de Z ? Autrement dit ce nombre dépend-il ou non de la colonne ?

Domi

Rudy · May 2006

C'est exactement ça Domi.
Je veux qu'il y ait autant de A que de Z -comme tu l'as indiqué- parmi le plus grand nombre de triplets qui sont des arrangements avec répétition des trois lettres A,O et Z. En n'oubliant pas toutefois que parmi lesdits arrangements ou triplets on ne peut trouver par ex AZO et ZAO, que je dis symétriques.
Ce qui m'intéresse, c'est le problème général : quel est le plus grand nombre de n-uplets (toujours avec le même nombre de A et de Z comme indiqué plus haut) étant des arrangements avec répétitions des trois lettres A,O et Z. Où l'on ne peut trouver p ex AOZZO et ZOAAO (pour des 5-uplets).

A+

Rudy

... · May 2006

Je dois dire que je suis un peu d'accord avec Rudy.
Même si ce problème est en quelque sorte un problème de proba, c'est dommage de mélanger le dénombrement aux proba.

Il m'arrive souvent quand je ne suis pas motivé de ne pas regarder la partie proba alors que ce genre de problème me plait beaucoup

C'est peut-être trop réducteur d'avoir fait une case proba
et d'y mettre les problèmes de dénombrements.

Domi · May 2006

Bonjour Rudy,

Je suis sûrement bouché mais la phrase même nombre de A et de Z sur chaque colonne n'est pas claire pour moi . Veut-elle dire ?

1°) Sur chacune des colonnes le nombre de A est égal au nombre de Z .

ex :

AA0 ...
A0A ...
Z00 ...
ZZZ ...

2°) Même nombre de A sur chacune des colonnes et même nombre de Z sur chacune des colonnes .

ex :

AZA ...
ZAZ ...
ZZZ ...

3°) Un nombre identique de A sur chaque colonne et un nombre identique de Z sur chaque colonne .

ex :

AZA ...
AAZ ...
ZZZ ...
ZAA ...

Si c'est la dernière proposition qui est la bonne , dans le cas des triplets , 12 est clairement un maximum . Je prends la disposition en ligne pour la suite ( tu ne m'as donné ton avis à ce propos ) . Par l'absurde , supposons qu'il existe une disposition de plus de douze triplets avec tes contraintes . En observant les triplets ci-dessous , on peut dire que chaque ligne ne peut pas contenir plus de quatre O :

O OO OO OO OO
O OO AZ AZ OO
O AZ OO AZ ZA

Chaque ligne contient donc au moins cinq A et cinq Z

Il y a en tout neuf triplets dont le premier élément est A et neuf dont le premier élément est Z . Si on dispose cinq A sur la première ligne , on élimine par symétrie cinq des éléments dont le premier élément est Z et on ne peut pas disposer cinq Z sur la première ligne : contradiction .

En attendant ta réponse pour les deux questions posées,

A+ Domi

Jules Renucci · May 2006

Rudy, bonjour

Je te livre ce résultat ne sachant s'il pourra t'aider :

Les 27 triplets ( soit n^3) obtenus par permutation circulaire se présentent sur 9 lignes de la manière suivante :

AOZ AOA AOO
AZZ AZA AZO
AAZ AAA AAO
OOZ OOA OOO
OZZ OZA OZO
OAZ OAA OAO
ZOZ ZOA ZOO
ZZZ ZZA ZZO
ZAZ ZAA ZAO
Tu remarques que ces 9 lignes sont deux a deux symétriques (les triplets de l'une sont les symétriques des triplets de l'autre)
Il en est ainsi pour les lignes (1,7) (3,8) (2,9) (5,6)
la ligne 4 portant les deux symétriques OOZ et OOA
Pour n=3 (impair) on obtient n(n^2-1)/2 +1
On doit pouvoir généraliser.
cordialement

Rudy · May 2006

Domi,

Plus haut j'ai écrit :

AAZ
AAO
AZA
ZAA
ZAO
ZOZ
AOZ
ZOO
OZZ
OZA
OZO
OOA
parce que l'on peut constater ci-dessus que chaque colonne y possède le même nombre de A que de Z.

On ne peut s'exprimer plus simplement. C'est donc ton point 1° qui prévaut. Pour la disposition en ligne, tu as bien sûr raison c'est beaucoup mieux.

Rudy

Domi · May 2006

Rudy , le problème est que ton exemple est aussi en accord avec ma 3ème proposition , tu confirme bien que c'est la première qui est la bonne ?

Domi

Rudy · May 2006

J'aime beaucoup ton idée Jules.
Toutefois, tu vas me trouver idiot mais je ne comprends pas la ligne :
Pour n=3 (impair) on obtient n(n^2-1)/2 +1

Amicalement

Rudy

Rudy · May 2006

Je confirme mon bon Domi : y a des jours tu es complètement bouché :-)))

Je confirme aussi que ton point trois m'est tout à fait étranger, à savoir : Un nombre identique de A sur chaque colonne et un nombre identique de Z sur chaque colonne.

A+

Rudy

Jules Renucci · May 2006

Rudy tu as raison, j'ai écrit dans l'urgence sans trop réfléchir!
Je voulais simplement exprimer que le nombre des triplets cherchés était
moitié du total des triplets.
Il suffit de pouvoir calculer le nombre total de triplets possibles qui est en l'occurence 3^3
Dans le cas général ,ce nombre n'est-il pas n^n ? 5^5 pour les quintuplets?
La meilleure présentation des n-uplets me semble être le tableau sur n^2 lignes

bien cordialement

Domi · May 2006

Rudy , la langue nous joue des tours ,

point 3°) ; Même nombre "n" de A sur chaque colonne et même nombre "n" de Z sur chaque colonne .

Désolé mais j'aimerais bien être sûr de ce point avant de poursuivre car si c'était 3°) la bonne définition , j'aurais plein d'idées , la 1°) ne m'inspirant guère .

Je ne fais pas du harcèlement , bouché mais pas mal embouché

)

Domi

Domi · May 2006

Toujours sous l'hypothèse 3°) , en appliquant le même type de raisonnement que pour les triplets , il semblerait qu'un majorant de l'ensemble des n-uplets réalisant les contraintes soit :

$\frac{3^n-1}{2}$ si $n$ est pair .
$\frac{3^n-3}{2}$ si $n$ est impair .

Il reste à exhiber ( si possible ) un cas réalisant cette condition .

Domi

Rudy · May 2006

Désolé Domi, mais c'est le point 1° qu'il faut respecter. Il ne m'inspire pas trop non plus. Toutefois je connais maintenant la formule recherchée (1) et qui est
(3expn)-3 / 2 , c-à-d exactement ce que tu as écrit pour n impair.
Amusant non ?

(1) Je la connaissais dès le départ, mais sans aucun mérite. Ma question est : comment y parvenir ?

A+

Jules Renucci · May 2006

Pour RUDY et DOMI

Bonjour
Rudy, je pense pouvoir répondre à ta question:

Le résultat $\frac{3^n-1}{2}$ n’est pas un majorant mais la valeur réelle du nombre de n-uplets vérifiant la condition proposée par Rudy.
En effet, à partir des 3 lettres A,O,Z, le nombre de n-uplets possibles est $3^n$ qui est impair.
(on pourra toujours présenter ces n-uplets sur un tableau comportant $3^2=9$ lignes et $3^{n-2}$ colonnes)
Chacune des lettres A,O,Z figure $3^{n-1}^$ fois dans l’ensemble des n-uplets.
Toute permutation de deux lettres conserve l’ensemble des n-uplets.
Par exemple, la permutation (A,Z) transforme chaque n-uplet en son symétrique au sens de Rudy . Le n-uplet (O,O,O,……O) est transformé en lui-même.
(De même d’ailleurs que les permutations (A,O) ou (O,Z) avec pour invariant, respectivement (Z,Z,Z …..Z) ou (A,A,A...A)
Chaque n-uplet ayant donc son symétrique unique et réciproquement tout n-uplet étant le symétrique d’un n-uplet unique il y a donc $N=\frac{3^n-1}{2}$ n-uplets répondant aux conditions et cela que n soit pair ou impair.
Ce qui donne pour N les valeurs 2,4,13, 40, 121 … pour les valeurs 1,2,3,4,5 respectives de n.
Bien cordialement

Jules

Jules Renucci · May 2006

J’ajoute qu’une généralisation est possible en prenant $p$ lettres ou éléments et en cherchant les n-uplets qui répondent à la condition de symétrie par une permutation de deux lettres.
La valeur obtenue sera : $N=\frac{p^n-(p-2)^n}/{2}$

Jules

Pierre J · May 2006

Bonjour Jules, Rudy, Domi, et tout le monde

Rudy, dans ta re-formulation du 05-26-06 01:27, du parles de retirer le triplet ZZZ, alors qu'en réalité tu retire le triplet OOO.

Puis tu introduis une symétrie entre A et Z.

Le résultat n'est pas le même selon que tu retire ZZZ ou OOO! (me semble-t-il)

C'était juste pour être sûr que tout le monde parle de la même chose...

A+,
Pierre

Jules Renucci · May 2006

Pierre salut

En fait Rudy n'a pas besoin de "retirer" un quelconque triplet. Le nombre total de triplet est bien 3^3=27 y compris les triplets AAA,ZZZ et OOO
Si tu introduis la permutation (A,Z) c'est le triplet OOO qui demeure invariant, de même les triplets AAA et ZZZ pour les permutations respectives (O,Z) et (O,A)
L'ensemble des 27 triplets est symétrique (au sens de Rudy)pour chacune des 3 permutations possibles.
On obtient donc (3^3-1)/2 triplets vérifiant la condition de Rudy
Je crois avoir donné la solution à 8h50!

Domi · May 2006

Jules,

En tant que boulet de service sur ce fil , puis-je te demander quelques explications sur ta méthode .

les 9 lignes de n-uplets sont faites je suppose en prenant pour les deux premiers éléments , OO , OA , OZ , AO , AA , AZ , ZO , ZA , ZZ ( jusque là , ça va ) . Après , il me semble que le nombre d'apparitions de chaque lettre dans l'ensemble des n-uplets est $n.3^{n-1}$ et non pas $3^{n-1}$ . Pour la suite , je ne suis pas convaincu qu'un n-uplet solution soit transformé en une nouvelle solution par la symétrie (O, A) , le nombre de O pouvant être distinct du nombre de A . Pour finir , je ne vois pas comment tu comptes les solutions . En fin de compte , je ne comprends pas grand chose , si tu pouvais m'expliquer un peu ?

Domi

Jules Renucci · May 2006

Domi, salut.
Boulet de service dis-tu? allons donc! Bon j'essaye de répondre :

Restons aux triplets et construisons les de la manière suivante

A A A

O O O

Z Z Z

on distribue les éléments de la première colonne à chacun des éléments de la deuxième colonne ce qui donne

AA
AO
AZ
OA
OO
OZ
ZA
ZO
ZZ
Chacun de ces duplets est ensuite distribué à chacun des éléments de la troisième colonne, d'où
AAA AAO AAZ
AOA AOO AOZ
AZA AZO AZZ
OAA OAO OAZ
OOA OOO OOZ
OZA OZO OZZ
ZAA ZAO ZAZ
ZOA ZOO ZOZ
ZZA ZZO ZZZ
On obtient ainsi les 3^3=27triplets
Tu peux constater l'équirépartition des lettres A,O,Z, ce qui est tout à fait logique étant donné qu'elles sont permutables (il ny a aucune raison à ce qu'il y ait plus de O que de A ou de Z). Chaque lettre est donc représentée $3^3$ fois Dans le cas d'un n-uplet de sera$3^n$ et non $3^{n-1}$ comme je l'ai écrit par erreur.
Un triplet quelconque parmi les 27 a un et un seul symétrique au sens de Rudy.
Par exemple le triplet ZAO a pour symétrique AZO et réciproquement
le triplet AOZ a pour symétrique le triplet ZOA
Le triplet OOO a pour symétrique le triplet OOO
Le triplet ZZZ a pour symétrique AAA etc.......
Il y a donc $\frac{3^3-1}{2}$ triplets répondant aux conditions de Rudy.
Dans le cas d'un n-uplet on aura $\frac{3^n-1}{2}$ solutions.

Bien cordialement

Jules

Domi · May 2006

Une petite réponse à Pierre avant de lire Jules ,

il me semble bien que c'est OOO que l'on supprime et pas ZZZ , ce doit être une faute de frappe , en effet , dans la liste qui suit c'est bien OOO qui c'est volatilisé .

Domi

Domi · May 2006

Merci Jules pour ta réponse,

je crois que je vais avoir du mal à te suivre dans ton raisonnement : "il n'y a aucune raison qu'il y ait plus de A que de Z " n'est pas équivalent à " il n'est pas possible qu'il y ait plus de A que de Z" . En fait si je t'ai bien compris , tu considères l'ensemble des n-uplets et tu retires les symétriques au sens de Rudy . Le problème est un peu plus compliqué que cela , non ?

Domi

Jules Renucci · May 2006

Domi c'est moi à présent qui ait l'impression d'être un boulet....

Pour les triplets, j'ai établi le tableau complet. Non???? manque -il des triplets à mon tableau ? Peux tu écrire un triplet qui n'y figure pas?
N'y a t-il pas autant de A que de O ou de Z ?
Cela n'est -il pas d'une logique parfaite? La distributivité d'une lettre par rapport aux deux autres n'est-elle pas symétrique et n'impose t-elle pas l'équirépartition ?

En quoi s'il te plait le problème est-il plus compliqué que ce que je perçois?

Merci d'avance pour ta réponse.

bien cordialement

Jules Renucci · May 2006

J'écris ci-dessous les 81 quadruplets. Je les écris de manière que le quadruplet OOOO occupe la position centrale du rectangle.
On remarquera que les symétriques sont opposés sur les diagonales passant par OOOO

AAAA AAAO AAAZ AAOA AAOO AAOZ AAZA AAZO AAZZ
AOAA AOAO AOAZ AOOA AOOO AOOZ AOZA AOZO AOZZ
AZAA AZAO AZAZ AZOA AZOO AZOZ AZZA AZZO AZZZ
OAAA OAAO OAAZ OAOA OAOO OAOZ OAZA OAZO OAZZ
OOAA OOAO OOAZ OOOA OOOO OOOZ OOZA OOZO OOZZ
OZAA OZAO OZAZ OZOA OZOO OZOZ OZZA OZZO OZZZ
ZAAA ZAAO ZAAZ ZAOA ZAOO ZAOZ ZAZA ZAZO ZAZZ
ZOAA ZOAO ZOAZ ZOOA ZOOO ZOOZ ZOZA ZOZO ZOZZ
ZZAA ZZAO ZZAZ ZZOA ZZOO ZZOZ ZZZA ZZZO ZZZZ

Rassurez vous je ne vais pas écrire les quintuplets!

jaybe · May 2006

Je suis assez surpris que personne n'ait proposé "combinatoire" (des mots) comme thème. Sinon, le cadre offert par $F_3^n$ en posant $A=1$ et $Z=2$ ne me semble pas trop mal adapté pour formaliser tout ceci !

Domi · May 2006

Jules ,
 
 je viens de passer une heure à tapper sur des fûts ce qui explique mon absence . Je voulais dire dans mon dernier post que Rudy demande deux choses . Je reprends l'exemple des triplets et la disposition en ligne , les triplets figurent donc sur les colonnes .
 
 Un exemple possible de douze triplets :
 
 AAAZZZAZOOOO : 4A et 4Z
 AAZAAOOOZZZO : 4A et 4Z
 ZOAAOZZOZAOA : 4A et 4Z
 
 Cet exemple est possible car aucune paire de triplet n'est symétrique , aucun triplet n'est OOO et sur chaque ligne , le nombre de A est identique au nombre de Z . Existe-t-il un exemple avec 13 triplets comme l'indique ta formule , j'en doute .
 Ceci dit il est vrai que les différentes formulations et autres changements de lignes et colonnes font que nous ne savons plus trop où nous en sommes : il serait bon de formaliser un peu tout cela .
 
 Domi

Jules Renucci · May 2006

Au temps pour moi ou, encore, autant pour moi!!!!

Je n'avais pas assimilé la deuxième condition qui impose un nombre égal de A et Z dans chacune des trois colonnes. Je remarque cependant que ce nombre égal est le même pour chaque colonne dans l'exemple que tu donnes :4Z et 4A pour chaque colonne

Tu as donc raison . (3^n-1)/2 est, pour l'instant, un majorant du nombre des triplets possibles.

Je vais donc m'y remettre

Domi · May 2006

Une proposition de reformulation que je propose à Rudy et aux autres :

$E_n$ , l'ensemble des n-uplets non nuls de $\Z/3\Z$ .

$x = (x_1;x_2;...;x_n)$ et $y = (y_1;y_2;...;y_n)$ deux éléments de $E_n$ sont dits symétriques si :$\forall i \in\{1;2;...n\}$ , $x_i+y_i = 0$ .

une partie $M = \{x^1;x^2;...;x^m\}$ de $E_n$ est acceptable si :
1°) $M$ ne contient pas deux éléments symétriques .
2°) $\forall i \in \{1;2;...;n\}$ , $Card {j \in \{1;2;...m \}/ x_i^j = 1\} = Card \{j \in {1;2;...m\} / x_i^j = 2\}$ .

Déterminer en fonction de $n$ le cardinal d'une partie acceptable maximale de $E_n$ .

Domi

Alain Debreil · May 2006

Une proposition de reformulation que je propose à Rudy et aux autres :

$E_n$ , l'ensemble des n-uplets non nuls de $\Z/3\Z$ .

$x = (x_1;x_2;\ldots ;x_n)$ et $y = (y_1;y_2;\ldots;y_n)$ deux éléments de $E_n$ sont dits symétriques si :$\forall i \in\{1;2;\ldots;n\} ,\ x_i+y_i = 0$ .

Une partie $M = \{x^1;x^2;\ldots ;x^m\}$ de $E_n$ est acceptable si :
1°) $M$ ne contient pas deux éléments symétriques.
2°) $\forall i \in \{1;2;...;n\} ,\ Card \{j \in \{1;2;...m \}\mid x_i^j = 1\} = Card \{j \in \{1;2;\ldots;m\} \mid x_i^j = 2\}$.

Déterminer en fonction de $n$ le cardinal d'une partie acceptable maximale de $E_n$ .

Domi

Domi · May 2006

Une proposition de reformulation que je propose à Rudy et aux autres :

$E_n$ , l'ensemble des n-uplets non nuls de $\Z/3\Z$ .

$x = (x_1;x_2;...;x_n)$ et $y = (y_1;y_2;...;y_n)$ deux éléments de $E_n$ sont dits symétriques si :$\forall i \in\{1;2;...n\}$ , $x_i+y_i = 0$ .

une partie $M = \{x^1;x^2;...;x^m\}$ de $E_n$ est acceptable si :
1°) $M$ ne contient pas deux éléments symétriques .
2°) $\forall i \in \{1;2;...;n\}$ , $Card \{j \in \{1;2;...m \}/ x_i^j = 1\} = Card \{j \in \{1;2;...m\} / x_i^j = 2\}$ .

Déterminer en fonction de $n$ le cardinal d'une partie acceptable maximale de $E_n$ .

Domi

PS : version Latex corrigé .

Domi · May 2006

Oui Jules ,
 
 pour le nombre De A et de Z qui est toujours 4 dans cet exemple , d'où le long échange avec Rudy : je voulais lui faire avouer que ce nombre était le même pour chaque colonne mais il n'a pas voulu en démordre le bougre . Le nombre de A et de Z est identique sur chaque colonne mais peut changer d'une colonne à l'autre .
 
 Domi

Rudy · May 2006

En fait, le nombre de A et de Z doit être identique sur chaque colonne et il n'y a pas deux triplets qui soient symétriques. Ca ce sont les seules conditions que je puisse imposer. Pour le reste, je ne suis pas sensé savoir si le nombre de A et de Z changera ou non d'une colonne à l'autre.
OK pour la reformulation.

Bonne continuation et pour rappel la solution est (3expn - 3) / 2
ce qui donne 12, 39 ...

Rudy

Rudy · June 2006

« Rudy, dans ta re-formulation du 05-26-06 01:27, du parles de retirer le triplet ZZZ, alors qu'en réalité tu retires le triplet OOO ». (Pierre)
Désolé, je devais bien sûr écrire OOO et non ZZZ.

Domi, voici la reformulation la plus simple que j’ai pu trouver :

Il faut trouver le maximum de matrices (x1 ; x2 ; x3 … xn) avec xi qui appartient à {-1 ; 0 ; 1} telles que
1°) la somme de ces matrices donne la matrice nulle.
2°) la somme de deux quelconques de ces matrices ne donne jamais la matrice nulle.

Par exemple pour n = 2 on ne peut trouver mieux que 3 matrices
(-1 ; 0)
( 1 ;-1)
( 0 ; 1)
ou encore
( 1 ; 1)
( 0 ;-1)
(-1 ; 0)

Voilà
A ce soir.

Domi · June 2006

Rudy ,

je crois en effet qu'il faut trouver la formulation la plus simple du problème avant d'essayer de le résoudre et la présentation matricielle est interéssante ( tu vas pouvoir demander à Alain de ranger ton sujet dans la rubrique "Algèbre"

) ) . Attention toutefois à ne pas se mélanger les indices . Pour $n$ donné nous cherchons une matrice de type $(n,m)$ , $M = (x_i^j)_{i = 1 \ à \ m}^{j = 1 \ à \ n}$ . On adopte la convention usuelle l'exposant correspond au numéro de ligne et l'indice au numéro de colonne et les $x_i^j$ sont des éléments de $\Z/3\Z$.
\begin{pmatrix}

x^1_1 & x^1_2 & \ldots & x^1_m \\
x^2_1 & x^2_2 & \ldots & x^2_m \\
\vdots & \vdots &\ddots & \vdots \\
x^n_1 & x^n_2 & \ldots & x^n_m

\end{pmatrix}

Les matrices acceptables sont celles qui vérifient les trois conditions :
\begin{enumerate}
\item Toutes les colonnes sont différentes et non nulles .
\item La somme de deux colonnes distinctes n'est jamais nulle .
\item Sur chaque ligne le nombre de 1 est égal au nombre de 2 .
\end{enumerate}
Il faut donc pour $n$ donné , déterminer le plus grand $m$ tel qu'il existe une matrice $(n,m)$ acceptable .

Domi

jaybe · June 2006

Une description équivalente du point 3 : $M 1_m = 0_n$, $1_m$ étant le vecteur de taille $m$ dont chaque coordonnée vaut 1.

Domi · June 2006

Non Jaybe ,

tu fais la même erreur que Rudy , "le même nombre de 1 et de 2 sur chaque ligne " n'est pas équivalent à "la somme des éléments de la ligne est égale à zéro" .

prendre par exemple la ligne : ( 1 ; 1 ; 1 ; 1; 2 ) qui vérifie ta condition 3°) sans remplir la condition initiale .

Domi

Domi · June 2006

Puisqu'il faut que quelqu'un se lance , une façon d'aborder les choses pour $n$ donné . On écrit la matrice à $n$ lignes et à $3^n-1$ colonnes constituée de toutes les colonnes distinctes et non nulles . La matrice vérifie les conditions 1. et 3. de ma reformulation . Reste à retirer les colonnes symétriques ( que l'on pourrait d'ailleurs plus justement appeler opposées ) sans détruire le nombre égal de 1 et 2 sur chaque ligne et c'est toute la difficuté . Par exemple il y a dans notre grande matrice $2^n$ colonnes sans zéro , peut-on partitionner cet ensemble en deux classes , chaque classe ne contenant jamais un élément et son opposé et dans chaque classe autant d'éléments ayant 1 en ième position que d'éléments ayant 2 en ième position . Il suffirait alors de supprimer toutes les colonnes d'une classe pour s'approcher de la matrice voulue .

C'est une approche possible , je ne suis pas sûr qu'elle aboutisse .

Domi

jaybe · June 2006

Ah oui, tiens ! Au taon pour moi.

Rudy · June 2006

Salut Domi,

Tout à fait bien ta dernière re-formulation (ainsi que ton approche).
Va donc pour la forme. Pour le fond sachant que m ne peut dépasser 3n-1 , et mieux encore, qu'il ne peut dépasser 3n-1 /2, je reste médusé devant le fait qu'il ne peut valoir 3n-1 /2 mais qu'il peut valoir (3n-1 /2)-1 c-à-d (3n-3 /2) (qui du coup devient le plus grand m).
Bonne recherche !

A+

Domi · June 2006

Rudy,

juste un petit coucou pour te dire que ce soir , c'est corvée de copies donc les matrices attendront un peu . Pour rebondir tout de même sur ta remarque , avec mon approche , une fois judicieusement rétirées les colonnes symétriques ( opposées ) , le retrait d'une seule colonne doit nous amener à la matrice maximale . La question du choix des colonnes à retirer n'est sûrement pas facile par exemple pour l'ensemble des colonnes ayant un seul élément non nul , le retrait des opposés casse nécessairement l'égalité entre le nombre de 1 et le nombre de 2 sur chaque ligne . Je n'en dis pas plus , le devoir m'attend mais si quelqu'un d'autre à des idées ( je n'aime pas trop les travaux en solo ) .

Domi

Domi · June 2006

Mon approche est à revoir la "grosse matrice" ne vérifiant absolument pas le point 3°) . Je vais essayer de la construire colonne par colonne en commençant par celles qui contiennent le plus de zéro .

Domi

Domi · June 2006

Bonjour Rudy et les autres ,

ma nouvelle stratégie semble être la bonne , à vérifier soigneusement toutefois ( avec moi , tout est possible ) . Je construis la matrice acceptable de dimension$(n,\frac{3^n-3}{2})$ par récurrence sur $n$ .

pour $n = 2$ , on vérifie facilement que la matrice ci-dessous convient :
\begin{pmatrix}

0 & 1 & 2 \\
1 & 2 & 0

\end{pmatrix}
On construit ensuite pas à pas les matrices suivantes en substituant de la façon suivante :

$0 \rightarrow 0,1,2$ ; $1 \rightarrow 1,2,0$ ; $2 \rightarrow 2,0,1$ .

J'obtiens par exemple au rang 3 :

\begin{pmatrix}

0 & 1 & 2 & 1 & 2 & 0 & 2 & 0 & 1\\
1 & 2 & 0 & 2 & 0 & 1 & 0 & 1 & 2

\end{pmatrix}

On complète la dernière ligne alternativement avec 0 , 1 , 2 en remarquant que chaque colonne apparaissant figure alors exactement 3 fois :

\begin{pmatrix}

0 & 1 & 2 & 1 & 2 & 0 & 2 & 0 & 1\\
1 & 2 & 0 & 2 & 0 & 1 & 0 & 1 & 2\\
0 & 0 & 0 & 1 & 1 & 1 & 2 & 2 & 2

\end{pmatrix}

On remarque ensuite que les 3 colonnes :

\begin{pmatrix}

1 & 1 & 0\\
1 & 1 & 0\\
1 & 1 & 0\\
\vdots & \vdots & \vdots\\
1 & 1 & 0\\
0 & 2 & 2

\end{pmatrix}

peuvent être ajoutées à la matrice pour obtenir une matrice à $\frac{3^n-3}{2}$ colonnes vérifiant les 3 conditions imposées .

ll reste à voir pourquoi il n'existe pas de matrice acceptable à $\frac{3^n-1}{2}$ colonnes .

Domi

Domi · June 2006

Deux petites remarques :
 
 
 <OL><LI>Dans la matrice que je propose ( donc à vérifier ) , la seule colonne qui ne figure pas et dont l'opposée ne figure pas non plus est la colonne de 1 ou de 2 ( ce n'est sûrement pas anodin ).
 </LI><LI>Le procédé est constructif mais comme je ne suis pas dans la tête de Rudy , je ne sais pas si cela à un intérêt .
 </LI></OL>
 
 Domi

Rudy · June 2006

Je n'ai pas eu le temps de lire ton post Domi, je me lèverai assez tôt demain pour m'y interesser. Toutefois je voulais absolument vous signaler la découverte que j'ai faite sur mon travail (quand celui-ci m'en a donner le loisir). Pour moi c'est un vrai rebondissement (et pour vous ?) :
pour n = 3, notre problème revient à chercher un maximum de nombres naturels -hormis 0 et deux nombres qui soient opposés- situés entre -13 et 13 (ceux-ci y compris), tels que la somme de ces nombres fassent 0!
Exemple : -1+3+2+4+9-8+10+6+5-7-12-11 = 0 et on ne peut faire mieux que 12 nombres -hormis 0 et deux nombres qui soient opposés- situés entre -13 et 13 (ceux-ci y compris) pour y arriver.

En fait 13 = (3expn -1) /2 avec n = 3, pour n=4 les nombres devront donc se situer entre -39 et 39, pour n=4 ...

Mon problème revient donc à démontrer quil y a au maximum (3expn -3) /2 nombres naturels -hormis 0 et deux nombres qui soient opposés- situés entre -(3expn -1) /2 et (3expn -1) /2 (ceux-ci y compris) tels que la somme de ces nombres fassent 0.

Amusant non ?

Rudy

Jules Renucci · June 2006

Rudy, bonjour
Voici une solution pour le 4-uplet. Je trouve 39 triplets(38 si l'on exclue le 4-uplet 0000.
Tu remarqueras la périodicité de chaque colonne
1e colonne : 13 (1),13(-1),13(0)
2ecolonne :13(1,0,-1)
3e colonne :alternance des triplets 000,111,- 1-1-1,000,111,-1-1-1,000,....
4e colonne : 12(1),12(-1) 15(0)
1 1 0 0
1 0 0 0
1 -1 0 0
1 1 1 0
1 0 1 0
1 -1 1 0
1 1 -1 0
1 0 -1 0
1 -1 -1 0
1 1 0 1
1 0 0 1
1 -1 0 1
1 1 1 1
-1 0 1 1
-1 -1 1 1
-1 1 -1 1
-1 0 -1 1
-1 -1 -1 1
-1 1 0 1
-1 0 0 1
-1 -1 0 1
-1 1 1 -1
-1 0 1 -1
-1 -1 1 -1
-1 1 -1 -1
-1 0 -1 -1
0 -1 -1 -1
0 1 0 -1
0 0 0 -1
0 -1 0 -1
0 1 1 -1
0 0 1 -1
0 -1 1 -1
0 1 -1 0
0 0 -1 0
0 -1 -1 0
0 1 0 0
0 -1 0 0
0 0 0 0
Cette remarque peut permettre de construire assez rapidement les n-uplets solutions. Elle montre aussi qu'il y a une solution avec des n-uplets ordonnés
Le tableau n'est pas très joli. Je ne sais pas comment on obtient les alignements.
Pour n=3 on obtient la solution ordonnée:
1 1 0
1 0 0
1 -1 0
1 1 1
-1 0 1
-1 -1 1
-1 1 -1
-1 0 -1
0 -1 -1
0 1 0
0 0 -1
0 -1 1
0 0 0

Trouver les bonnes combinaisons

Réponses

Bonjour!

Catégories

In this Discussion