Διακριτά Μαθηματικά — Ιανουάριος 2023 — Ομάδα Δ¶

Μεταγραφή από τις σελίδες 7–8 του αρχείου Discrete_Exams_January_23.pdf.

Discrete_Exams_January_23.pdf (σελ. 7-8)¶

ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ ΕΞΕΤΑΣΗ ΣΤΟ ΜΑΘΗΜΑ «ΔΙΑΚΡΙΤΑ ΜΑΘΗΜΑΤΙΚΑ» - 31/01/2023 Ομάδα Δ (Διάρκεια Εξέτασης 2 ώρες και 30 λεπτά)$^4$

Στις παρακάτω ασκήσεις, δεν χρειάζεται να υπολογίζετε τις ακριβής αριθμητικές τιμές εκτός και αν σας ζητείται ρητά. Σε κάθε περίπτωση, απαγορεύεται η χρήση οποιασδήποτε υπολογιστικής μηχανής.

1.(1,5) α) (0,5) Να βρείτε την αριθμητική τιμή του εξής αθροίσματος: $\sum_{i=7}^{100}(2i + 1)$ β) (1) Να αποδείξετε με επαγωγή ότι ο κλειστός τύπος του αθροίσματος $S_n = \sum_{j=0}^{n} j 2^j$ είναι ο $S_n = (n - 1)2^{n+1} + 2$

2.(0,5) Έστω ότι μας δίνονται οι εξής προτάσεις ως αξιώματα: $$y \to \neg x$$ $$z \to (y \land x)$$ Να δείξετε αν από αυτά τα αξιώματα προκύπτει (με κανόνες εξαγωγής συμπερασμάτων) η εξής πρόταση: $$\neg z$$ Να αναγράφετε τον κανόνα εξαγωγής συμπεράσματος ή ταυτολογία που χρησιμοποιείτε κάθε φορά.

3.(1,5) Έστω ο παρακάτω ορισμός: Ένας ακέραιος $n$ καλείται φοβερός αν ισχύει ότι $3 | n^2 + 2n$. Να αποδείξετε αν ισχύουν ή όχι οι παρακάτω προτάσεις, αναφέροντας τον τύπο απόδειξης που χρησιμοποιείτε κάθε φορά: α) (0,4) Όλοι οι περιττοί αριθμοί είναι φοβεροί. β) (0,6) Αν για κάποιον ακέραιο $j$ ισχύει ότι $n = 3j + 2$, τότε ο $n$ δεν είναι φοβερός. γ) (0,5) Αν $6 | n$, τότε ο $n$ είναι φοβερός.

4.(1) Έστω ότι το $Z$ είναι ένα σύνολο με $k$ στοιχεία και έστω ότι $P(Z)$ είναι το δυναμοσύνολό του. Ορίζουμε τη σχέση $R$ πάνω στο $P(Z)$ ως εξής: $(A, B) \in R$ αν $|A| = |B|$. α) (0,5) Να δείξετε ότι η $R$ είναι μία σχέση ισοδυναμίας. β) (0,5) Η διαμέριση που ορίζει η $R$ στο $P(Z)$ πόσες κλάσεις ισοδυναμίας έχει;

5.(1,5) Έστω τα παρακάτω κατηγορήματα με τομέα αναφοράς όλους τους φυσικούς αριθμούς: $P(p)$: ο $p$ είναι πρώτος $Q(p, q)$: ο $p$ διαιρεί τον $q$ ($p|q$) Έστω η εξής δήλωση: Για κάθε φυσικό αριθμό που δεν είναι πρώτος, υπάρχει κάποιος πρώτος που τον διαιρεί. α) (0,3) Γράψτε τη δήλωση ως λογική πρόταση χρησιμοποιώντας τα δοθέντα κατηγορήματα. β) (0,3) Συμπληρώστε τη λογική πρόταση από το ερώτημα (α) (εφαρμόστε την πράξη της άρνησης σε όλη την λογική πρόταση) και κάντε τις απλοποιήσεις ώστε να μην υπάρχει η πράξη της άρνησης μπροστά από ποσοδείκτη ή από παρένθεση. γ) (0,2) Γράψτε τη λογική πρόταση του ερωτήματος (β) σε φυσική γλώσσα (χωρίς να χρησιμοποιείτε ονόματα μεταβλητών). δ) (0.7) Αποδείξτε αν ισχύουν ή όχι καθένα από τα παρακάτω θεωρήματα: $$\forall p \forall q ((P(p) \land Q(q, p)) \to P(q))$$ $$\forall p \forall q ((P(q) \land Q(q, p)) \to P(p))$$ Υπόδειξη: Ο αριθμός 1 δεν είναι πρώτος.

