Μετάβαση στο περιεχόμενο

Διακριτά Μαθηματικά — Αύγουστος 2022 — Ομάδα Α

Μεταγραφή από τις σελίδες 1–2 του αρχείου Discrete_Exams_29-08-22.pdf.

Discrete_Exams_29-08-22.pdf (σελ. 1-2)

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

1. (22%) Ο Κωστάκης συμμετέχει σε ένα επιτραπέζιο παιχνίδι ρόλων (Role Playing Game) τύπου Dungeons & Dragons (D&D) και είναι σε ένα κρίσιμο σημείο που για να ξεφύγει από τον Νοούβορο θα πρέπει να ρίξει 4 δωδεκάεδρα ζάρια διαφορετικού χρώματος και το άθροισμά τους να είναι ακριβώς 24. Το δωδεκάεδρο ζάρι έχει όλους τους αριθμούς από το 1 έως το 12. Για να υπολογίσει τη μάλλον μικρή πιθανότητα να κερδίσει πρέπει πρώτα να υπολογίσει με πόσους τρόπους μπορεί να φέρει άθροισμα 24 ρίχνοντας τα 4 διαφορετικά δωδεκάεδρα ζάρια.

α) (17) Μπορείτε να βοηθήσετε τον Κωστάκη με αυτό το πρόβλημα μέτρησης χρησιμοποιώντας γεννήτριες συναρτήσεις;

β) (5) Για να υπολογίσει την πιθανότητα ο Κωστάκης πρέπει επίσης να υπολογίσει πόσοι διαφορετικοί τρόποι υπάρχουν να ρίξουμε 4 διαφορετικού χρώματος δωδεκάεδρα ζάρια. Μπορείτε να τον βοηθήσετε;

Υπόδειξη: Η γεννήτρια συνάρτηση \(\frac{1}{(1-x)^n}\) αντιστοιχεί στην ακολουθία \(C(n+k-1, k) = \binom{n+k-1}{k}\). Δεν χρειάζεται να βρείτε το τελικό αριθμητικό αποτέλεσμα. Ο ακριβής τύπος χωρίς μεταβλητές και παραμέτρους είναι αρκετός.

2. (15%) Για σημεία \((x, y)\) και \((u, v)\) στο επίπεδο, η σχέση \(R\) έτσι ώστε \((x, y) \, R \, (u, v)\) σημαίνει ότι \(x^2 + y^2 = u^2 + v^2\). Αποδείξτε ότι η σχέση \(R\) είναι μία σχέση ισοδυναμίας. Να συζητήσετε πως αυτή η σχέση ισοδυναμίας διαμερίζει τα σημεία του \((x, y)\)-επιπέδου.

3. (10%) Οι 200 πρωτοετείς φοιτητές του τμήματος Επιστήμης Διακοπών δηλώνουν μαθήματα στην γραμματεία. Κάθε φοιτητής θα πρέπει να δηλώσει τουλάχιστον ένα μάθημα. Τα στοιχεία της γραμματείας δείχνουν ότι 80 φοιτητές δήλωσαν το μάθημα της Εργονομίας Ξαπλώστρας (ΕΞ), 90 φοιτητές το μάθημα Είδη Καφέ (ΕΚ), 55 φοιτητές το μάθημα Επικίνδυνη Οδήγηση (ΕΟ), 32 φοιτητές τα μαθήματα ΕΞ και ΕΚ, 23 φοιτητές τα μαθήματα ΕΚ και ΕΟ, 16 φοιτητές τα μαθήματα ΕΞ και ΕΟ και τέλος 8 φοιτητές και τα τρία μαθήματα. Έκαναν όλοι οι φοιτητές δήλωση και αν όχι πόσοι ήταν αυτοί που δεν έκαναν;

4. (16%)

