Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 09-06-2011 20:31:28

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

La somme de parties est...

Quelle est la somme du cardinal des parties d'un ensemble à n éléments?

Une partie d'un ensemble étant un ensemble inclus dans ce dernier et le cardinal étant le nombre d'éléments.

Exemple :
Pour n=2 il y a une partie à 0 éléments qui donne 0 dans la somme, 2 parties à 1 élément qui contribue à 2 ( 2 fois le cardinal 1) et une partie à 2 éléments qui apporte 2 (1 fois le cardinal 2) d'où une somme qui vaut 4.

Il n'y a pas besoin de gros moyens pour qui sera assez malin.big_smile

Bon travail.



Annonces sponsorisées :

Un mathématicien complet est topologiquement fermé!
  • |
  • Répondre

#0 Pub

 #2 - 09-06-2011 20:45:36

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

LLa somme des parties est...

Non les sous-ensembles au sens large, y compris tout l'ensemble.
(j'espère que c'était ta question)


Un mathématicien complet est topologiquement fermé!

 #3 - 09-06-2011 20:56:34

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

La somme des partiess est...

n*2^(n-1).
Il suffit d'isoler un élément au hasard et de compter le nombre de fois qu'il intervient dans un groupe.

 #4 - 09-06-2011 21:01:22

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

La somme des partes est...

Conseil :Essayez le cas n=3 à la main.
(a,b,c) a comme sous ensemble non vide (a);(b);(c);(a,b);(a,c)(b;c) et (a,b,c).
Le cardinal de (a,b) est 2, celui de (a,b,c) est 3...


Un mathématicien complet est topologiquement fermé!

 #5 - 09-06-2011 23:08:34

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 802
Lieu: Seahaven island

la somme des paryies est...

Salut,
Il s'agit donc d'analyser combien de fois le même élément sera compté.
Un élément se trouve dans 2^(n-1)sous ensemble différents.
Donc n*2^(n-1) nous donne la somme des cardinaux de toutes les parties.

 #6 - 09-06-2011 23:10:45

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3313

La somme des partiees est...

Ça serai super cool si la réponse était [latex]n^2 [/latex]roll mais j'y réflechit dès demain.


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #7 - 09-06-2011 23:19:57

irmo322
Professionnel de Prise2Tete
Enigmes résolues : 36
Messages : 198

La somme des parties eest...

Je propose deux solutions (la deuxième est mieux):


I)

Soit [latex]S(n)[/latex] la somme des cardinaux des parties d'un ensemble à [latex]n[/latex] éléments.

Soit [latex]n[/latex] entier positif. Soit [latex]E[/latex] un ensemble à [latex]n+1[/latex] éléments. Soit [latex]e[/latex] un élément de [latex]E[/latex].
Je sépare les parties de [latex]E[/latex] en deux groupes: celles qui ne contiennent pas [latex]e[/latex] et celles qui contiennent [latex]e[/latex].
La somme des cardinaux des parties qui ne contiennent pas [latex]e[/latex] est tout simplement [latex]S(n)[/latex].
La somme des cardinaux des parties qui contiennent [latex]e[/latex] est [latex]S(n)+2^n[/latex] car le nombre de parties qui contiennent [latex]e[/latex] est [latex]2^n[/latex].

Donc [latex]S(n+1)=2.S(n)+2^n[/latex].

On a S(0)=0.
On en déduit que [latex]S(n)=n.2^{n-1}[/latex].


II)

Soit [latex]n[/latex] entier positif. Soit [latex]E[/latex] un ensemble à [latex]n[/latex] éléments.
Soit [latex]e[/latex] un élément de [latex]E[/latex].
[latex]e[/latex] apparait dans [latex]2^{n-1}[/latex] parties. Sa contribution pour la somme des cardinaux des parties de [latex]E[/latex] s'élève donc à [latex]2^{n-1}[/latex].
Je somme les contributions de chaque élément de [latex]E[/latex], il y en a [latex]n[/latex], donc la somme des cardinaux des parties de [latex]E[/latex] est [latex]n.2^{n-1}[/latex].

 #8 - 10-06-2011 03:09:47

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

La somme des aprties est...

On va démontrer par récurrence que le résultat est n*2^(n-1)

Pour n=0: on a bien 0
On suppose qu'au rang n on ait une somme de cardinaux égale à n*2^(n-1)
Au rang n+1, essayons de montrer que cette somme vaut (n+1)*2^n

