Univ. Lille 1 - Licence Informatique S3/S3H 2ème année 2015-2016 Mathématiques
Univ. Lille 1 - Licence Informatique S3/S3H 2ème année 2015-2016 Mathématiques Discrètes Devoir surveillé no 2— le 8 janvier 2016 Prenez le temps de lire ce sujet. Ce devoir comporte 5 exercices. Les questions sont indépendantes pour la plupart. L’énoncé est un peu long mais le barème est sur 22 points. Exercice 1 [3 points] Un restaurant propose sur sa carte “une farandole de desserts”. le consommateur doit choisir cinq desserts parmi les six desserts suivants : dame blanche ; gueule noire ; orange givrée ; tarte au sucre brun ; bavarois à la violette ; crème aux marrons. Les répétitions sont autorisées. On peut donc faire le choix de prendre –par exemple– quatre dames blanches et une gueule noire... Q 1.1 [1 point] Combien de choix différents sont possibles ? Éléments de réponse Il y avait deux manière de comprendre le sujet. implicitement on ne souhaitait pas tenir compte de l’ordre et on considerait que les plats de la farandole étaient servis en même temps. Certain ont fait le choix de tenir compte de l’ordre, ces réponses, pourvu qu’elles soient cohérentes, ont été admises. 6 variétés de desserts, donc 5 barres pour séparer les variétés, 5 choix à faire donc 5 points 10 5 = 252 Q 1.2 [1 point] Marie-Paule aime le parfum de la violette, elle souhaite choisir un dessert où il y a au moins deux fois du bavarois à la violette. Combien a-t-elle de choix différents ? Éléments de réponse elle choisit déjà deux bavarois à la violette et elle complète les 3 desserts restants. 6 variétés de desserts, donc 5 barres pour séparer les variétés, 3 choix à faire donc 3 points 8 3 = 56 Q 1.3 [1 point] Renaud souhaite éviter de prendre trois fois ou plus le même plat. Combien a-t-il de choix ? Éléments de réponse – soit il prend au plus une fois chaque plat. il y a 6 5 = 6 manières de le faire. – soit il prend un plat deux fois et trois autres plats il y a 6 5 5 3 = 60 – soit il prend deux plats deux fois et un autre plats il y a 6 5 5 2 = 60 au total cela fait 126 Exercice 2 [4 points] Q 2.1 [1 point] Soit S une partie de N de cardinal au moins 3. Prouvez qu’il existe deux éléments x,y de S tels que x + y soit pair. Éléments de réponse la somme de deux entiers de même parité donne un entier pair. On classe les éléments de S en deux classes les entiers pairs et les entiers impairs. Comme il y a au moins trois éléments dans S l’une des deux classes contient au moins deux éléments. Il y a donc dans S deux entiers de même parité... Q 2.2 [1 point] On considère maintenant une partie de N × N. Quel est le nombre minimal d’éléments de S permettant de garantir l’existence de (x1, x2) et (y1, y2), deux éléments de S, tels que les deux sommes (x1 + y1) et (x2 + y2) soient paires. Éléments de réponse 1 On reproduit le même raisonnement mais on fait cette fois ci 4 classes. – PP les couples dont les deux composantes sont paires – PI les couples dont la premiere composante est paire et la seconde composante est impaire – IP les couples dont la premiere composante est impaire et la seconde composante est paire – II les couples dont les deux composantes sont impaires dès qu’on a 5 éléments, on est assuré qu’il existe au moins une classe qui contient deux éléments. Or la somme de deux éléments d’une classe donne un couple dont les deux composantes sont paire. Cela nous permet d’affirmer qu’à partir de 5 éléments on est sûr de l’existence des deux couples souhaités. en considérant la partie S = {(0, 0), (0, 1), (1, 0), (1, 1)} on constate que 4 couples ne permettent pas d’assurer l’existence (il faut former les 4 2 = 6 sommes possibles) Q 2.3 [1 point] On considère une famille S de points du plan dont les coordonnées sont entières (toutes les deux !). Combien faut-il de points au minimum dans S pour être sûr qu’il existe un segment dont le milieu soit aussi à coordonnées entières ? Éléments de réponse C’est la question précédente. (si la somme est paire, la demi-somme est entière) Q 2.4 [1 point] Soit n un entier naturel non nul. On considère maintenant une partie de Nn. Quel est le nombre minimal d’éléments de S permettant de garantir l’existence de (x1, x2, ..., xn) et (y1, y2, ..., yn) deux éléments de S telles que les n sommes (x1 + y1) et (x2 + y2), ... , (xn + yn) soient paires ? Éléments de réponse On généralise sans difficulté particulière le raisonnement précédent. il faudra 2n + 1 points. Exercice 3 [5 points] Le langage de programmation Brainfuck est un langage de programmation sur un alphabet à 8 symboles. Q 3.1 [1 point] n désigne un entier naturel. Combien y a-t-il de mots de n lettres sur cet alphabet ? Éléments de réponse 8n L’alphabet considéré contient un crochet ouvrant et un crochet fermant. La seule règle de syntaxe est que les crochets ouvrants "[" et crochets fermants "]" doivent se correspondre, formant ainsi un mot bien parenthésé. Q 3.2 [1 point] Combien de mots bien parenthésés, différents et de longueur 2k contenant uniquement des crochets peut-on écrire ? Éléments de réponse 1 k + 1 2k k On suppose k ≤n 2 . Q 3.3 [1 point] Combien de mots de longueur n−2k peut-on écrire avec les 6 symboles restants ? Éléments de réponse 6n−2k Q 3.4 [1 point] Combien de programmes Brainfuck de longueur n , possédant k crochets ouvrants, syntaxiquement corrects, peut-on écrire ? Éléments de réponse 2 1 k + 1 2k k 6n−2k n 2k Q 3.5 [1 point] Combien de programmes Brainfuck de longueur n , syntaxiquement corrects, peut-on écrire ? On donnera le résultat sous la forme d’une somme qu’on ne cherchera pas à calculer. Éléments de réponse ⌊n 2 ⌋ X k=0 1 k + 1 2k k 6n−2k n 2k Exercice 4 [3 points] Dans cet exercice f désigne une fonction de N dans N. f est dite a support fini lorsqu’il existe un entier n tel que pour tout entier k tel que k ≥n on ait f(k) = 0. Sous forme mathématique, cela s’écrit : ∃n ∈N ∀k ∈N k ≥n = ⇒f(k) = 0 On s’intéresse à l’ensemble F0(N) des fonctions f de N dans N à support fini. Q 4.1 [1 point] Donnez une traduction mathématique de g n’est pas à support fini. Éléments de réponse On rappelle que la négation de l’implication a = ⇒b est a ∧¬b. Par conséquent, on peut écrire la négation de g est à support fini. ∀n ∈N ∃k ∈N k ≥n ∧f(k) ̸= 0 Q 4.2 [1 point] Soit n un entier fixé. Combien y a-t-il de fonctions f de F0(N) telles qu’on ait à la fois – ∀k ∈N k ≥n = ⇒f(k) = 0 – ∀k ∈N f(k) ≤n. Éléments de réponse (n + 1)n Q 4.3 [1 point] Démontrez que l’ensemble F0(N) est dénombrable. Éléments de réponse Il suffit de montrer que F0(N) est réunion dénombrable d’ensemble finis ou dénombrables. Si on note Kn les ensembles précédents. On a Kn fini pour tout entier n et par ailleurs F0(N) = ∪n∈NKn Exercice 5 [7 points] Soient f et g deux fonctions de N dans N . On définit sur l’ensemble des fonctions de N dans N une relation binaire de la manière suivante : f R g ⇐ ⇒∃n ∈N ∀k ∈N k ≥n = ⇒f(k) = g(k). Lorsque f R g, on dira que f est ultimement égale à g. Q 5.1 [4 points] Quelles propriétés possède la relation R ainsi définie ? Éléments de réponse 3 – elle est reflexive f R f car ∀k ∈Nf(k) = f(k). donc on peut prendre comme rang n = 0 – elle est symétrique car f(k) = g(k) ⇐ ⇒g(k) = f(k) – elle est transitive car si f R g alors ∃n1 ∈N ∀k ∈N k ≥n1 = ⇒f(k) = g(k). si g R h alors ∃n2 ∈N ∀k ∈N k ≥n2 = ⇒g(k) = h(k). En prenant n = max(n1, n2) on a : ∀k ∈N k ≥n = ⇒f(k) = h(k). – elle n’est pas antisymétrique. Contre exemple : soit f la fonction définie par f(0) = 1 et f(n) = 0 si n ≥1. fR0 et 0Rf mais f ̸= 0 Q 5.2 [1 point] La relation R est-elle une relation d’équivalence ? Éléments de réponse oui, car elle est à la fois reflexive, symétrique et transitive. Q 5.3 [1 point] La relation R est-elle une relation d’ordre ? Éléments de réponse Non, uploads/Religion/ 15-16-ds-2-avec.pdf
Documents similaires
-
10
-
0
-
0
Licence et utilisation
Gratuit pour un usage personnel Attribution requise- Détails
- Publié le Jul 17, 2022
- Catégorie Religion
- Langue French
- Taille du fichier 0.2270MB