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 - 26-10-2010 16:08:49

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

Sous ensembles d sous ensembles

Nous avons un ensemble E de taille n

1) Combien existe-t-il de couples d'ensembles (A, B) tels que A est un sous ensemble de B qui est un sous ensemble de E ? (A c B c E)

Vous pouvez tester la case réponse pour n = 10

2) Soit m un entier, combien y a-t-il de m-uplets (A1, A2, ...,Am) de parties de E tels que A1 c A2 c ... c Am



Annonces sponsorisées :

 
Réponse :
  • |
  • Répondre

#0 Pub

 #2 - 26-10-2010 16:33:07

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

Sous ensembles de sous ensemles

Tu aurais pu la poster dans une heure ou deux, que je prenne le temps de bosser un peu sur ma thèse entre-deux lol

Bon, par pur manque d'autodiscipline, j'entame cette énigme.

Résultat essentiel : avec [latex]P(E)[/latex] l'ensemble des parties de [latex]E[/latex], c'est-à-dire l'ensemble de tous les sous-ensembles de [latex]E[/latex], on a [latex]Card (P(E)) = 2^n[/latex] (facile à prouver).

En entrant plus dans le détail : comme il y a [latex]\binom{n}{k}[/latex] façons de choisir [latex]k[/latex] éléments parmi [latex]n[/latex], il y a autant de sous-ensembles différents et de cardinal [latex]k[/latex] d'un ensemble de cardinal [latex]n[/latex]. En sommant sur [latex]k[/latex], on obtient le [latex]2^n[/latex] ci-dessus.

Voici donc tous les ensembles [latex]B[/latex] que l'on peut choisir, et pour un ensemble [latex]B[/latex] de cardinal [latex]k[/latex], on peut créer [latex]2^k[/latex] sous-ensembles [latex]A[/latex] de [latex]B[/latex]. Et voici la belle formule qui débarque, et qui donne le nombre [latex]C_n[/latex] de couples d'ensemble [latex](A,B)[/latex] respectant l'énoncé que l'on peut créer en fonction de [latex]n[/latex] :
[TeX]C_n = \sum_{k=0}^n \binom{n}{k} 2^k[/TeX]
Euh... Peut-on calculer ça d'une façon pas trop moche ? Ouais, avec Wolfram|Alpha lol

Pour n=10, je tape :

Code:

sum binomial[10,k]*2^k, k=0 to 10

Et il me répond 59049, qui est validé par la case réponse smile

Là aussi, il y a de la bonne explosion de valeurs dans l'air :

5     -> 243
10    -> 59049
15    -> 14348907
20    -> 3486784401
25    -> 847288609443
30    -> 205891132094649


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

 #3 - 26-10-2010 16:33:40

luthin
Professionnel de Prise2Tete
Enigmes résolues : 36
Messages : 124

SSous ensembles de sous ensembles

Il y a [latex]C_n^p[/latex] façons de choisir un ensemble B de taille p de E.

Il y a [latex]C_p^q[/latex] façons de choisir un ensemble A de taille q de B.

Le nombre recherché est donc:
[TeX]N(n)=\sum_{p=0}^n\sum_{q=0}^p C_n^p C_p^q=\sum_{p=0}^n C_n^p 2^p=3^n[/TeX]
On a donc:
[TeX]\fbox{N(10)=3^{10}=59049}[/TeX]

 #4 - 26-10-2010 17:05:30

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

Sous ensembles de sous ensmbles

On commence par fixer un ensemble B de X éléments
Combien y a t'il de sous-ensembles de B ayant Y éléments ?
C'est par définition le nombre d'arrangement C(X,Y), qui vaut X! / [(X-Y)! Y!]

Donc, combien y a t'il de sous-ensembles de B à X éléments, toutes tailles confondues ?
C'est la somme pour Y allant de 0 à X des C(X,Y), qui vaut 2^X (chose qu'on démontre aisément en déroulant le binôme de Newton de (1+1)^X)

Chaque ensemble B de X éléments peut être couplé à 2^X sous ensembles, mais combien y-a-t'il d'ensembles B de X éléments ?
Pareil, c'est le nombre d'arrangement C(N,X), qui vaut N! / [(N-X)! X!]