α) (8) Έστω η πρόταση \(\exists x \forall y P(x, y)\). Σε ποιες από τις παρακάτω περιπτώσεις αυτή ικανοποιείται και γιατί;

  1. Το σύνολο των φυσικών \(\mathbb{N}\) με το \(P(x, y)\) να σημαίνει τη συνήθη διάταξη \(x \leq y\).
  2. Το σύνολο των φυσικών \(\mathbb{N}\) με το \(P(x, y)\) να σημαίνει «το \(y\) διαιρείται από το \(x\)».
  3. Το σύνολο των πραγματικών \(\mathbb{R}\) με το \(P(x, y)\) να σημαίνει τη συνήθη διάταξη \(x \leq y\).
  4. Το σύνολο των ακεραίων \(\mathbb{Z}\) με το \(P(x, y)\) να σημαίνει ότι «το \(x\) είναι τετράγωνο του \(y\)».

β) (8) Ο τύπος \(\neg p_1 \rightarrow (p_1 \rightarrow p_2)\) είναι:

  • [ ] Ταυτολογία
  • [ ] Ισοδύναμος με τον \(p_2\)
  • [ ] Ισοδύναμος με τον \((\neg p_1 \wedge p_1) \rightarrow p_2\)
  • [ ] Ισοδύναμος με τον \(p_1 \rightarrow (p_2 \rightarrow p_1)\)

5. (10%) Να υπολογίσετε το άθροισμα:

\[\sum_{i=1}^{n} \sum_{j=0}^{\infty} \left(\frac{i}{i+1}\right)^j\]

6. (37%)

α. (9) Έστω ότι επιλέγουμε αυθαίρετα 6 ακέραιους στο διάστημα μεταξύ του 1 και του 2022 (συμπεριλαμβανομένου του 1 και του 2022). Να δείξετε αν υπάρχει ζεύγος αριθμών από αυτούς τους έξι επιλεγμένους αριθμούς έτσι ώστε η διαφορά τους να διαιρείται από το 5.

β. (10) Να αποδείξετε συνδυαστικά την εξής ισότητα: \(k\binom{n}{k} = n\binom{n-1}{k-1}\)

γ. (18) Έστω ότι θέλουμε να βρούμε πόσους κωδικούς προϊόντων μήκους 8 μπορούμε να φτιάξουμε από το ελληνικό αλφάβητο (24 γράμματα) και τα 10 ψηφία (0, 1, …, 9). Σας ζητείται (με συνοπτική αιτιολόγηση) να υπολογίσετε το πλήθος των κωδικών όταν (δεν χρειάζεται να κάνετε τις πράξεις για το ακριβές αριθμητικό αποτέλεσμα):

  1. (1) Δεν υπάρχει κανένας περιορισμός στην τοποθέτηση των γραμμάτων/αριθμών.
  2. (1) Η πρώτη θέση πάντα να ξεκινά από αριθμό.
  3. (2) Η πρώτη θέση να είναι περιττός αριθμός ενώ η όγδοη να έχει μόνο αριθμούς.
  4. (3) Να υπάρχει τουλάχιστον ένας αριθμός στον κωδικό (δεν υπάρχει περιορισμός που να αφορά τη θέση του).
  5. (4) Κάθε γράμμα/αριθμός να εμφανίζεται το πολύ μία φορά και όλοι οι κωδικοί που προκύπτει ο ένας από τον άλλο μέσω κυκλικής μετατόπισης να είναι ίδιοι (π.χ., ο κωδικός 3ρ56τγη9 είναι ισοδύναμος με τους ρ56τγη93, 56τγη93ρ, …, 93ρ56τγη).
  6. (4) Κάθε γράμμα/αριθμός να εμφανίζεται το πολύ μία φορά εκτός από το 1 που θα εμφανίζεται ακριβώς 4 φορές.
  7. (3) Δεν μας ενδιαφέρει η σειρά με την οποία εμφανίζονται τα γράμματα/αριθμοί στον κωδικό (δηλαδή ο κωδικός aaaa123ad είναι ίδιος με τον κωδικό daaaa123).

