Maths et Délires
Des maths et des délires
 

Maths et Délires Index du Forum

 FAQFAQ   RechercherRechercher   Liste des MembresListe des Membres   Groupes d'utilisateursGroupes d'utilisateurs   S'enregistrerS'enregistrer 
 ProfilProfil   Se connecter pour vérifier ses messages privésSe connecter pour vérifier ses messages privés   ConnexionConnexion 

Exo de combinatoire

 
Poster un nouveau sujet   Répondre au sujet    Maths et Délires Index du Forum -> Mathématiques olympiques
Voir le sujet précédent :: Voir le sujet suivant  
Auteur Message
Thibaut
Geek mutant fou


Inscrit le: 23 Juin 2005
Messages: 3226
Localisation: MB 318, Montrouge

MessagePosté le: 22 Jan 2008, 16:26    Sujet du message: Exo de combinatoire Répondre en citant

Soit [tex:1ce2a3a715]X[/tex:1ce2a3a715] un ensemble, et [tex:1ce2a3a715]T[/tex:1ce2a3a715] un ensemble de parties de [tex:1ce2a3a715]X[/tex:1ce2a3a715], stable par intersections (par intersections finies suffit ?).

Montrer que, si, pour tout [tex:1ce2a3a715]n \in \mathbb N[/tex:1ce2a3a715], il existe une famille de [tex:1ce2a3a715]n[/tex:1ce2a3a715] éléments non vides et deux à deux disjoints de [tex:1ce2a3a715]T[/tex:1ce2a3a715], alors il existe une famille infinie d'éléments non vides et deux à deux disjoints de [tex:1ce2a3a715]T[/tex:1ce2a3a715].

Si vous trouvez que ça n'a pas sa place dans Maths. Olympiques, je peux le déplacer, mais il me semble que l'exercice peut se comprendre et se résoudre à ce niveau-là...
_________________
"“The Sith who were famous for being bad, Jacen, were the way they were because they were badly damaged men or women to start with. Not because they were Sith. Usually, they were weak, or deluded, or greedy to begin with. Like your grandfather.”"
Shira Brie aka Lumiya aka Brisha Syo, Legacy of the Force, #1: Betrayal
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail
Abou
Matheux(se) cinglé(e)


Inscrit le: 18 Oct 2007
Messages: 347
Localisation: Paris, mais presque.

MessagePosté le: 22 Jan 2008, 19:03    Sujet du message: Re: Exo de combinatoire Répondre en citant

Qu'entends-tu par "stable par intersections" (encore plus "intersections finies")?

Je vois ça comme ça : [tex:17e4afa715]\forall[/tex:17e4afa715]{[tex:17e4afa715]X_i[/tex:17e4afa715]}[tex:17e4afa715]_{i\in A} \in T[/tex:17e4afa715], [tex:17e4afa715]\bigcap\limits_{i\in A} X_i \subset T [/tex:17e4afa715].
Si c'est bien ça, je ne vois pas comment ça pourrait ne pas être le cas. Mais ça donnerait le "intersections finies" par [tex:17e4afa715]A[/tex:17e4afa715] ensemble fini d'indices.


Et quand tu dis disjoints, c'est comme distincts?


Dernière édition par Abou le 02 Mar 2008, 13:44; édité 1 fois
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail MSN Messenger
antony
Mathématicien(ne) fou (folle)


Inscrit le: 24 Juin 2005
Messages: 2176
Localisation: Vincennes/Aulnay

MessagePosté le: 22 Jan 2008, 19:25    Sujet du message: Re: Exo de combinatoire Répondre en citant

Abou a écrit:
Qu'entends-tu par "stable par intersections" (encore plus "intersections finies")?