$^4$ Αν θεωρείτε ότι υπάρχει κάποιο πρόβλημα στην εκφώνηση, τότε λύστε την άσκηση κάνοντας κάποια συγκεκριμένη υπόθεση την οποία θα καταγράψετε ρητά. Αν ο διδάσκων καταλάβει ότι υπάρχει κάποια ασάφεια, το θέμα θα δοθεί ολόκληρο υπέρ των φοιτητών βαθμολογικά.

6.(4) α) (0,8) Αποδείξτε συνδυαστικά ότι $\binom{k}{n} \binom{n}{m} = \binom{k}{m} \binom{k - m}{n - m}$. β) (1,8) Απαντήστε τις παρακάτω ερωτήσεις με συνοπτική αιτιολόγηση. 1. (0,4) Πόσες διαφορετικές λέξεις μπορούμε να φτιάξουμε χρησιμοποιώντας όλα τα γράμματα της λέξης ΞΕΧΑΣΑ; 2. (0,4) Πόσοι αριθμοί μεταξύ του 1 και του 180 (συμπεριλαμβανομένου και αυτών των αριθμών) διαιρούνται τέλεια από το 9 ή το 8; 3. (1) Σε ένα παιδικό πάρτι, έχουν έρθει 34 παιδιά, 14 αγόρια και 20 κορίτσια, τα οποία θεωρούμε διακεκριμένα. a. (0,2) Με πόσους τρόπους μπορούμε να μοιράσουμε 100 (ίδιες) καραμέλες στα 34 παιδιά; b. (0,4) Με πόσους τρόπους μπορούμε να σχηματίσουμε 8 ζευγάρια παιδιών, για να χορέψουν, ώστε κάθε ζευγάρι να αποτελείται από ένα διαφορετικό αγόρι και ένα διαφορετικό κορίτσι (δηλ. δεν μπορεί το ίδιο παιδί να συμμετέχει σε δύο ή περισσότερα ζευγάρια); c. (0,4) Με πόσους τρόπους μπορούμε να βάλουμε όλα τα παιδιά σε μία σειρά, ώστε να μην υπάρχουν δύο ή περισσότερα αγόρια σε διαδοχικές θέσεις; γ) (0,6) Με πόσους τρόπους μπορούμε να επιλέξουμε $n$ αντικείμενα από $r$ διαφορετικά αντικείμενα έτσι ώστε στις επιλογές ποτέ να μην βρίσκονται ταυτόχρονα 2 συγκεκριμένα αντικείμενα (αυτά τα αντικείμενα έχουν εκ των προτέρων καθορισθεί). δ) (0,8) Έστω μία σκακιέρα $3 \times 7$ που διαιρείται σε 21 ίσα τετράγωνα ($3 \times 7 = 21$), καθένα από τα οποία χρωματίζεται είτε άσπρο είτε γκρι. Να δείξετε ότι η σκακιέρα περιέχει ένα ορθογώνιο του οποίου τα τέσσερα διαφορετικά τετράγωνα που ορίζουν τα άκρα του έχουν το ίδιο χρώμα. (Προσοχή: το ορθογώνιο πρέπει να έχει διάσταση τουλάχιστον δύο γραμμών και τουλάχιστον δύο στηλών – το ορθογώνιο στο σχήμα είναι 3x4)

[Σχήμα: Σκακιέρα πλέγματος 3x7 με 21 τετράγωνα. Ένα ορθογώνιο 3x4 περιβάλλεται από έντονο περίγραμμα, με τις τέσσερις γωνίες του (τετράγωνα) χρωματισμένες γκρι.]