=> Le nombre de couples (A,B) pour un ensemble B à X éléments est
2^X * N! / [(N-X)! X!]

=> Le nombre de couples (A,B) pour toutes les tailles de B est donc défini par la formule suivante:
[TeX]\sum_{X=0}^N{\frac{2^XN!}{(N-X)! X!}}[/TeX]
Oh, stupeur, encore un binôme de Newton !!
[TeX]\sum_{X=0}^N{\frac{2^XN!}{(N-X)! X!}}=\\
\sum_{X=0}^NC_n^X 2^X 1^{(N-X)}=\\
(2+1)^N = 3^N
[/TeX]
Pour un ensemble E à n éléments, on a donc 3^n paires différentes d'ensembles (A,B) telles que E contient B qui contient A
(Pour n=10, la réponse est 59.049)

 #5 - 26-10-2010 17:17:15

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Sous ensembles de sous nesembles

Sauf erreur smile
[TeX]\sum_{k=0}^n2^kC_n^k=(1+2)^n=3^n[/TeX]
Vasimolo

 #6 - 26-10-2010 17:52:06

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

sous ensembles de sous ensembled

Joli exercice et jolie formule. Je n'ose dire simple mais élégant.

Un ensemble de n éléments à [latex]2^n[/latex] sous-ensembles.

Un ensemble à n éléments a [latex]C_n^k[/latex] sous-ensembles à k éléments. Or chacun de ces sous-ensembles a lui-même [latex]2^k[/latex] sous-ensembles.

Il y a donc au total [latex]\sum_{k=0}^nC_n^k2^k[/latex] couples de la forme que l'on recherche.

Or cette expression est justement le développement du binome pour [latex](2+1)^n[/latex]. Il y en a donc [latex]3^n[/latex] .

Pour n=10, cela donne 59049, ce qui est validé par la case réponse.

Merci.

De plus à vu de nez, j'ai l'impression que ça se généralise très bien...

 #7 - 26-10-2010 22:54:27

scrablor
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 931

Sous ensembls de sous ensembles

Ça doit valoir 3^n.
Si card(A)=p, A possède 2^p parties. Ce qui arrive autant de fois qu'il y a de combinaisons de p parmi n.
Quand on ajoute le tout, de p=0 à p=n,  on reconnaît la formule du binôme de (1+2)^n.


Celui qui fuit les casse-tête ne vaut pas un clou.

 #8 - 27-10-2010 04:45:06

McFlambi
Professionnel de Prise2Tete
Enigmes résolues : 48
Messages : 144

sous ensembles de sous enqembles

pour chaque ensemble de cardinal [latex]n[/latex], il y a [latex]2^n[/latex] parties, ou sous ensembles. Et en particulier, il y a [latex]C_n^i=\frac{n!}{i! (n-i)!}[/latex] parties de cardinal [latex]i[/latex]

Donc pour chaque B de cardinal [latex]i[/latex] dans E (de cardinal [latex]n[/latex]), il y a encore [latex]2^i[/latex] A differents dedans, d'ou la formule
[TeX]\sum_{i=0}^n C_n^i 2^i=\sum_{i=0}^n C_n^i 2^i 1^{n-i} = 3^n[/TeX]
pour 10 cela donne 59049.

Une autre facon plus elegante de voir le probleme est de dire que prendre un couple (A,B), c'est, pour chaque element de E, choisir s'il est :
-dans A et B
-dans A
-dans aucun des deux
d'ou directement la reponse [latex]3^n[/latex]

 #9 - 27-10-2010 09:36:22

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

sous ensembles de sous endembles

Deux idées en plus

