Probl`emes de Math´ematiques Chaˆınes et antichaˆınes dans un ensemble fini. ´Enonc´e Chaˆınes et antichaˆınes dans un ensemble fini. Dans le probl`eme, E d´esigne un ensemble fini non vide de cardinal n. – Deux parties A, B de E seront dites comparables si A ⊂ B ou B ⊂ A. – Soit F une partie non vide de P(E). On dit que F est une chaˆıne si les ´el´ements de F sont deux `a deux comparables. On dit que F est une antichaˆıne si les ´el´ements de F sont deux `a deux non comparables. – Le cardinal d’une chaˆıne (d’une antichaˆıne) sera appel´e sa longueur. – Par exemple, si E = {1, 2, 3, 4, 5, 6, 7, 8, 9} : F = {∅, {2, 5}, {2, 3, 5, 7, 8}, {2, 3, 5}, {5}} est une chaˆıne de E, de longueur 5. F = {{2, 5}, {3, 5, 7}, {5, 8}, {2, 4, 9}, {6}, {1}} est une antichaˆıne de E, de longueur 6. Chaˆınes maximales 1. (a) Montrer qu’une partie F de P(E) est une chaˆıne de longueur r ≥ 1 si et seulement si elle s’´ecrit F = {X1, X2, . . . , Xr}, o`u X1 ⊊ X2 ⊊ · · · ⊊ Xr. [ S ] (b) Pr´eciser quelle est la longueur maximum d’une chaˆıne de E. Dans la suite du probl`eme, on dira d’une telle chaˆıne qu’elle est maximale. [ S ] (c) Donner la liste de toutes les chaˆınes maximales de l’ensemble {a, b, c}. [ S ] 2. Soit f une bijection de {1, . . . , n} sur l’ensemble E. Si 0 ≤ k ≤ n, on note Nk = {1, . . . , k} (donc N0 = ∅), et Xk = f(Nk). (a) Montrer qu’on d´efinit ainsi une chaˆıne maximale de E, que l’on notera Ff. [ S ] (b) Montrer que l’application qui `a f associe Ff est une bijection (de l’ensemble des bijections de {1, . . . , n} sur E vers l’ensemble des chaˆınes maximales de E.) [ S ] (c) D´eduire de ce qui pr´ec`ede le nombre de chaˆınes maximales de E. [ S ] 3. Soit A une partie de E, et soit F une chaˆıne maximale de E. On dit que F passe par A si l’ensemble A est l’un des ´el´ements de la famille F. (a) ´Enum´erer les chaˆınes maximales de {a, b, c, d, e} qui passent par {a, b, c}. [ S ] (b) Si card A = m, pr´eciser combien de chaˆınes maximales de E passent par A. [ S ] Antichaˆınes Dans cette partie, on se propose de d´emontrer le th´eor`eme de Sperner (1928) : La longueur maximum d’une antichaˆıne d’un ensemble de cardinal n est � n [n/2] � . 1. On rappelle que [x] d´esigne la partie enti`ere de x. (a) Montrer que � n [n/2] � est le maximum des �n k � , avec 0 ≤ k ≤ n. [ S ] (b) Montrer qu’il existe dans E une antichaˆıne de longueur � n [n/2] � . [ S ] Page 1 Jean-Michel Ferrard www.klubprepa.net c⃝EduKlub S.A. Tous droits de l’auteur des œuvres r´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation individuelle et priv´ee sont interdites.