7. (10%) Έστω οι ακέραιοι \(x, y, z\). Θέλουμε να αποδείξουμε την εξής πρόταση: αν \(x \nmid y \cdot z\) τότε, \(x \nmid z\) και \(x \nmid y\). (\(\nmid\) σημαίνει «δεν διαιρεί»). Σας ζητούνται τα εξής:

  1. Ορίστε προτασιακές μεταβλητές που να αντιστοιχούν στις τρεις συνθήκες της πρότασης.
  2. Να εκφράσετε την πρόταση που θέλουμε να αποδείξουμε ως λογική πρόταση με χρήση αυτών των μεταβλητών.
  3. Να εκφράσετε το αντιθετοαντίστροφο της πρότασης (από ερωτ. 2) τόσο ως λογική πρόταση (χρησιμοποιώντας δηλαδή τα προτασιακά σύμβολα) όσο και σε φυσική γλώσσα.
  4. Αποδείξτε την αλήθεια της πρότασης με έμμεση απόδειξη (αντιθετοαντίστροφο).

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

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

Λύσεις (🟢 official)

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

Προσοχή

Το κλειδί (σελ. 9–12) καλύπτει όλες τις ομάδες· σημειώνει ότι τα Α και Δ είναι ίδια (με διαφορετική σειρά), όπως και τα Β και Γ, εκτός αν αναφέρεται ρητά διαφορετικά.

Λύσεις — Διακριτά Μαθηματικά — Αύγουστος 2022 — Ομάδα Α

Discrete_Exams_29-08-22.pdf (σελ. 9-12)

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

Τα Α και Δ είναι ίδια αλλά με διαφορετική σειρά καθώς και τα Β και Γ (εκτός και αν αναφέρεται ρητά ότι η άσκηση είναι διαφορετική).

1Α, 2Β, 5Γ, 6Δ.

α) Κάθε ζάρι ρίχνει οποιονδήποτε αριθμό μεταξύ 1 και 12. Αφού ρίχνουμε 4 φορές η γεννήτρια συνάρτηση θα είναι:

\[(x + x^2 + x^3 + \cdots + x^{12})^4\]

Θέλουμε να βρούμε τον συντελεστή του \(x^{24}\) σε αυτό το γινόμενο. Η παραπάνω γεννήτρια συνάρτηση γίνεται ως εξής:

\[x^4(1 + x + x^2 + \cdots + x^{11})^4\]

Ο συντελεστής που ψάχνουμε είναι αυτός του \(x^{20}\) στο γινόμενο \((1 + x + x^2 + \cdots + x^{11})^4 = \left(\frac{1 - x^{12}}{1 - x}\right)^4\).

Αυτό γράφεται ως εξής χρησιμοποιώντας το δυωνυμικό ανάπτυγμα στον αριθμητή:

\[\frac{1 - 4x^{12} + 6x^{24} - 3x^{36} + x^{48}}{(1-x)^4} = \frac{1}{(1-x)^4} - \frac{4x^{12}}{(1-x)^4} + \frac{6x^{24}}{(1-x)^4} - \frac{3x^{36}}{(1-x)^4} + \frac{x^{48}}{(1-x)^4}\]

Προσέξτε ότι για το συντελεστή που ψάχνουμε μας ενδιαφέρει η συνεισφορά μόνο από τα δύο πρώτα κλάσματα μιας και τα υπόλοιπα δίνουν συντελεστή μεγαλύτερο του 20. Άρα, ψάχνουμε να βρούμε τον συντελεστή από το

\[\frac{1}{(1-x)^4} - \frac{4x^{12}}{(1-x)^4}\]

Με δεδομένη τη γεννήτρια συνάρτηση που μας δίνεται από την υπόδειξη της εκφώνησης έχουμε ότι η παραπάνω γεννήτρια συνάρτηση αντιστοιχεί στην ακολουθία:

\[\binom{k+3}{k} - 4\binom{k-9}{k-12}\]