(1,5) Θέλουμε να μετρήσουμε τους διαφορετικούς τρόπους με τους οποίους μπορούμε να παρκάρουμε 50 αυτοκίνητα σε 80 θέσεις στάθμευσης (προφανώς κάθε θέση στάθμευσης μπορεί να χρησιμοποιηθεί από το πολύ ένα αυτοκίνητο) σε κάθε μία από τις παρακάτω περιπτώσεις (δεν χρειάζεται να κάνετε αριθμητικές πράξεις, ο τύπος αρκεί):
Τα αυτοκίνητα και οι θέσεις στάθμευσης είναι διαφορετικές.
Τα αυτοκίνητα είναι ίδια αλλά οι θέσεις στάθμευσης είναι διαφορετικές.
Τα αυτοκίνητα είναι διαφορετικά αλλά οι θέσεις στάθμευσης είναι ίδιες.
Τα αυτοκίνητα είναι ίδια και οι θέσεις στάθμευσης είναι ίδιες.

Καλή Επιτυχία!!!

Λύσεις (🟢 official)

Κατάσταση: 🟢 official Πηγή: ενδεικτικές λύσεις (σελίδες 9–11 του αρχείου «Discrete_Exams_January_23.pdf»)

Προσοχή

Το κλειδί (σελ. 9–11) καλύπτει όλες τις ομάδες Α–Δ· η ενότητα της Ομάδας Δ πρέπει να επιλεγεί από το κείμενο.

Λύσεις — Διακριτά Μαθηματικά — Ιανουάριος 2023 — Ομάδα Δ¶

Discrete_Exams_January_23.pdf (σελ. 9-11)¶

ΕΝΔΕΙΚΤΙΚΕΣ ΛΥΣΕΙΣ¶

Α(1), Β(5), Γ(3), Δ(7) Στην πραγματικότητα πρόκειται περί προβλήματος απαρίθμησης που αφορά τους τρόπους που μπορούμε να τοποθετήσουμε 6 σφαίρες (αυτοκίνητα) σε 9 υποδοχές (θέσεις στάθμευσης) με τον περιορισμό ότι κάθε υποδοχή δέχεται το πολύ μία σφαίρα σε τέσσερις διαφορετικές περιπτώσεις. Για κάθε περίπτωση έχουμε: 1. Για κάθε διαφορετικό αυτοκίνητο επιλέγουμε μία θέση στάθμευσης. Επειδή τα αυτοκίνητα είναι διαφορετικά μας ενδιαφέρει η σειρά με την οποία θα επιλέξουμε τις θέσεις, και δεν έχουμε επανατοποθέτηση αφού κάθε θέση στάθμευσης μπορεί να αντιστοιχηθεί σε το πολύ ένα αυτοκίνητο. Άρα έχουμε μία x-μετάθεση από ένα y-σύνολο. Άρα η λύση είναι $P(y, x) = \frac{y!}{(y-x)!}$ 2. Τώρα που τα αυτοκίνητα είναι ίδια κάνουμε ότι και στο 1ο ερώτημα μόνο που τώρα δεν μας ενδιαφέρει η σειρά με την οποία θα επιλέξουμε τις θέσεις στάθμευσης. Άρα έχουμε ένα πρόβλημα απαρίθμησης όπου δεν μας ενδιαφέρει η σειρά και δεν έχουμε επανατοποθέτηση. Επομένως η λύση είναι ένας x-συνδυασμός από ένα y-σύνολο: $C(y, x) = \frac{y!}{(y-x)! \cdot x!}$ 3. Αφού οι θέσεις στάθμευσης είναι ίδιες, υπάρχει μόνο ένας τρόπος να παρκάρουμε τα αυτοκίνητα – παρόλο που αυτά είναι διαφορετικά μεταξύ τους μιας και δεν έχουμε κάποιο τρόπο να διακρίνουμε μία θέση από κάποια άλλη. Επομένως, υπάρχει μόνο ένας τρόπος να τα τοποθετήσετε. 4. Το ίδιο με το (3). Το γεγονός ότι και τα αυτοκίνητα είναι όλα ίδια δεν αλλάζει κάτι. Επομένως, με έναν τρόπο μπορεί να γίνει αυτή η τοποθέτηση.