Je vois ça comme ça : [tex:4bc8500951]\forall[/tex:4bc8500951]{[tex:4bc8500951]X_i[/tex:4bc8500951]}[tex:4bc8500951]_{i\in A} \in T[/tex:4bc8500951], [tex:4bc8500951]\bigcap\limits_{n\in A} X_i \subset T [/tex:4bc8500951].
Si c'est bien ça, je ne vois pas comment ça pourrait ne pas être le cas. Mais ça donnerait le "intersections finies" par [tex:4bc8500951]A[/tex:4bc8500951] ensemble fini d'indices.
Oui, c'est ce que ça veut dire. Mais je ne vois pas en quoi c'est évident (enfin si, perso j'ai cru avoir une preuve mais je me suis rendu compte qu'elle foirait, donc bon...)

Abou a écrit:
Et quand tu dis disjoints, c'est comme distincts?
Non, ça veut dire d'intersection vide.
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé
Abou
Matheux(se) cinglé(e)


Inscrit le: 18 Oct 2007
Messages: 347
Localisation: Paris, mais presque.

MessagePosté le: 22 Jan 2008, 19:43    Sujet du message: Répondre en citant

Ha oui, au temps pour moi pour les "disjoints" Laughing

Par contre pour les {[tex:0309f3731f]X_i[/tex:0309f3731f]}, si [tex:0309f3731f] x \in[/tex:0309f3731f][tex:0309f3731f] \bigcap\limits_{n\in A} X_i[/tex:0309f3731f] alors [tex:0309f3731f]\forall i \in A[/tex:0309f3731f], [tex:0309f3731f] x \in X_i[/tex:0309f3731f] donc [tex:0309f3731f]x \in T[/tex:0309f3731f], i.e. [tex:0309f3731f]\bigcap\limits_{n\in A} X_i \subset T[/tex:0309f3731f], non?
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail MSN Messenger
Thibaut
Geek mutant fou


Inscrit le: 23 Juin 2005
Messages: 3226
Localisation: MB 318, Montrouge

MessagePosté le: 22 Jan 2008, 20:18    Sujet du message: Re: Exo de combinatoire Répondre en citant

Abou a écrit:
Qu'entends-tu par "stable par intersections" (encore plus "intersections finies")?


[tex:cafc0c3212]T[/tex:cafc0c3212] est stable par intersections lorsque, pour toute famille [tex:cafc0c3212](X_a)_{a \in A} \in T^A[/tex:cafc0c3212] d'éléments de [tex:cafc0c3212]T[/tex:cafc0c3212], [tex:cafc0c3212]\bigcap\limits_{a \in A} X_a \in T[/tex:cafc0c3212].

[tex:cafc0c3212]T[/tex:cafc0c3212] est stable par intersections finies lorsque c'est le cas en restreignant la condition aux familles finies d'éléments de [tex:cafc0c3212]T[/tex:cafc0c3212], ou, de manière équivalente, lorsque : [tex:cafc0c3212]X \in T[/tex:cafc0c3212] et [tex:cafc0c3212]\forall X_1, X_2 \in T, X_1 \cap X_2 \in T[/tex:cafc0c3212]