Θέτουμε \(k = 20\) για να βρούμε το συντελεστή που μας ενδιαφέρει και έχουμε:

\[\binom{23}{20} - 4\binom{11}{8} = 1771 - 660 = 1111\]

Για Β: θέτουμε \(k = 19\) και έχουμε:

\[\binom{22}{19} - 4\binom{10}{7} = 1540 - 480 = 1060\]

Για Γ: θέτουμε \(k = 18\) και έχουμε:

\[\binom{21}{18} - 4\binom{9}{6} = 1330 - 336 = 994\]

Για Δ: θέτουμε \(k = 17\) και έχουμε:

\[\binom{20}{17} - 4\binom{8}{5} = 1140 - 224 = 916\]

β) Είναι ένα 4-δείγμα από ένα σύνολο μεγέθους 12 (επανατοποθέτηση και μας ενδιαφέρει η σειρά αφού αντιστοιχεί στα διαφορετικά χρώματα). Άρα οι τρόποι είναι \(12^4 = 20736\).

2Α, 3Β, 3Γ, 4Δ.

Θα πρέπει να έχει 3 ιδιότητες:

Ανακλαστική: \((x, y)\, R\, (x, y)\) ισχύει αφού \(x^2 + y^2 = x^2 + y^2\).

Συμμετρική: \((x, y)\, R\, (u, v)\) σημαίνει ότι και \((u, v)\, R\, (x, y)\) από τον αντίστοιχο τύπο.

Μεταβατική: \((x, y)\, R\, (u, v)\) και \((u, v)\, R\, (w, z)\) το οποίο σημαίνει: \(x^2 + y^2 = u^2 + v^2\) και \(w^2 + z^2 = u^2 + v^2\), από το οποίο προκύπτει ότι \((x, y)\, R\, (w, z)\).

Οι διαμερίσεις που προκύπτουν αφορούν όλα τα σημεία τα οποία βρίσκονται σε ίση απόσταση από την αρχή των αξόνων. Αυτό σημαίνει ότι μία κλάση ισοδυναμίας είναι στην ουσία ένας κύκλος.

Για το Β έχει αλλάξει μόνο το όνομα των μεταβλητών.

3Α, 1Β, 7Γ, 5Δ.

\(N(\text{ΕΞ}) = 80\), \(N(\text{ΕΚ}) = 90\), \(N(\text{ΕΟ}) = 55\), \(N(\text{ΕΞ} \cap \text{ΕΚ}) = 32\), \(N(\text{ΕΚ} \cap \text{ΕΟ}) = 23\), \(N(\text{ΕΞ} \cap \text{ΕΟ}) = 16\) και \(N(\text{ΕΞ} \cap \text{ΕΚ} \cap \text{ΕΟ}) = 8\).

\[N(\text{ΕΞ} \cup \text{ΕΚ} \cup \text{ΕΟ}) = 80 + 90 + 55 - 32 - 23 - 16 + 8 = 162\]

Άρα 38 φοιτητές δεν έχουν κάνει δήλωση.

Για το (Β) αντίστοιχα είναι 58.

Για το (Γ) αντίστοιχα είναι 68.

Για το (Δ) αντίστοιχα είναι 78.

4Α, 6Β, 6Γ, 7Δ.

α)

Α:

  1. Σωστό: Πράγματι υπάρχει ένας αριθμός που είναι μικρότερος ή ίσος από όλους τους φυσικούς αριθμούς και αυτός είναι το 1.

  2. Σωστό: Πράγματι, υπάρχει ένας αριθμός που διαιρεί όλους τους φυσικούς αριθμούς και αυτός είναι το 1.

  3. Λάθος: Ο τύπος εδώ αναφέρει ότι υπάρχει ελάχιστος στο σύνολο των πραγματικών αριθμών – κάτι που δεν ισχύει.

  4. Λάθος: Δεν υπάρχει κάποιος ακέραιος που να είναι το τετράγωνο όλων των ακεραίων αριθμών.