I) Pour aller plus vite
On remarque que pour n=0, on a 1 paire, pour n=1, on a 3 paires, et pour n=2 on a 9 paires. On suppose que le nombre de paires pour n quelconque est 3^n, et on le démontre par récurrence.
Si card(E) = n et card({(A,B} tq A c B c E}) = 3^n, alors
Soit x un élément qui n'est pas dans E, et E' = E U {x}, card(E') = n+1
Pour chaque paire (A,B) trouvée pour E, on peut déduire 3 paires valides
- (A,B) puisque E c E'
- (A,B U {x})
- (A U {x} ,B U {x})
Toute paire (A,B) qu'on pourrait trouver dans E' est de cette forme là (x présent 0, 1 ou 2 fois). Donc on a 3 fois plus de paires pour E' que pour E, donc 3^(n+1). CQFD

II) Pour aller plus loin
Soit E un ensemble, card(E) = N, soit k un entier naturel, soit s un ensemble d'ensembles tel que card(s) = k, et enfin soit S = {s tels que A1 c A2 c ... c Ak c E}
On peut montrer que card(S) = (k+1)^N

2 méthodes pour ça:
a. On peut procéder par récurrence sur k.
On a 2^n sous ensembles de E.
On suppose on a (k+1)^n ensembles de k sous ensembles de E et imbriqués
Pour des ensembles de k+1 éléments, pour un élément A(k+1) de cardinal X, on a (d'après l'hypothèse de récurrence) (k+1)^X "suites" possibles.
On a de plus C(n,X) ensembles A(k+1) de cardinal X possibles.
Le résultat est donc la somme suivante
[TeX]\sum_{X=0}^NC_n^X(k+1)^X=\\
((k+1)+1)^N=\\
(k+2)^N[/TeX]
d'après la formule du binôme de Newton, CQFD

b. On peut aussi procéder par récurrence sur n.
Pour n=0, on a une seule combinaison de k sous ensembles (tous sont égaux à l'ensemble vide)
On suppose que le nombre de possibilité pour n est (k+1)^n
On procède comme dans le I). Soit E' = E U {x}, toute solution pour E correspond à k+1 solutions pour E'
- (A1, A2, ..., Ak)
- (A1, A2, ..., A(k-1), Ak U {x})
- (A1, A2, ..., , A(k-1) U {x}, Ak U {x})
...
- (A1, A2 U {x}, ..., , A(k-1) U {x}, Ak U {x})
- (A1 u {x}, A2 U {x}, ..., , A(k-1) U {x}, Ak U {x})
Toute solution de E' est correspond à une de ces solutions, on a donc k+1 fois plus de solutions pour E' que pour E, donc au total (k+1)*(k+1)^n = (k+1)^(n+1). CQFD bis

 #10 - 27-10-2010 10:48:31

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

Sous ensembbles de sous ensembles

Bravo a tous ceux qui ont déjà trouvé.
Bravo supplémentaire à rivas pour avoir flairé la généralisation et grand bravo a Scarta pour l'avoir démontré. Et de deux manière s'il vous plait !!

Donc exercice supplémentaire :

Soit m un entier, combien y a-t-il de m-uplets (A1, A2, ...,Am) de parties de E tels que A1 c A2 c ... c Am

 #11 - 27-10-2010 11:10:20

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Sous ensembles de sous ensemblees

La réponse est [latex](m+1)^n[/latex] , ça revient en effet à indiquer quel moment de la liste apparaît le kième élément de E ( s'il apparaît ) .

Vasimolo

 #12 - 27-10-2010 13:11:06

luthin
Professionnel de Prise2Tete
Enigmes résolues : 36
Messages : 124

SSous ensembles de sous ensembles

Pour la question bonus, je dirais [latex](m+1)^n[/latex].

 #13 - 27-10-2010 15:14:59

McFlambi
Professionnel de Prise2Tete
Enigmes résolues : 48
Messages : 144

Sous ensembles de sous ensembes

Bin prendre un [latex]m[/latex]-uplet, c'est prendre pour chaque element un entier [latex]k[/latex] entre 0 et [latex]m[/latex] (qui correspond aux [latex]k[/latex] parties incluses qui contiennent l'element).
[TeX]u(m,n)=(m+1)^n[/TeX]
sinon, on peut le faire par reccurence, en prenant la premiere partie (la plus grosse) du [latex]m[/latex]-uplet contenant [latex]i[/latex] elements (il y en a [latex]C_n^i[/latex]):
[TeX]u(m,n)=\sum_{i=0}^n C_n^i u(m-1,i)[/TeX]
avec [latex]u(1,i)=2^i[/latex]