- je choisis un élément quelconque noté alpha
- on a 2^(n+1) sous-ensembles (car chaque élément peut être ou ne pas être dans une partie). Parmi ceux-ci, 2^n contiennent alpha et 2^n ne le contiennent pas. On va calculer les sommes séparément
- Pour ceux qui ne le contiennent pas, il s'agit de toutes les parties d'un ensemble à n éléments (notre ensemble, privé de alpha), la somme des cardinaux des parties est donc n*2^(n-1)
- Pour ceux qui le contiennent, les cardinaux sont les mêmes, à ceci près que pour chaque ensemble on ajoute 1 élément (alpha). Du coup, la somme vaut n*2^(n-1) + 2^n (car il y a 2^n sous ensembles)

Au final donc, la somme pour un ensemble de n+1 éléments vaut
n*2^(n-1)+n*2^(n-1)+2^n = n*2^n+2^n = (n+1)*2^n; cqfd

La réponse est donc n*2^(n-1)

Résultat sympathique, car on pouvait aussi écrire cela de manière plus complexe, comme par exemple la somme pour k allant de 0 à n des k*C(n,k). On obtient alors une jolie égalité:
[TeX]\sum_{k=0}^n{k.C_n^k}=n.2^{n-1}[/TeX]

 #9 - 10-06-2011 09:18:30

Memento
Professionnel de Prise2Tete
Enigmes résolues : 30
Messages : 176

la somme dzs parties est...

Alors, tout d'abord, pour un ensemble [latex]E[/latex] à [latex]n[/latex] éléments, il y à [latex]\binom{n}{k}[/latex] ensembles à [latex]k[/latex] éléments dans les parties de [latex]E[/latex]. La somme recherché est donc:
[TeX]\sum_{k=1}^n k*{\binom{n}{k}}
= \sum_{k=1}^n k*{\frac{n!}{k!*(n-k)!}}
= \sum_{k=1}^n {\frac{n!}{(k-1)!*(n-k)!}}
= \sum_{k=1}^n {\frac{n*(n-1)!}{(k-1)!*((n-1)-(k-1))!}}
= n*{\sum_{k=0}^{n-1} {\binom{n-1}{k}}}
=n*2^{n-1}[/TeX]
Jolie problème wink

 #10 - 10-06-2011 09:45:33

rivas
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1105
Lieu: Jacou

la somme des parties esr...

Il y a [latex]C_n^k[/latex] parties à k éléments.
La somme que l'on cherche est donc:
[TeX]S=\sum_{k=1}^nk.C_n^k[/latex].
La partie "gênante" est le k en facteur, qu'il faut essayer de faire disparaitre (on connait des formules de sommation des coefficients binomiaux).

Or [latex]k.C_n^k=k.\dfrac{n!}{k!(n-k)!}=n.\dfrac{(n-1)!}{(k-1)!(n-1-(k-1))!}=nC_{n-1}^{k-1}[/TeX]
On a donc [latex]S=\sum_{k=1}^{n}n.C_{n-1}^{k-1}=n.\sum_{i=0}^{n-1}C_n^i=n.2^{n-1}[/latex]

Merci pour ce petit calcul smile

 #11 - 10-06-2011 12:59:11

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

La smome des parties est...

Il n'y a pas besoin de coefficients binomiaux! cool


Un mathématicien complet est topologiquement fermé!

 #12 - 10-06-2011 14:19:12

Bamby2
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 152

La somme des parties estt...

on remarque qu'a chaque fois qu'on ajoute un element, l'ensemble des parties est composé du precedent ensemble + une copie de celui ci avec en plus l'element ajouté en gros en imaginant un vecteur binaire (0,X) et (1,X), donc chaque element est compté 2 fois plus a l'etape suivante.

on peut donc partant de la penser que chaque element est present [latex]2^{n-1}[/latex] qu'une simple réccurence nous prouve.

la somme vaut donc : [latex]n* 2^{n-1}[/latex]

 #13 - 10-06-2011 21:38:01

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

La somme des patries est...

Instinctivement, [latex]n2^{n-1}[/latex].



Bon, maintenant, soyons un peu futé... Il y a [latex]2^n[/latex] sous-ensembles, ça se démontre très facilement (on crée un sous-ensemble en choisissant de prendre ou pas chaque élément, donc deux choix possibles pour chacun des éléments, et hop).