Α(2), Β(3), Γ(1), Δ(4) α) Θα δείξουμε ότι έχει τις τρεις σχετικές ιδιότητες: Ανακλαστική: Ισχύει για κάθε $A \in P(X)$ ότι $|A| = |A|$. Συμμετρική: Για $A, B \in P(X)$ αν ισχύει ότι $(A, B) \in R$ τότε $|A| = |B|$. Άρα ισχύει ότι $|B| = |A|$ το οποίο γράφεται ως $(B, A) \in R$. Άρα ισχύει. Μεταβατική: Για $A, B, \Gamma \in P(X)$ αν ισχύει ότι $(A, B) \in R$ και $(B, \Gamma) \in R$ τότε $|A| = |B|$ και $|B| = |\Gamma|$. Από τη μεταβατική ιδιότητα της ισότητας προκύπτει ότι $|A| = |\Gamma|$, το οποίο σημαίνει ότι $(A, \Gamma) \in R$. Άρα ισχύει. β) Οι κλάσεις ισοδυναμίας αποτελούνται από σύνολα που έχουν το ίδιο πληθάριθμο. Δεδομένου ότι το δυναμοσύνολο του $X$ περιέχει σύνολα με από 0 (το κενό σύνολο) μέχρι και $n$ στοιχεία (το σύνολο $X$) αυτό σημαίνει ότι το πλήθος των κλάσεων ισοδυναμίας θα είναι $n + 1$.

Α(3), Β(1), Γ(7), Δ(5) α) $\forall x ((\neg P(x)) \to (\exists y)(P(y) \land Q(y, x)))$ β) $\exists x ((\neg P(x)) \land (\forall y)(P(y) \to \neg Q(y, x)))$ ή $\exists x ((\neg P(x)) \land (\forall y)(\neg P(y) \lor \neg Q(y, x)))$ γ) Υπάρχει ένας σύνθετος αριθμός έτσι ώστε για κάθε πρώτο αριθμό, αυτός ο πρώτος να μη διαιρεί τον σύνθετο (πασιφανώς ψευδής πρόταση). δ) Η πρώτη πρόταση σε φυσική γλώσσα μεταφράζεται ως εξής: «Για κάθε ζεύγος φυσικών αριθμών $x$ και $y$, αν ο $x$ είναι πρώτος και ο $y$ διαιρεί τον $x$ τότε και ο $y$ είναι πρώτος». Η πρόταση αυτή είναι ψευδής, αφού αν θέσουμε $y = 1$ τότε όταν ισχύει η υπόθεση για x πρώτο, το συμπέρασμα δεν ισχύει αφού ο 1 δεν είναι πρώτος. Η δεύτερη πρόταση σε φυσική γλώσσα μεταφράζεται ως εξής: «Για κάθε ζεύγος φυσικών αριθμών $x$ και $y$, αν ο $y$ είναι πρώτος και ο $y$ διαιρεί τον $x$ τότε και ο $x$ είναι πρώτος». Αυτή η πρόταση είναι προφανώς λάθος. Ένα αντιπαράδειγμα είναι για $y = 5$ και $x = 10$, όπου το $x$ δεν είναι πρώτος αριθμός παρόλο που ο $y = 5$ είναι και διαιρεί το $x = 10$.

Α(4), Β(2), Γ(5), Δ(1) α) (Α) $\sum_{i=5}^{100} 2i + 1 = 2 \sum_{i=5}^{100} i + \sum_{i=5}^{100} 1 = 2 \sum_{i=1}^{100} i - 2 \sum_{i=1}^{4} i + 96 = 2 \frac{100 \cdot 101}{2} - 2 \frac{4 \cdot 5}{2} + 96 = 100 \cdot 101 + 76 = 10176$ (Β) 10165 (Γ) 10185

(Δ) 10152