Quelle est ta "preuve", Antony (j'espère que c'est pas la mienne, j'ai pas envie d'apprendre qu'elle est fausse...) ?
_________________
"“The Sith who were famous for being bad, Jacen, were the way they were because they were badly damaged men or women to start with. Not because they were Sith. Usually, they were weak, or deluded, or greedy to begin with. Like your grandfather.”"
Shira Brie aka Lumiya aka Brisha Syo, Legacy of the Force, #1: Betrayal
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail
antony
Mathématicien(ne) fou (folle)


Inscrit le: 24 Juin 2005
Messages: 2176
Localisation: Vincennes/Aulnay

MessagePosté le: 22 Jan 2008, 20:43    Sujet du message: Répondre en citant

Pour n fixé, soit [tex:8a7c13668d](e_{i,n})_{1\leq i\leq n}[/tex:8a7c13668d] une famille de [tex:8a7c13668d]n[/tex:8a7c13668d] éléments de [tex:8a7c13668d]T[/tex:8a7c13668d] deux à deux disjoints. On construit la suite [tex:8a7c13668d](f_{i,n})_{1\leq i\leq n}[/tex:8a7c13668d] de la manière suivante :
- [tex:8a7c13668d]f_{n,n}=e_{n,n}[/tex:8a7c13668d]
- Si [tex:8a7c13668d]e_{i,n+1}\cap f_{i,n}=\emptyset[/tex:8a7c13668d], [tex:8a7c13668d]f_{i,n+1}=f_{i,n}[/tex:8a7c13668d], sinon, [tex:8a7c13668d]f_{i,n+1}=f_{i,n}\cap e_{i,n+1}[/tex:8a7c13668d]
On voit assez facilement que pour tout [tex:8a7c13668d]n[/tex:8a7c13668d], [tex:8a7c13668d](f_{i,n})_{1\leq i\leq n}[/tex:8a7c13668d] une famille de [tex:8a7c13668d]n[/tex:8a7c13668d] éléments [tex:8a7c13668d]\not=\emptyset[/tex:8a7c13668d] de [tex:8a7c13668d]T[/tex:8a7c13668d] deux à deux disjoints, et que pour tout [tex:8a7c13668d]i[/tex:8a7c13668d], la suite [tex:8a7c13668d](f_{i,n})_n[/tex:8a7c13668d] est décroissante.
Du coup je suis tenté de prendre [tex:8a7c13668d]F_n=\lim_if_{i,n}\in T[/tex:8a7c13668d] (c'est une intersection infinie d'éléments de [tex:8a7c13668d]T[/tex:8a7c13668d]) et de dire qu'elle satisfait aux conditions de l'énoncé, mais rien ne me garantit que ce ne sont pas des ensembles vides (d'ailleurs ça peut tout à fait arriver).
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé
Abou
Matheux(se) cinglé(e)


Inscrit le: 18 Oct 2007
Messages: 347
Localisation: Paris, mais presque.

MessagePosté le: 22 Jan 2008, 21:44    Sujet du message: Répondre en citant

Ha oui, ça y est j'ai (enfin) compris ... je confondais ensemble et élément ... (c'est vraiment pas ma journée aujourd'hui - j'ai presque planté sur sin(p)-sin(q) en colle ce midi - ...)
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail MSN Messenger
Thibaut
Geek mutant fou


Inscrit le: 23 Juin 2005
Messages: 3226
Localisation: MB 318, Montrouge

MessagePosté le: 22 Jan 2008, 22:11    Sujet du message: Répondre en citant

Effectivement, ma preuve était celle-ci... Il faut donc ajouter une hypothèse de compacité, genre toute suite décroissante d'éléments de [tex:2a5f651ac7]T[/tex:2a5f651ac7] d'intersection vide est vide àpcr.
_________________
"“The Sith who were famous for being bad, Jacen, were the way they were because they were badly damaged men or women to start with. Not because they were Sith. Usually, they were weak, or deluded, or greedy to begin with. Like your grandfather.”"
Shira Brie aka Lumiya aka Brisha Syo, Legacy of the Force, #1: Betrayal
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail
antony
Mathématicien(ne) fou (folle)


Inscrit le: 24 Juin 2005
Messages: 2176
Localisation: Vincennes/Aulnay

MessagePosté le: 22 Jan 2008, 22:19    Sujet du message: Répondre en citant

Mouais, mais j'aime pas trop... ça fait un peu l'hypothèse qui est là pile pour que ça marche... Faudrait quelque chose de plus naturel. Ou des idées de contre-exemples, pour voir ce qui est vraiment nécessaire.
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé
Thibaut
Geek mutant fou


Inscrit le: 23 Juin 2005
Messages: 3226
Localisation: MB 318, Montrouge

MessagePosté le: 02 Fév 2008, 13:00    Sujet du message: Répondre en citant

Apparemment, ça marche même sans "compacité", et même avec seulement des intersections finies...

Définition :

Appelons piquage partiel d'un tel couple [tex:64a592ed8d](X, T)[/tex:64a592ed8d] une famille d'éléments non vides et deux à deux disjoints de [tex:64a592ed8d]T[/tex:64a592ed8d].
Un piquage est un piquage partiel maximal, ie tel qu'il existe au plus un élément de [tex:64a592ed8d]T[/tex:64a592ed8d] qui ne rencontre aucun élément du piquage : le vide.

Lemme 1 :
Tout piquage partiel de [tex:64a592ed8d](X, T)[/tex:64a592ed8d] peut être prolongé en un piquage.

Lemme 2 :
Si tout piquage de [tex:64a592ed8d](X, T)[/tex:64a592ed8d] est fini, alors c'est encore le cas de [tex:64a592ed8d](F, T \cap \mathcal P (F))[/tex:64a592ed8d], pour [tex:64a592ed8d]F \in T[/tex:64a592ed8d].
(Preuve : un piquage du second est un piquage partiel du premier.)

Lemme 3 :

Si [tex:64a592ed8d](F_i)_{i \in I}[/tex:64a592ed8d] est un piquage de [tex:64a592ed8d](X, T)[/tex:64a592ed8d] et que, pour [tex:64a592ed8d]i \in I[/tex:64a592ed8d], [tex:64a592ed8d](F_{i, j})_{j \in J_i}[/tex:64a592ed8d] est un piquage de [tex:64a592ed8d](F_i, T \cap \mathcal P (F_i))[/tex:64a592ed8d], alors la famille de tous les [tex:64a592ed8d]F_{i, j}[/tex:64a592ed8d] est un piquage de [tex:64a592ed8d](X, T)[/tex:64a592ed8d].
Preuve : le fait qu'il s'agisse d'éléments de [tex:64a592ed8d]T[/tex:64a592ed8d] n'est pas un scoop, le fait qu'ils soient disjoints non plus, et la maximalité n'est pas bien difficile à montrer...

Lemme 4 :
Soient [tex:64a592ed8d](F_i)_{i \in I}[/tex:64a592ed8d], [tex:64a592ed8d](G_j)_{j \in J}[/tex:64a592ed8d] deux piquages de [tex:64a592ed8d](X,T)[/tex:64a592ed8d].
Alors la famille [tex:64a592ed8d](F_i \cap G_j)_{(i, j) \in I \times J}[/tex:64a592ed8d], une fois épurée de ses éléments vides, est un piquage de [tex:64a592ed8d](X, T)[/tex:64a592ed8d].

Preuve : même tonneau que le précédent, il faut d'ailleurs l'utiliser pour prouver la maximalité.

À présent, supposons que [tex:64a592ed8d](X, T)[/tex:64a592ed8d] admette des piquages finis arbitrairement grands.

Maintenant, on va construire un arbre, dont les sommets sont étiquetés par des éléments non vides de [tex:64a592ed8d]T[/tex:64a592ed8d], de telle sorte que la famille des étiquettes des sommets d'un même niveau forme un piquage de [tex:64a592ed8d](X, T)[/tex:64a592ed8d].
On le par récurrence sur le niveau :

Le niveau 0 est constitué d'un seul nœud, étiqueté par [tex:64a592ed8d]X[/tex:64a592ed8d]. Il forme bien un piquage de [tex:64a592ed8d](X, T)[/tex:64a592ed8d].
Supposons avoir construit les niveaux jusqu'à [tex:64a592ed8d]k[/tex:64a592ed8d].
Soit [tex:64a592ed8d](x_i)_{i \in I}[/tex:64a592ed8d] la famille des nœuds du niveau [tex:64a592ed8d]k[/tex:64a592ed8d], et [tex:64a592ed8d](F_i)_{i \in I}[/tex:64a592ed8d] le piquage formé par leurs étiquettes.
Par hypothèse, on a piquage fini de cardinalité strictement supérieure, [tex:64a592ed8d](G_j)_{j \in J}[/tex:64a592ed8d].
On place alors, pour [tex:64a592ed8d]j \in J[/tex:64a592ed8d] et [tex:64a592ed8d]i \in I[/tex:64a592ed8d], un sommet étiqueté par [tex:64a592ed8d]F_i \cap G_j[/tex:64a592ed8d] comme fils de [tex:64a592ed8d]x_i[/tex:64a592ed8d] dès que [tex:64a592ed8d]F_i \cap G_j[/tex:64a592ed8d] est non vide.
Par le lemme 4, il s'agit bien d'un piquage de [tex:64a592ed8d](X, T)[/tex:64a592ed8d].

Trois choses à montrer :
1) Chaque nœud a au moins un fils.
En effet, si un [tex:64a592ed8d]F_i[/tex:64a592ed8d] ne rencontrait aucun des [tex:64a592ed8d]G_i[/tex:64a592ed8d], il contredirait la maximalité de [tex:64a592ed8d](G_j)_{j \in J}[/tex:64a592ed8d].
2) La taille des niveaux est strictement croissante. En effet, chaque [tex:64a592ed8d]G_j[/tex:64a592ed8d] rencontre au moins un [tex:64a592ed8d]F_i[/tex:64a592ed8d] (même argument que précédemment), donc donne naissance à un nœud de génération [tex:64a592ed8d]k+1[/tex:64a592ed8d].
3) L'arbre est à branchement fini, ie chaque sommet de l'arbre n'a qu'un nombre fini de fils. Évident par construction.

