Posté le: Mer 06 Juil 2005 12:21 Sujet du message: pour changer un peu les idées
Quel est le nombre maximal de sous ensembles d'un ensemble S de N éléments que l'on peut définir avec les conditions suivantes.
1. Chaque sous ensemble a au moins 2 éléments
2. L'intersection de deux sous ensembles distincts est toujours soit vide, soit un singleton. _________________ I long to accomplish great and noble tasks, but it is my chief duty to accomplish humble tasks as though they were great and noble.
The world is moved along, not only by the mighty shoves of its heroes, but also by the aggregate of the tiny pushes of each honest worker.
Posté le: Mer 06 Juil 2005 17:58 Sujet du message:
Salut man,
Tu es back du pays avec des exos trongs ou quoi ?
Je propose l'approche préconisée lors d'examens oraux;je commence à regarder les petites valeurs de N .
**Pour N=2 ,il y'a un seul ensemble,S lui même !
**Pour N=3 ,S={a,b,c},il y'a trois sous ensembles de 2 élements à savoir {a,b},{a,c},{b,c} et S.
Les trois sous ensembles à deux éléments satisfont les hypothèses, le nombre maximal ne pouvant être 4,il vaut donc 3 et l'ensemble formé des sous-ensembles à deux éléments satisfait aux hypothèses de départ !
**Pour N=4 ,S={a,b,c,d }
-Il y'a C(2,4)=6 sous-ensembles à deux élements,soit {a,b},{a,c},{a,d},{b,c},{b,d},{c,d}
- il y'a C(3,4)=4 sous-ensembles à 3 éléments soit {a,b,c},{a,b,d} ,{a,c,d} et {b,c,d}
L'ensemble formé des sous-ensemble à deux éléments satisfait les hypothèses, ainsi m >= 6.
Mais dans l'ensemble formé des sous-ensemble qui satisfait les hypothèses,il ne peut y avoir deux sous-ensembles à 3 éléments car le cardinal de leur intersection serait égal à 2.Ainsi, il y'a au maximum 1 sous-ensemble à 3 éléments,mais alors pour la présence de ce sous-ensemble,on ne pourra pas inclure 3 sous-ensembles de 2 éléments.
Ainsi,on ne peut avoir 7 éléments et m=6 .
** Pour N quelconque ,on appelle C={S_1,S_2,...,S_n} un sous-ensemble de P(S) qui satisfassent les hypotèses.....
Une conjecture me dit que le nombre cherché est C(2,N) ,mais je laisse d'autres continuer... _________________ Mon blog: http://nino.akopo.com
Posté le: Mer 06 Juil 2005 17:59 Sujet du message: Re: pour changer un peu les idées
kamiche a écrit:
Quel est le nombre maximal de sous ensembles d'un ensemble S de N éléments que l'on peut définir avec les conditions suivantes.
1. Chaque sous ensemble a au moins 2 éléments
2. L'intersection de deux sous ensembles distincts est toujours soit vide, soit un singleton.
slt
le nombre maximale est choix de 2 dans n c.a.d n!/(2!*(n-2)!) : le nombre de couplets de S.... _________________ ...
Posté le: Mer 06 Juil 2005 21:43 Sujet du message: Re: pour changer un peu les idées
PinPon a écrit:
kamiche a écrit:
Quel est le nombre maximal de sous ensembles d'un ensemble S de N éléments que l'on peut définir avec les conditions suivantes.
1. Chaque sous ensemble a au moins 2 éléments
2. L'intersection de deux sous ensembles distincts est toujours soit vide, soit un singleton.
le nombre maximale est choix de 2 dans n c.a.d n!/(2!*(n-2)!) : le nombre de couplets de S....
Effectivement, je crois aussi que c'est cela.
Il fallait vraiment que j'aie l'esprit encore en vacances pour ne pas le voir, ou alors, j'ai un peu trop forcé sur la gordon spark.
En tout cas, merci PinPon et Nino. _________________ I long to accomplish great and noble tasks, but it is my chief duty to accomplish humble tasks as though they were great and noble.
The world is moved along, not only by the mighty shoves of its heroes, but also by the aggregate of the tiny pushes of each honest worker.
Posté le: Mer 06 Juil 2005 23:58 Sujet du message:
nino a écrit:
Ceci dit, je ne vois pas comment le prouver....
j'essaie de commencer...
soit Ps l'ensemble de sous ensembles de S verifiant les conditions 1 et 2.
* Supposons que tout les couplets de S appartienent a Ps.
y'a pas de doute que les Conditions 1 et 2 soient remplis par les couplets .
soit Ei un sous ensemble de S ayant plus de 2 Element . c.a.d card(Ei)>2
il existe au moins 2 elements de Ps(couplets ) C1 , C2 qui sont inclus dans Ei
--> Ei ne peut apartenir a Ps, car card(Ei n C1) = 2.
on en deduit donc : tout les sous ensembles de S ayant plus de 2 elements n'arpartiennent pas a Ps , d'ou card(Ps)= C(2,n) nombre de couplets de S.
** Supposons maintenant que au moins un sous ensembles de S avec plus de 2 elements apartient a Ps , et montrons que dans ce cas, card(Ps)< C(2,n) ....
mon bic est fini ...
ps : escuser pour la grammaire et l'orthographe . _________________ ...
Posté le: Ven 08 Juil 2005 21:51 Sujet du message:
tu as n(n+1)/2 elements si tu les associes 2 par 2 en comptant que une fois les associations indeferemment de l'orde (exemple on compte A-B mais pas B-A) on a (n(n+1)/2)*(n(n+1)/2)-1)/2 et en comptant l'ordre on a (n(n+1)/2)*(n(n+1)/2)-1)
est ce juste?!!!!!
Posté le: Ven 08 Juil 2005 21:57 Sujet du message:
sorry j ai pas fini la reponse...tu auras le maximum de sous ensemble en joignant tes elements 2 par 2 puisk que c est la condition mini...et ensuite ce la va de soit que si tu comptes toutes les possibilités avec les meme elements (exemple A-B et B-A) la reponse est mon dernier chiffre du mail au dessus ..., allez balance le resultat...
Posté le: Mer 13 Juil 2005 17:57 Sujet du message:
olmeque a écrit:
sorry j ai pas fini la reponse...tu auras le maximum de sous ensemble en joignant tes elements 2 par 2 puisk que c est la condition mini...et ensuite ce la va de soit que si tu comptes toutes les possibilités avec les meme elements (exemple A-B et B-A) la reponse est mon dernier chiffre du mail au dessus ..., allez balance le resultat...
Je crois que le résultat que tu donnes est exact. J'avais posé le pb sans l'avoir.
Pour l'origine de la question, j'essayais de savoir le nombre max de réseaux virtuels (VLAN) que l'on peut configurer dans un réseau local (LAN) de N stations, sachant qu'un VLAN n'a de sens qu'avec au moins deux stations, et que deux stations ont en commun au plus un VLAN. _________________ I long to accomplish great and noble tasks, but it is my chief duty to accomplish humble tasks as though they were great and noble.
The world is moved along, not only by the mighty shoves of its heroes, but also by the aggregate of the tiny pushes of each honest worker.
Posté le: Sam 16 Juil 2005 17:48 Sujet du message:
kamiche a écrit:
Pour l'origine de la question, j'essayais de savoir le nombre max de réseaux virtuels (VLAN) que l'on peut configurer dans un réseau local (LAN) de N stations, sachant qu'un VLAN n'a de sens qu'avec au moins deux stations, et que deux stations ont en commun au plus un VLAN.
Comme quoi, elles se cachent partout ces mathématiques _________________ Mon blog: http://nino.akopo.com
Vous ne pouvez pas poster de nouveaux sujets dans ce forum Vous ne pouvez pas répondre aux sujets dans ce forum Vous ne pouvez pas éditer vos messages dans ce forum Vous ne pouvez pas supprimer vos messages dans ce forum Vous ne pouvez pas voter dans les sondages de ce forum