β) Βάση: για $n = 0$ ισχύει αφού $\sum_{k=0}^{0} k 2^k = 0$ και $(0 - 1)2^{0+1} + 2 = -2 + 2 = 0$ που ισχύει. Επαγωγική υπόθεση: Έστω ότι ισχύει για $n = j$. Δηλαδή ισχύει ότι: $\sum_{k=0}^{j} k 2^k = (j - 1)2^{j+1} + 2$ Θα δείξουμε ότι ισχύει για $n = j + 1$. Έχουμε: $$\sum_{k=0}^{j+1} k 2^k = \sum_{k=0}^{j} k 2^k + (j + 1)2^{j+1} = (j - 1)2^{j+1} + 2 + (j + 1)2^{j+1} = 2^{j+1}(j - 1 + j + 1) + 2 = 2j 2^{j+1} + 2 = j 2^{j+2} + 2$$ που πράγματι είναι ο κλειστός τύπος για το άθροισμα που θέλουμε να αποδείξουμε.

Α(5), Β(7), Γ(2), Δ(3) α) Θα αποδείξουμε με αντιπαράδειγμα ότι δεν ισχύει. Πράγματι για $n = 5$, ισχύει ότι $5^2 + 2 \cdot 5 = 35$ που πράγματι δεν διαιρείται από το 3. β) Άμεση απόδειξη: Αφού $3|n$, θα υπάρχει ακέραιος $k$ έτσι ώστε $n = 3k$. Άρα: $$n^2 + 2n = 9k^2 + 6k = 3(3k^2 + 2k)$$ και άρα διαιρείται από το 3. Άρα, όλα τα πολλαπλάσια του 3 είναι φοβεροί αριθμοί. γ) Θα το αποδείξουμε με αντίφαση. Άρα, θα κάνουμε την εξής υπόθεση που θα μας οδηγήσει σε αντίφαση: Για κάποιον ακέραιο $j$ ισχύει ότι $n = 3j + 2$ και ο $n$ είναι φοβερός. Αφού $n = 3j + 2$ έχουμε: $$n^2 + 2n = (3j + 2)^2 + 2(3j + 2) = 9j^2 + 12j + 4 + 6j + 4 = 9j^2 + 18j + 8 = 9j^2 + 18j + 6 + 2 = 3(3j^2 + 6j + 2) + 2$$ Αυτό σημαίνει ότι ο αριθμός $n$ είναι της μορφής $3i + 2$ για κάποιον ακέραιο $i$. Επομένως, ο $n$ δεν είναι πολλαπλάσιο του 3 που έρχεται σε αντίφαση με την αρχική μας υπόθεση ότι ο $n$ είναι φοβερός. Άρα αποδείχτηκε η πρόταση ότι σε αυτή την περίπτωση ο $n$ δεν είναι φοβερός.

Α(6), Β(4), Γ(6), Δ(2) Ξεκινάμε από τα αξιώματα: 1. $p \to \neg q$ 2. $r \to (p \land q)$ Έχουμε: 3. $\neg p \lor \neg q$ (από ισοδυναμία συνεπαγωγής στο (1)) 4. $\neg (p \land q)$ (από De Morgan στο (3)) 5. $\neg r$ (από Modus Tollens μεταξύ (4) και (2))

Α(7), Β(6), Γ(4), Δ(6) α) Το αριστερό μέρος μετρά με πόσους τρόπους μπορούμε να επιλέξουμε k άτομα από μία ομάδα n ατόμων και από αυτά τα k θέλουμε m να είναι αρχηγοί. Αυτό μπορούμε να το μετρήσουμε και ως εξής: επιλέγουμε m αρχηγούς από τα n άτομα και έπειτα επιλέγουμε από τα υπόλοιπα n-m άτομα τα υπόλοιπα k-m που δεν είναι αρχηγοί. Αφού και οι δύο τρόποι μέτρησης αφορούν το ίδιο πρόβλημα προκύπτει η ισότητα. β) 1. Έχουμε 6 γράμματα και άρα όλες οι μεταθέσεις είναι $6!$. Όμως δύο γράμματα είναι ίδια και άρα έχουμε μετρήσει παραπάνω. Διαιρούμε με το $2!$ για να διώξουμε αυτά που μετρήσαμε 2 φορές (κανόνας διαίρεσης). Άρα η απάντηση είναι $\frac{6!}{2!}$. 2. 36 αριθμοί διαιρούνται από το 5, 22 από το 8 και 4 αριθμοί από το $40=5 \times 8$. Από εγκλεισμό-αποκλεισμό προκύπτει ότι το πλήθος είναι $36+22-4=54$. 3. a. Είναι 100-επιλογή από ένα 30-σύνολο. Άρα: $\binom{100 + 30 - 1}{100} = \binom{129}{100}$