dont on peut supposer la solution assez vite et verifier ensuite... De maniere equivalente, on peut partir de la plus petite partie, a ce moment on se retrouve a enlever les elements de cette partie et on refait le meme probleme pour m-1, et on a un formule semblable, qui peut aussi aider a comprendre la forme de la solution:
[TeX]u(m,n)=\sum_{i=0}^n C_n^i u(m-1,n-i)[/TeX]
On peut faire une recurrence sur [latex]n[/latex], donc il suffit de se dire que si on rajoute un element a E, alors on peut le mettre dans les k premieres parties incluses de chaque m-uplet (m+1 choix)... d'ou
[TeX]u(m,n) = (m+1)u(m,n-1)[/TeX]
qui donne la reponse assez vite aussi.
[He ca fait 4 demonstrations ! j'ai gagne ?]

 #14 - 27-10-2010 19:06:41

LeSingeMalicieux
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1298
Lieu: Haute-Marne

Sous ensembles de sous ensebles

Désolé, je suis plutôt très mauvais en LaTeX, aussi, j'ai préféré faire une image. En même temps ça limitera l'accès serveur (même si ça augmente de 2.65 Ko l'espace serveur utilisé) wink

Pour la question 1, avec :
- E ensemble de taille n
- B sous-ensemble de E de taille i
- A sous-ensemble de B de taille k

Je pense que le nombre de couples d'ensembles (A, B) est :
http://www.prise2tete.fr/upload/LeSingeMalicieux-Nicouj-SousEnsembles.PNG
(Si quelqu'un veut me donner la formule LaTeX, ça serait avec plaisir smile )


Pour la question 2, je pense qu'en imbriquant selon la formule précédente, on peut trouver la réponse.

EDIT 20:06 :
Tiens c'est rigolo, en cherchant la réponse pour n=10 (qui est 59049) avec un célèbre tableur, et afin de me confirmer dans ma réponse, je m'aperçois qu'il est question de la somme des termes de la n-ième ligne du triangle de Pascal multipliés par des puissances de 2. C'est quand même génial les mathématiques smile
Je vais tâcher de généraliser avec ces découvertes, mais je ne promets rien.


Avoir quatre mains, c'est plus pratique pour taper sur un clavier.

 #15 - 27-10-2010 23:22:32

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

sous ensembles de sous ensembkes

La démonstration est dans ma tête smile mais je n'ai pas trop le temps de l'écrire.
En fait, c'est une démo par récurrence qui se base sur le même principe qu'au rang 2 déjà montré.
Au rang p+1, on trouve le développement de (p+1)^n en se basant sur le rang p.
J'espère vous avoir convaincu, sinon j'y reviendrai...

 #16 - 02-11-2010 13:42:09

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

Sous ensemblse de sous ensembles

Bravo a tous.

La réponse est bien (k+1)^n  soit 3^n  dans le cas particulier de la question 1
Beaucoup de démo qui utilisent le binôme de Newton (la manière que j'ai utilisée aussi)
La démo de Vasimolo et de McFlambi est une révélation big_smile
Bravo et merci a vous deux

 #17 - 02-11-2010 14:42:12

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

Sous ensembles de sous ensemlbes

LeSingeMalicieux a écrit:

http://www.prise2tete.fr/upload/LeSinge … embles.PNG
(Si quelqu'un veut me donner la formule LaTeX, ça serait avec plaisir smile )

\sum_{i=0}^n \left( C_n^i \times \left( \sum_{k=0}^i C_i^k \right) \right)
[TeX]\sum_{i=0}^n \left( C_n^i \times \left( \sum_{k=0}^i C_i^k \right) \right)[/TeX]
Les parenthèses ne rendent pas terrible : c'est à cause de l'interpréteur. D'autres les eussent faites plus lisses et plus belles...


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

 #18 - 02-11-2010 14:56:48

engine
Professionnel de Prise2Tete
Enigmes résolues : 37
Messages : 351

sous enqembles de sous ensembles

srx c'est de quels niveaux vos énigmes... T-T


plouf

 #19 - 02-11-2010 14:58:54

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

sous ensembles de sous ensembmes

Celle-là est faisable par un élève de Terminale S, spé maths (pour les outils). Après, c'est soit de la débrouillardise, soit de l'obstination smile


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

 #20 - 02-11-2010 15:03:46

engine
Professionnel de Prise2Tete
Enigmes résolues : 37
Messages : 351

Sous ensembles de sous enssembles

C'est possible de mettre le niveau entre crochets ? Parce que bon celle-là pas question que je l'aborde, mais d'autres je ne sais jamais pas trop ^^ Bref j'ai l'impression qu'ici on ne poste pas bcp d'énigmes abordables :S


plouf

 #21 - 02-11-2010 15:14:41

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

sous ensembles dz sous ensembles

Magie des énigmes mathématiques hmm

D'un autre côté, il y a aussi des énigmes cryptées qui sont plus ou moins dures, mais comment noter le niveau ? smile


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

 #22 - 02-11-2010 16:24:02

LeSingeMalicieux
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1298
Lieu: Haute-Marne

Sous ensembles dde sous ensembles

Merci MthS pour la formule LaTeX (et merci également à McFlambi qui est passé par MP) smile


Avoir quatre mains, c'est plus pratique pour taper sur un clavier.

 #23 - 02-11-2010 22:53:55

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

Sous ensembles de sous ensemblse

J'ai déjà eu du mal à comprendre ce qu'on cherchait, alors j'ai bien fais de ne pas chercher. Mais j'apprends telement chose ici smile tous les raisonnement qui sont possible, c'est très bien pour les contrôles ça smile et avec de la chance pour le bac aussi.


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

Réponse rapide

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

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pif, Paf et ?

Mots clés des moteurs de recherche

Mot clé (occurences)
Combien existe-t-il de couples (2) — Le nombre de couples (x;y) de parties de e tels que x inclu dans y (1) — Ensembles qui se contiennent (1) — Combien existe t-il de couples (ab) (1) — En deduire le nombre de couples (ab) de sous-ensembles de e tels que (1) — Comment noter les sous ensembles (1) — Combien existe-t-il de couple (ab) tels que (1) — K sous-ensemble (1) — Nombre de couple (ab) tel que a inclus dans b (1) — Nombre de couple (ab) tel quea inclue dans b (1) — Nombre de couples (ab) inclus dans e a inclus dans b (1) — Ensemble e contient n elements combien existe il de couples (a;b) de deux ensemble tel que (1) — Soit a={befoglkw} et b={aehiklw }.1-ecris a n b et a u b en extension.2-determine card (a);card(b) et card(a n b).traite l exercice de denombrement (1) — Demonstration 2^n sur une ligne du triangle de pascal (1) — Combien un ensemble a 10 elements a-t-il de sous ensembles ? (1) — Combien existe-t-il de sous-ensembles d?un ensemble de taille n ? (1) — Enigme sur les ensembles (1) — Soit x un ensemble a n element. combien y a t-il de parties de x a p elements qui contiennent un ensemble de k elements donne d avance (1) — Ensemble des sous ensemble de e newton (1) — Enigmes sur les ensembles (1) — Combien existe t-il de balance (1) — En deduire: ?_(k=0)^n?c_n^k =2^n (1) — Combien existe t il de binomes (1) — E est un ensemble de cardinal n combien il u a des sous ensembles (1) — Taille sous ensemble a?b (1) — Somme nombre ensemble (1) — Nombres de parties avec a inclus dans b (1) — Nombre de couple (ab) de parties e tel que a inclu dans b (1) — Combien existe-t-il de sous-ensembles d?un ensemble de taille n (1) — Combien existe t il de couples (ab) (1) — Uplets enigmes maths (1) — Sous ensemble de n (1) — Nombre couples parties (1) — Nombre de couples de parties dans un element (1) — Ensembles des combinaisons de p l element parmi n (1) — E est un ensemble qui contient n elements. combien existe-t-il de couples (a; b) de deux ensembles tel que (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