Sans même faire les calculs de combinatoire, on sait qu'il y a autant de sous-ensembles a [latex]k[/latex] éléments que de sous ensembles a [latex]n-k[/latex] éléments. Pourquoi ? Parce qu'un sous-ensemble a [latex]k[/latex] éléments est inévitablement le complémentaire d'un et un seul sous-ensemble a [latex]n-k[/latex] éléments. Donc, si on a [latex]M_k[/latex] sous-ensembles a [latex]k[/latex] éléments, on a aussi [latex]M_k[/latex] sous-ensembles a [latex]n-k[/latex] éléments (autrement dit, [latex]M_{n-k} = M_k[/latex] : on obtiendrait la même chose avec la combinatoire, mais bon, pas la peine...).

Cette symétrie particulière nous permet d'arriver au résultat annoncé de deux façons.

--> La première consiste a dire qu'un sous-ensemble contient en moyenne [latex]\frac{n}{2}[/latex] éléments, puisque chaque sous-ensemble a son "symétrique", c'est-a-dire un sous-ensemble qui forme avec lui une partition de l'ensemble de départ. On multiplie ce cardinal moyen d'un sous-ensemble par le nombre de sous-ensembles, on simplifie par 2 la fraction obtenue, et hop.

--> La deuxième, plus "rigoureuse", consisterait en le calcul direct du nombre [latex]S[/latex] que l'on cherche en regroupant les sous-ensembles selon leur nombre [latex]k[/latex] d'éléments (qu'on n'a même pas besoin d'exprimer en fonction de [latex]n[/latex] et de [latex]k[/latex], adieu la combinatoire) :
[TeX]S = 0 \times M_0 + 1 \times M_1 + \dots + (n-1) \times M_{n-1} + n \times M_n[/TeX]
Ensuite, on rassemble les "anti-jumeaux" :
[TeX]S = \left( 0 \times M_0 + n \times M_n \right) + \left( 1 \times M_1 + (n-1) \times M_{n-1} \right) + \dots + P[/TeX]
Le terme "du milieu" [latex]P[/latex] diffèrera selon que [latex]n[/latex] est pair ou impair ; dans le premier cas, il vaudra :
[TeX]P = \frac{n}{2} \times M_{\frac{n}{2}}[/TeX]
Dans le second :
[TeX]P = \frac{n-1}{2} \times M_{\frac{n-1}{2}} + \frac{n+1}{2} \times M_{\frac{n+1}{2}}[/TeX]
On utilise ensuite les égalités [latex]M_0 = M_n[/latex], [latex]M_1 = M_{n-1}[/latex], etc. pour faire un petit passe-passe, illustré ici pour le premier terme :
[TeX]0 \times M_0 + n \times M_n = 0 \times \left( \frac{M_0 + M_n}{2} \right) + n \times \left( \frac{M_0 + M_n}{2} \right) = \frac{n}{2} \left( M_0 + M_n \right)[/TeX]
Idem avec tous les autres, pour finalement obtenir, dans les deux cas :
[TeX]S = \frac{n}{2} \sum_{k=0}^n M_k[/TeX]
La somme est le nombre total de sous-ensembles, soit [latex]2^n[/latex], et hop.



Intéressant... Et, pour moi qui suis une quiche en géométrie, reposant lol


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #14 - 12-06-2011 16:50:19

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

La somme des paties est...

Une autre méthode, plus directe.
On cherche la somme [latex]\sum_{k=0}^n{k.C_n^k}[/latex]
Comme [latex]C_n^k = C_n^{n-k}[/latex], on a
[TeX]2.\sum_{k=0}^n{k.C_n^k} = \\
\sum_{k=0}^n{k.C_n^k + (n-k).C_n^{n-k}} = \\
\sum_{k=0}^n{n.C_n^k} = \\
n.\sum_{k=0}^n{C_n^k} = \\
n.2^n[/TeX]
Et donc au final: [latex]\sum_{k=0}^n{k.C_n^k} = n.2^{n-1}[/latex]

 #15 - 12-06-2011 18:53:24

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

La somme des parites est...

Ce n'est pas grosso modo ce que Rivas a déjà fait ?


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #16 - 12-06-2011 19:16:28

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3313

la somme des pzrties est...

En tout cas tu as un bon instinct smile avant de faire les calculs moi aussi j'aimerai y arriver sad


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #17 - 12-06-2011 19:33:15

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

L asomme des parties est...

MthS-MlndN a écrit:

Ce n'est pas grosso modo ce que Rivas a déjà fait ?

Ben, quand j'ai posté ça, je ne savais pas encore ce que Rivas avait fait; mais cette méthode est indubitablement différente et plus directe que la première méthode postée par mes soins un peu avant smile

To-do list des choses à faire dans ma vie:
Caser le mot indubitablement dans un forum => Done
Prochain mot: Phtisiologie smile smile


Edit: et j'ai regardé ce qu'a fait Rivas, et c'est légèrement différent. On sait tous comment Gauss aurait fait la somme des 100 premiers entiers : en calculant son double, et en groupant les termes 2 par 2. Ici, on peut faire un peu pareil, comme Mathias le faisait remarquer dans sont post en fait. Du coup, on calcule 2S comme étant n*2^n et c'est tout bon

 #18 - 12-06-2011 19:41:08

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

La somme des parties est..

Bravo à tous.
Ma méthode était la suivante :
Compter deux fois la somme, une fois normalement et une autre en considérant le complémentaire de chaque terme de la somme, finalement on compte n fois [latex]2^n[/latex] et comme on a compté 2 fois le résultat est [latex]n2^{n-1}[/latex].


Un mathématicien complet est topologiquement fermé!

 #19 - 12-06-2011 20:09:36

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

La somme des parrties est...

scarta a écrit:

MthS-MlndN a écrit:

Ce n'est pas grosso modo ce que Rivas a déjà fait ?

Ben, quand j'ai posté ça, je ne savais pas encore ce que Rivas avait fait; mais cette méthode est indubitablement différente et plus directe que la première méthode postée par mes soins un peu avant smile

OK, mea culpa big_smile


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298
 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Dans une course, vous doublez le 31ème, en quelle position êtes-vous ?

Sujets similaires

Mots clés des moteurs de recherche

Mot clé (occurences)
Calculer la somme du cardinal d un ensemble (6) — Somme des coefficients binomiaux au carre (4) — Somme des carres des coefficients binomiaux (3) — Le carre de somme de n element (2) — La somme des parties (2) — Somme des cardinaux (2) — Enigme la somme (2) — Somme des cardinaux des parties de e (2) — Somme de cardinaux (2) — Somme cardinal a (2) — Somme des elements d un ensembl (2) — Calculer la somme d u cardinal d un ensemble (2) — Sommes des parties d un ensemble (2) — Deduire la somme des cardinal de a (2) — La somme des parties ensembles mathematiques (1) — La somme des individus est differente (1) — Calculer la somme des cardinaux de toutes les partie de e (1) — Somme des elements d un ensemble (1) — Le tout est different de la somme des parties (1) — Exemple de carre logique (1) — La somme des parties est (1) — Camcul somme des cardinal (1) — Sommes d ensembles (1) — L ensemble des parties d un ensemble produit (1) — Sommation formule (1) — Produit somme n+k nk enigme solution (1) — Formule nombre de partie d un ensemble (1) — Coefficients binomiaux besancon (1) — Somme des cardinaux des parties d un ensemble (1) — Calculer la somme des cardinaux de tous les sous-ensembles de e (1) — Deux ensemble de nombres de m^me somme (1) — Cardinal d un ensemble compose de troi sous ensembl (1) — L ensemble des parties de e (1) — Formule de cardinal de deux ensembles (1) — Enigme isoler des elements (1) — La somme es parties est super (1) — Sommes des parties (1) — Somme des cardinaux d un ensemble (1) — Nombre de parties + 2^n (1) — Nombre parties ensemble (1) — Enigmes mathematiques somme de chaque carre est 20 (1) — Enigme e est un ensemble de n elements (1) — Calculer la somme des cardinaux de toutes les parties de e (1) — Somme de parties d ensemble (1) — Enigme: element d une somme (1) — Somme des cardinaux des partie d un ensemble (1) — Enigme la somme de a+b+c (1) — Somme de coefficients binomiaux au carre (1) — Somme cardinal des parties (1) — En deduire la somme des 100 premiers entiers pairs enigme (1) — Nombre de partie ensemble (1) — Tout somme des parties mathematiques (1) — Somme des parties (1) — Formule somme factorielle (1) — Cardinal d un ensemble par somme (1) — Somme cardinaux parties de e (1) — A + b = d tout somme des parties (1) — La somme enigme (1) — -216 est la somme des element de l ensemble n (1) — Somme des nombres d un ensemble (1) — Somme de cardinal (1) — Somme 1/k! (1) — Somme de cardinal de k sur n (1) — Le tout etant la somme des parties (1) — Cardinal de l ensemble des parties de e (1) — Methode somme des parties (1) —

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete