COMBINATOIRE: CORRIGÉ DE L'EXAMEN DE JANVIER 2006. Q1. Si en tête du sujet j'ai donné le rappel de la formule d'inclusion-exclusion, ce n'est pas pour faire étalage de ma culture, mais pour qu'on l'utilise ! (Par ailleurs, lors de la dernière heure de cours, avantageusement brossée par plus de 90% de la promotion, j'ai fait quelques exercices pour expliciter cette formule pour 3 ou 4 ensembles.) Soient les ensembles: - E de tous les étudiants ; - B de ceux qui font du basket ; - V de ceux qui font du volley ; - G de ceux qui font de la gym. L'énoncé dit sans ambiguité que : card(E \ [B U V U G]) = 12 , card(B) = 17 , card(V) = 15 , card(G) = 12 , card(B ^ V) = 7 , card(B ^ G) = 5 , card(V ^ G) = 4 , card(B ^ V ^ G) = 3 . Donc la formule d'inclusion-exclusion donne le nombre de sportifs: card(B U V U G) = card(B) + card(V) + card(G) - card(B ^ V) - card(B ^ G) - card(V ^ G) + card(B ^ V ^ G) = 17 + 15 + 12 - 7 - 5 - 4 + 3 = 31 . Donc le nombre total d'étudiants est : card(E \ [B U V U G]) + card(B U V U G) = 12 + 31 = 43 . Q2. La relation d'équivalence engendrée par une relation R est la plus petite relation d'équivalence contenant R, c.-à-d. l'intersection des relations d'équivalence contenant R. Donc cette relation d'équivalence engendrée par R existe toujours ! NB. Quand on parle d'inclusion, d'intersection, de plus petit, etc., pour des relations sur un ensemble E, on considère une relation R comme un ensemble de couples, en fait R = { (a,b) dans ExE | a R b }. Ici R est sur N, donnée par a R b ssi b = a+4. La relation d'équivalence S engendrée par R est la congruence modulo 4: a S b ssi b-a est un multiple de 4. a) Montrons que toute relation d'équivalence T contenant R doit contenir S. Montrons d'abord par récurrence sur n dans N que pour tout m dans n on a m T m+4n. n=0: Par réflexivité, m T m = m+4x0. Si vrai pour n, vrai pour n+1: Par hypothèse d'induction, m T m+4n. Par définition, m+4n R m+4n+4 = m+4(n+1), et comme T contient R, m+4n T m+4(n+1). Par transitivité, m T m+4(n+1). Soient a et b dans N tels que a S b, c.-à-d. b-a soit un multiple de 4. Si b >= a, b = a+4n pour n dans N, donc a T b comme montré ci-dessus. Si b < a, a = b+4n pour n dans N, donc b T a comme montré ci-dessus, et par symétrie on obtient a T b. b) Montrons que S est une relation d'équivalence contenant R: Réflexivité: a-a = 0, multiple de 4, donc a S a. Symétrie: si a S b, alors b-a est multiple de 4, donc a-b = -(b-a) est multiple de 4, ainsi b S a. Transitivité: si a S b et b S c, alors b-a et c-b sont multiples de 4, donc c-a = (c-b)+(b-a) est multiple de 4, ainsi a S c. Contient R: si a R b, alors b = a+4, donc b-a=4, multiple de 4, ainsi a S b. Comme S est une relation d'équivalence contenant R, et que toute autre relation d'équivalence contenant R doit contenir S, S est bien la plus petite: la relation d'équivalence engendrée par R. 3)a) La formule binomiale donne : n --- \ /n\ k n-k n n / \k/ (-2) 3 = (-2 + 3) = 1 = 1 . --- k=0 3)b) On utilise : /n\ / n \ \k/ = \n-k/ . Aussi en posant p = n-k, (n-1)/2 (n-1)/2 n --- --- --- \ /n\ \ / n \ \ /n\ / \k/ = / \n-k/ = / \p/ --- --- --- k=0 k=0 p=(n+1)/2 Ce qui donne : (n-1)/2 (n-1)/2 n n --- --- --- --- \ /n\ \ /n\ \ /n\ \ /n\ n 2 / \k/ = / \k/ + / \p/ = / \p/ = 2 . --- --- --- --- k=0 k=0 p=(n+1)/2 p=0 Finalement, (n-1)/2 --- \ /n\ n-1 / \k/ = 2 . --- k=0 4) Lors de la dernière heure de cours, répétons-le : avantageusement brossée par plus de 90% de la promotion, j'ai aussi expliqué que comme b est congru à 1 modulo b-1 et à -1 modulo b+1, on a b^n congru à 1 modulo b-1 et à (-1)^n modulo b+1, donc un nombre s'écrivant a_n...a_0 en base b est congru à a_n + ... + a_0 modulo b-1 et à a_0 -a_1 + ... + (-1)^n a_n modulo b+1. Dans le cas classique de b=10 (numérotation décimale), on obtient les fameuses "preuve par 9" et "preuve par 11" qu'on voit en collège. Donc : 123456789 est congru modulo 9 à 1+2+3+4+5+6+7+8+9 = 45, multiple de 9, c.-à-d. congru à 0. 123456789 est congru modulo 11 à 9-8+7-6+5-4+3-2+1 = 5. Il est ainsi inutile de faire une division.