Par une variante du lemme de König, l'arbre admet une branche contenant une infinité de nœuds qui ont au moins deux fils.

Soit donc [tex:64a592ed8d](x_n)_{n \in \mathbb N}[/tex:64a592ed8d] une telle branche (ordonnée comme on pense, ie avec [tex:64a592ed8d]x_0[/tex:64a592ed8d] la racine, et [tex:64a592ed8d]x_{n+1}[/tex:64a592ed8d] fils de [tex:64a592ed8d]x_n[/tex:64a592ed8d]) et [tex:64a592ed8d]\varphi : \mathbb N \to \mathbb N[/tex:64a592ed8d] extractrice telle que, pour [tex:64a592ed8d]n \in \mathbb N[/tex:64a592ed8d], [tex:64a592ed8d]x_{\varphi (n)}[/tex:64a592ed8d] a au moins deux fils.
Posons alors, pour [tex:64a592ed8d]n \in \mathbb N[/tex:64a592ed8d], [tex:64a592ed8d]G_n[/tex:64a592ed8d] l'étiquette d'un fils de [tex:64a592ed8d]x_{\varphi (n)}[/tex:64a592ed8d] autre que [tex:64a592ed8d]x_{\varphi (n) +1}[/tex:64a592ed8d].

Alors [tex:64a592ed8d](G_n)_{n \in \mathbb N}[/tex:64a592ed8d] est un piquage partiel infini de [tex:64a592ed8d](X, T)[/tex:64a592ed8d].
_________________
"“The Sith who were famous for being bad, Jacen, were the way they were because they were badly damaged men or women to start with. Not because they were Sith. Usually, they were weak, or deluded, or greedy to begin with. Like your grandfather.”"
Shira Brie aka Lumiya aka Brisha Syo, Legacy of the Force, #1: Betrayal
Revenir en haut
Voir le profil de l'utilisateur Envoyer un message privé Envoyer l'e-mail
Montrer les messages depuis:   
Poster un nouveau sujet   Répondre au sujet    Maths et Délires Index du Forum -> Mathématiques olympiques Toutes les heures sont au format GMT + 2 Heures
Page 1 sur 1

 
Sauter vers:  
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


Powered by phpBB © 2001, 2005 phpBB Group
Traduction par : phpBB-fr.com