Β:

  1. Λάθος: Δεν υπάρχει αριθμός που να είναι μεγαλύτερος ή ίσος από όλους τους φυσικούς.

  2. Σωστό: Πράγματι, υπάρχει ένας αριθμός που διαιρεί όλους τους φυσικούς αριθμούς και αυτός είναι το 1.

  3. Λάθος: Ο τύπος εδώ αναφέρει ότι υπάρχει ελάχιστος στο σύνολο των πραγματικών αριθμών – κάτι που δεν ισχύει.

  4. Λάθος: Δεν υπάρχει κάποιος ακέραιος που να είναι τετραγωνική ρίζα όλων των ακεραίων.

β)

  1. Σωστό: Από κανόνα εξαγωγής έχουμε: \(\neg p_1 \rightarrow (p_1 \rightarrow p_2) \equiv (\neg p_1 \wedge p_1) \rightarrow p_2 \equiv \Psi \rightarrow p_2 \equiv \Lambda\) (για το Β είναι λάθος).

  2. Λάθος: Ο \(p_2\) (Β: \(p_1\)) δεν είναι ταυτολογία και άρα δεν μπορεί να είναι ισοδύναμος με τον τύπο \(\neg p_1 \rightarrow (p_1 \rightarrow p_2)\) που είναι ταυτολογία από το (1).

  3. Σωστό: Ενδιάμεσο βήμα από το (1).

  4. Σωστό: Πράγματι από αναδιάταξη έχουμε: \(p_1 \rightarrow (p_2 \rightarrow p_1) \equiv p_2 \rightarrow (p_1 \rightarrow p_1)\). Όμως \(p_1 \rightarrow p_1\) είναι πάντα Αληθές. Άρα: \(p_1 \rightarrow (p_2 \rightarrow p_1) \equiv p_2 \rightarrow \Lambda \equiv \Lambda\). Άρα και αυτός ο τύπος είναι ταυτολογία και άρα είναι ισοδύναμοι.

5Α, 4Β, 4Γ, 2Δ.

\[\sum_{i=1}^{n} \sum_{j=0}^{\infty} \left(\frac{i}{i+1}\right)^j = \sum_{i=1}^{n} \frac{1}{1 - \frac{i}{i+1}} = \sum_{i=1}^{n} \frac{i+1}{1} = \sum_{i=1}^{n} i + \sum_{i=1}^{n} 1 = \frac{n(n+1)}{2} + n\]

Για το Β είναι ανάποδα τα \(i\) και \(j\).

6Α, 7Β, 1Γ, 3Δ.

α. Για να είναι η διαφορά τους διαιρέσιμη από το 5 (Β: 6), θα πρέπει οι δύο ακέραιοι να έχουν το ίδιο υπόλοιπο όταν διαιρούνται με το 5 (Β: 6). Αφού υπάρχουν 5 (Β: 6) διαφορετικά υπόλοιπα (οι περιστερώνες) και 6 (Β: 7) αριθμοί θα πρέπει αναγκαστικά από την αρχή του περιστερώνα δύο αριθμοί να έχουν το ίδιο υπόλοιπο. Άρα πάντα θα υπάρχει τέτοιο ζεύγος.

β. Το αριστερό μέρος μετρά το πλήθος των διατεταγμένων ζευγών της μορφής \((x, S)\), όπου \(S\) είναι ένα \(k\)-υποσύνολο του συνόλου \(\{1, 2, \ldots, n\}\) και \(x \in S\). Υπάρχουν \(\binom{n}{k}\) τρόποι επιλογής του \(S\) και \(k\) τρόποι επιλογής του \(x\). Το δεξιό μέρος μετρά το ίδιο αλλά με άλλο τρόπο. Πρώτα επιλέγουμε το \(x\) από τα \(n\) στοιχεία με \(n\) τρόπους και έπειτα επιλέγουμε τα υπόλοιπα \(k-1\) στοιχεία του \(S\) από τα εναπομείναντα \(n-1\) με \(\binom{n-1}{k-1}\) τρόπους. (Ίδιο για B με αλλαγμένες μεταβλητές.)