b. Επιλέγουμε τα 8 αγόρια με $C(12, 8)$ τρόπους. Για κάθε τέτοια επιλογή, τα 8 αγόρια επιλέγουν από ένα κορίτσι το καθένα με $P(18, 8)$ τρόπους. Άρα, από τον κανόνα του γινομένου, έχουμε $C(12, 8) \cdot P(18, 8) = \frac{12! 18!}{8! 4! 10!}$ τρόπους συνολικά. c. Τοποθετούμε στη σειρά τα κορίτσια με $18!$ τρόπους. Κάθε αγόρι μπορεί να επιλέξει (χωρίς επανάληψη) μία από τις 19 διακεκριμένες θέσεις που σχηματίζονται (στην αρχή, μεταξύ δύο κοριτσιών ή στο τέλος). Άρα για κάθε σειρά των κοριτσιών, τα αγόρια τοποθετούνται με $P(19, 12) = 19 \cdot 18 \cdot \dots \cdot 9 \cdot 8$ τρόπους. Από τον κανόνα του γινομένου, έχουμε $\frac{18! 19!}{7!}$ τρόπους συνολικά. γ) Θα χρησιμοποιήσουμε την αρχή τους αθροίσματος. Οι τρόποι να επιλεγούν r αντικείμενα όταν κανένα εκ των δύο αντικειμένων δεν έχει επιλεγεί είναι $\binom{n - 2}{r}$. Αν επιλεγεί το ένα τότε το άλλο θα πρέπει να είναι εκτός και αυτό μπορεί να γίνει με $\binom{n - 2}{r - 1}$ τρόπους. Το ίδιο ισχύει και για το άλλο αντικείμενο. Επομένως, το σύνολο των τρόπων είναι $\binom{n - 2}{r} + 2 \binom{n - 2}{r - 1}$. δ) Έστω ότι τα περιστέρια είναι οι 7 στήλες της σκακιέρας. Αν δύο στήλες έχουν ακριβώς ίδια χρώματα τότε δημιουργούν ένα ορθογώνιο που έχει την επιθυμητή ιδιότητα. Έστω ότι κάθε στήλη είναι διαφορετική. Έστω όλοι οι 8 τρόποι να χρωματίσουμε μία στήλη: AAA, AAΓ, ΑΓΑ, ΑΓΓ, ΓΑΑ, ΓΑΓ, ΓΓΑ, ΓΓΓ. Σχηματίζουμε 6 περιστερώνες ως εξής: {ΑΑΑ, ΑΑΓ}, {ΑΓΑ}, {ΓΑΑ}, {ΓΓΑ, ΓΓΓ}, {ΓΑΓ} και {ΑΓΓ}. Από την αρχή των περιστερώνων δύο στήλες θα ανήκουν στον ίδιο περιστερώνα και άρα πάντα μπορεί να δημιουργηθεί ένα τέτοιο ορθογώνιο. Για παράδειγμα, αν 2 στήλες είναι ΓΑΑ τότε σχηματίζουμε ένα ορθογώνιο με τα δύο Α ως γωνίες (το ορθογώνιο έχει 2 γραμμές). Ομοίως, αν ο περιστερώνας {ΑΑΑ, ΑΑΓ} περιέχει τα δύο περιστέρια, τότε σχηματίζεται το ορθογώνιο πάλι από τα δύο Α (δύο στήλες). Ομοίως και τα υπόλοιπα.

✔ Επιβεβαίωσε · ✖ Βρήκα λάθος

✖ Βρήκα λάθος στη μεταγραφή