γ.

  1. (Β: 2). Είναι ένα 8-δείγμα από το σύνολο των αριθμών και των γραμμάτων και άρα η απάντηση είναι \(34^8\).

  2. (Β: 1). Η πρώτη θέση είναι 1-δείγμα από ένα σύνολο 10 αριθμών ενώ οι επόμενες 7 αποτελούν 7-δείγμα από σύνολο 34 αριθμών και γραμμάτων. Από τη θεμελιώδη αρχή απαρίθμησης η απάντηση είναι \(10 \times 34^7\).

  3. (Β: 4). Ακολουθώντας αντίστοιχο σκεπτικό με τη (2) η απάντηση είναι: \(5 \times 34^6 \times 10\).

  4. (Β: 3). Όλες οι δυνατές ακολουθίες από το (1) μπορεί να είναι \(34^8\). Από όλες αυτές εμείς θέλουμε να βρούμε μόνο αυτές που έχουν έναν τουλάχιστον αριθμό. Αυτό είναι ισοδύναμο με το να βρούμε όλες τις ακολουθίες που δεν έχουν αριθμό (που είναι \(24^8\)) και να το αφαιρέσουμε από το συνολικό πλήθος των ακολουθιών. Άρα η απάντηση είναι \(34^8 - 24^8\) (εφαρμόσαμε στην ουσία την αρχή του αθροίσματος).

  5. (Β: 7). Καταρχάς, αφού μας ενδιαφέρει η σειρά αλλά δεν έχουμε επανατοποθέτηση θέλουμε να βρούμε μία 8-μετάθεση από ένα σύνολο μεγέθους 34, το οποίο είναι \(P(34, 8) = \frac{34!}{26!}\). Όμως, κάθε απάντηση είναι ισοδύναμη με άλλες 7 συνολικά λόγω της κυκλικής μετατόπισης και άρα από τον κανόνα της διαίρεσης η απάντηση είναι \(\frac{34!}{26!\, 8}\).

  6. (Β: 6). Επιλέγουμε τις θέσεις του 1 με \(\binom{8}{4}\) τρόπους μιας και δεν διαφοροποιούνται τα 1 μεταξύ τους. Επίσης, για τις άλλες 4 θέσεις έχουμε μία 4-μετάθεση από ένα σύνολο μεγέθους 33 (το 1 δεν το μετράμε πια), το οποίο συμβαίνει με \(P(33, 4) = \frac{33!}{29!}\). Από τον κανόνα γινομένου η απάντηση είναι \(\binom{8}{4} \cdot \frac{33!}{29!}\).

  7. (Β: 5). Αυτό είναι μία 8-επιλογή από ένα σύνολο μεγέθους 34. Άρα η απάντηση είναι \(\binom{34 + 8 - 1}{8} = \binom{41}{8}\).

7Α, 5Β, 2Γ, 1Δ.

1. Έστω τα εξής σύμβολα:

\(p\): \(x \nmid y \cdot z\)

\(q\): \(x \nmid z\)

\(r\): \(x \nmid y\)

2. \(p \rightarrow q \wedge r\)

3. Αντιθετοαντίστροφο: \(\neg q \vee \neg r \rightarrow \neg p\)

Αν \(x \mid z\) ή \(x \mid y\) τότε \(x \mid y \cdot z\).

4. Έμμεση απόδειξη:

Θα δείξουμε ότι αν \(x \mid z\) ή \(x \mid y\) τότε \(x \mid y \cdot z\). Πράγματι, έστω ότι \(x \mid z\). Τότε, το \(x\) διαιρεί και κάθε ακέραιο πολλαπλάσιο του \(z\). Επομένως θα διαιρεί και το \(y \cdot z\). Αντίστοιχα και για τη περίπτωση όπου \(x \mid y\).

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

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