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

Διακριτά Μαθηματικά — Σεπτέμβριος 2023 — Ομάδα Α

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

Discrete_Exams_September_23.pdf (σελ. 1-2)

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

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

Θέματα Μικρής Δυσκολίας (5 μονάδες)1

  1. (1,25) Έστω η σχέση \(R = \{(n, n^2) : n \in \mathbb{Z}\}\) μία σχέση στους ακέραιους αριθμούς. Αποδείξτε αν αυτή η σχέση είναι ή δεν είναι: ανακλαστική, μη-ανακλαστική, συμμετρική και μεταβατική. Είναι σχέση ισοδυναμίας (με αιτιολόγηση);

  2. (1) Να αποδειχθεί ότι αν ο ακέραιος \(n\) είναι τέλειο τετράγωνο, τότε και ο \(n^2\) είναι τέλειο τετράγωνο. Ισχύει το αντίστροφο (με αιτιολόγηση); (ένας ακέραιος \(x\) είναι τέλειο τετράγωνο αν υπάρχει ακέραιος \(k\) έτσι ώστε \(x = k^2\)).

  3. (0,75) Να αποδείξετε ότι ο τύπος \((p \Rightarrow (q \vee r)) \Leftrightarrow ((p \wedge \neg q) \Rightarrow r)\) είναι ταυτολογία.

  4. (1) Να δείξετε ότι για κάθε ακέραιο \(a\) ισχύει ότι ο αριθμός \((a^2 \bmod 4)\) θα είναι \(0\) ή \(1\).

(Υπόδειξη: ελέγξτε τι γίνεται αν ο \(a\) είναι περιττός και τι γίνεται όταν είναι άρτιος. Επίσης, μπορείτε να χρησιμοποιήσετε τη γνωστή ταυτότητα \((a + b) \bmod n = ((a \bmod n) + (b \bmod n)) \bmod n\))

  1. (1) Ο δάσκαλος Ip Man του Kung-Fu έχει μία τάξη 15 ατόμων (μεταξύ των οποίων είναι ο Μπρους και ο Τσάκι). Αποφάσισε να ξεκινήσει μία πειραματική τάξη με 5 άτομα στα οποία θα προσπαθήσει να διδάξει την τεχνική της πασχαλίτσας. Υπολογίστε τους τρόπους επιλογής της ομάδας των 5 μαθητών έτσι ώστε:

i. (0,3) Να συμμετέχει στην ομάδα ο Μπρους (δεν μας ενδιαφέρει τι κάνει ο Τσάκι).

ii. (0,3) Να μη συμμετέχει κανένας από τους δύο.

iii. (0,4) Να συμμετέχει ένας από τους δύο ή και οι δύο.

Θέματα Μεσαίας Δυσκολίας (4,5 μονάδες)

  1. (1) Ένας επιστήμονας που ασχολείται με τη λογική, έχει εφεύρει έναν καινούργιο ποσοτικοποιητή τον οποίο τον συμβολίζει με \(U\). Ο \(U\) σημαίνει «υπάρχει κάτι μοναδικό». Αυτό σημαίνει ότι η πρόταση \(Ux\,P(x)\) είναι αληθής αν υπάρχει ένα μοναδικό \(x\) για το οποίο η \(P(x)\) να είναι αληθής ενώ σε όλες τις άλλες περιπτώσεις θα είναι ψευδής.

Α) (0,5) Γράψτε μία λογική πρόταση ισοδύναμη με την \(Ux\,P(x)\) χρησιμοποιώντας μόνο τον υπαρξιακό ποσοτικοποιητή, το \(=\) και τους λογικούς τελεστές.

Β) (0,5) Γράψτε μία πρόταση ισοδύναμη με την \(Ux\,P(x)\) χρησιμοποιώντας μόνο τον καθολικό ποσοτικοποιητή, το \(=\) και τους λογικούς τελεστές.

  1. (1,2) Να βρείτε τον κλειστό τύπο του αθροίσματος: \(S_n = \sum_{j=1}^{n}\sum_{i=0}^{+\infty} j^{2/3}\left(1 - \frac{1}{2j^{1/3}}\right)^{i}\)

  2. (2,3) Α.(0,6) Έστω όλες οι μεταθέσεις των γραμμάτων ΑΒΓΔΕΖΗ.

  3. (0,3) Πόσες μεταθέσεις υπάρχουν που περιέχουν τις λέξεις ΒΑ και ΗΖΕ (τα γράμματα εμφανίζονται συνεχόμενα);

  4. (0,3) Σε πόσες μεταθέσεις το γράμμα Α προηγείται του γράμματος Β (το Α δεν χρειάζεται να είναι απαραίτητα ακριβώς στην προηγούμενη θέση από το Β);

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

Β. (0,8) Η Ερμιόνη θέλει να στείλει ένα σύνολο από 12 διαφορετικά σύμβολα και 40 κενά διαμέσου ενός καναλιού επικοινωνίας. Τα κενά θα πρέπει να σταλούν με τέτοιο τρόπο ώστε να υπάρχουν τουλάχιστον 3 κενά μεταξύ διαδοχικών συμβόλων, ενώ δεν επιτρέπονται κενά πριν το πρώτο σύμβολο ή μετά το τελευταίο. Με πόσους διαφορετικούς τρόπους μπορεί να στείλει το μήνυμα;

Γ. (0,4) Ο ιδιοκτήτης μίας πιτσαρίας φτιάχνει πίτσες συνδυάζοντας πάντα 4 διαφορετικά συστατικά. Πόσα διαφορετικά συνολικά συστατικά θα πρέπει να έχει τουλάχιστον αν ήθελε να προσφέρει 30 διαφορετικές πίτσες στο μενού;

Δ. (0,5) Ποιο είναι το ελάχιστο πλήθος ανθρώπων σε ένα στάδιο, ο καθένας από τους οποίους έχει γεννηθεί σε μία από τις 100 πόλεις μίας χώρας, για να υπάρχουν τουλάχιστον 50 που έχουν γεννηθεί στην ίδια πόλη;

Θέματα Αυξημένης Δυσκολίας (2 μονάδες)

  1. (1) Να αποδείξετε την εξής πρόταση: Για κάθε ακέραιο \(a\) και έναν πρώτο αριθμό \(p\), αν \(p \mid a+1\) τότε \(p \nmid a\).

  2. (1) Θεωρήστε περιττό \(n\). Χρησιμοποιώντας συνδυαστική απόδειξη (και μόνο) να δείξετε ότι:

\[\binom{n}{0}+\binom{n}{2}+\cdots+\binom{n}{2i}+\cdots+\binom{n}{n-1}=\binom{n}{1}+\binom{n}{3}+\cdots+\binom{n}{2i+1}+\cdots+\binom{n}{n}\]

Με τη μορφή αθροίσματος αυτό γράφεται ως: \(\sum_{i=0}^{\frac{n-1}{2}}\binom{n}{2i}=\sum_{i=0}^{\frac{n-1}{2}}\binom{n}{2i+1}\)

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

Λύσεις (🟢 official)

Κατάσταση: 🟢 official Πηγή: ενδεικτικές λύσεις Ομάδας Α (σελίδες 3–4 του αρχείου «Discrete_Exams_September_23.pdf»)

Λύσεις — Διακριτά Μαθηματικά — Σεπτέμβριος 2023 — Ομάδα Α

Discrete_Exams_September_23.pdf (σελ. 3-4)

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

1.

Η R δεν είναι ανακλαστική αφού το \((3,3) \notin R\).

Η R δεν είναι μη-ανακλαστική αφού το \((1,1) \in R\).

Η R δεν είναι συμμετρική αφού το \((2,4) \in R\) ενώ το \((4,2) \notin R\).

Η R δεν είναι μεταβατική αφού το \((2,4) \in R\) και \((4,16) \in R\) ενώ το \((2,16) \notin R\).

Όχι δεν είναι σχέση ισοδυναμίας αφού δεν είναι ανακλαστική (βεβαίως, δεν είναι ούτε συμμετρική ούτε μεταβατική).

2.

Άμεση απόδειξη. Έστω ότι ο \(n\) είναι τέλειο τετράγωνο. Τότε, σύμφωνα με τον ορισμό θα υπάρχει ακέραιος \(k\) έτσι ώστε \(n = k^2\). Άρα, \(n^2 = (k^2)^2\). Αφού ο \(k^2\) είναι ακέραιος, σημαίνει ότι και ο \(n^2\) είναι τέλειο τετράγωνο.

Το αντίστροφο δεν ισχύει. Πράγματι, αν ο \(n^2\) είναι τέλειο τετράγωνο, που είναι εκ των πραγμάτων, δεν σημαίνει ότι και ο \(n\) είναι τέλειο τετράγωνο. Για παράδειγμα, το 64 είναι τέλειο τετράγωνο, μιας και \(64 = 8^2\). Το 8 όμως δεν είναι τέλειο τετράγωνο. Η απόδειξη είναι με αντιπαράδειγμα.

3.

Μπορεί να γίνει και με πίνακα αληθείας.

\[(p \Rightarrow (q \vee r)) \Leftrightarrow ((p \wedge \neg q) \Rightarrow r) \equiv\]
\[(\neg p \vee q \vee r) \Leftrightarrow (\neg(p \wedge \neg q) \vee r) \equiv\]
\[(\neg p \vee q \vee r) \Leftrightarrow (\neg p \vee q \vee r)\]

Έστω \(\alpha\) μία λογική μεταβλητή:

\[\alpha \Leftrightarrow \alpha \equiv\]
\[(\neg\alpha \vee \alpha) \wedge (\alpha \vee \neg\alpha) \equiv\]
\[T \wedge T \equiv T\]

Άρα η παραπάνω πρόταση είναι ταυτολογία.

4.

Αν ο \(a\) είναι άρτιος, τότε \(a = 2k\) για κάποιον ακέραιο \(k\). Επομένως, \(a^2 \bmod 4 = 4k^2 \bmod 4 = 0\). Αν ο \(a\) είναι περιττός, τότε \(a = 2k+1\) για κάποιον ακέραιο \(k\). Επομένως, \(a^2 \bmod 4 = (4k^2 + 4k + 1) \bmod 4 = 4(k^2+k) \bmod 4 + 1 \bmod 4 = 0 + 1 = 1\). Αποδείχθηκε.

5.

i. Η ομάδα περιλαμβάνει τον Μπρους. Άρα, θα πρέπει να επιλέξουμε 4 άτομα για να συμπληρωθεί η πεντάδα χωρίς να μας ενδιαφέρει η σειρά επιλογής από τους 14 συνολικά που απομένουν. Υπάρχουν \(\binom{14}{4} = 1001\) τρόποι για να γίνει αυτό.

ii. Αρκεί να επιλέξουμε την πεντάδα από τους υπόλοιπους 13. Αυτό μπορεί να γίνει με \(\binom{13}{5} = 1287\) τρόποι.

iii. Έστω Α το πλήθος των ομάδων με τον Μπρους και Β το πλήθος των ομάδων με τον Τσάκι. Αυτό που ψάχνουμε είναι το \(|A \cup B|\). Από εγκλεισμό-αποκλεισμό έχουμε:

\[|A \cup B| = |A| + |B| - |A \cap B|\]

Το \(|A|\) και το \(|B|\) το έχουμε υπολογίσει από το ερώτημα i, αφού ό,τι ισχύει για τον Μπρους το ίδιο θα ισχύει και για τον Τσάκι. Για το \(|A \cap B|\), έχουμε στην ομάδα τόσο τον Μπρους όσο και τον Τσάκι και οι τρόποι να επιλέξουμε τους άλλους τρεις είναι \(\binom{13}{3} = 286\). Άρα το ζητούμενο είναι:

\[|A \cup B| = 1001 + 1001 - 286 = 1716\]

6.

Α)

\[Ux\,P(x) \equiv \exists x \left(P(x) \wedge \neg\left(\exists y(\neg(x = y) \wedge P(y))\right)\right)\]

B) Στην ουσία συμπληρώνουμε το ερώτημα (Α).

\[Ux\,P(x) \equiv \neg\forall x \left(\neg P(x) \vee \neg\forall y((x = y) \vee \neg P(y))\right)\]

7.

Το άθροισμα γράφεται ως:

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

8.

Α. 1. Στην ουσία θα πάρουμε τις μεταθέσεις «τεσσάρων γραμμάτων»: BA, HZE, Γ και Δ. Επομένως έχουμε \(4! = 24\) μεταθέσεις.

  1. Το Α θα προηγείται του Β στις μισές μεταθέσεις από τις συνολικά \(7!\). Άρα, \(\frac{1}{2} 7! = 2520\).

Β. Θα πρέπει μεταξύ των 12 διαφορετικών συμβόλων να υπάρχουν τρία κενά. Αυτό σημαίνει ότι στα 11 διαστήματα που αυτά ορίζουν χρησιμοποιούμε 3 κενά σε καθένα και άρα συνολικά \(3 \cdot 11 = 33\) κενά. Επομένως, 7 κενά μπορούν να τοποθετηθούν με οποιοδήποτε τρόπο σε αυτά τα 11 διαστήματα. Το πλήθος των τρόπων να γίνει αυτό είναι \(\binom{11 + 7 - 1}{7} = \binom{17}{7}\). Επίσης, για κάθε έναν από αυτούς τους τρόπους τοποθέτησης των 7 κενών έχουμε \(12!\) τρόπους να τοποθετήσουμε τα διαφορετικά σύμβολα. Από τον κανόνα του γινομένου έχουμε ότι το τελικό αποτέλεσμα είναι: \(12! \binom{17}{7}\).

Γ. Χρησιμοποιώντας \(x\) διαφορετικά συνολικά συστατικά θα έχουμε \(\binom{x}{4}\) πίτσες συνολικά. Θα πρέπει να βρούμε τον μικρότερο ακέραιο \(x\) ώστε \(\binom{x}{4} \geq 30\). Για \(x=6\), έχουμε 15 διαφορετικές πίστες ενώ για \(x=7\) έχουμε 35 διαφορετικές. Άρα, θα πρέπει να έχει τουλάχιστον 7 διαφορετικά συνολικά συστατικά.

Δ. Χρησιμοποιείται η γενικευμένη αρχή του περιστερώνα. Οι πόλεις είναι οι φωλιές και οι άνθρωποι τα περιστέρια. Αν θέλουμε να έχουμε τουλάχιστον 50 περιστέρια σε μία φωλιά, τότε χρειαζόμαστε να έχουμε \(N\) ανθρώπους έτσι ώστε \(\left\lceil \frac{N}{100} \right\rceil \geq 50\). Αυτό θα ισχύει για \(N = 100 \cdot 49 + 1 = 4901\).

9.

Θα αποδείξουμε το αντιθετοαντίστροφο. Δηλαδή θα δείξουμε ότι αν \(p \mid a\) τότε \(p \nmid (a+1)\). Θα το αποδείξουμε με εις άτοπο. Δηλαδή, υποθέτουμε ότι υπάρχει ακέραιος \(a\) και πρώτος αριθμός \(p\) ώστε \(p \mid a\) και \(p \mid (a+1)\). Τότε, από τον ορισμό της διαιρετότητας, υπάρχουν ακέραιοι \(r\) και \(s\) ώστε \(a = pr\) και \(a+1 = ps\). Συνεπάγεται ότι:

\[1 = (a+1) - a = ps - pr = p(s-r)\]

Αφού \(p(s-r) = 1\) και προφανώς το \(s-r\) είναι ακέραιος σημαίνει ότι ο \(p \mid 1\). Όμως, οι μόνοι ακέραιοι διαιρέτες του 1 είναι το 1 και -1. Αφού ο \(p\) είναι πρώτος ισχύει ότι \(|p| > 1\) ενώ από το παραπάνω θα πρέπει να ισχύει ότι \(p = 1\) ή \(p = -1\). Άτοπο. Άρα ισχύει η αρχική πρόταση.

10.

Έστω ότι έχουμε ένα σύνολο \(n\) ανθρώπων. Το αριστερό μέλος δείχνει με πόσους τρόπους μπορούμε να επιλέξουμε μία ομάδα ανθρώπων χωρίς να μας ενδιαφέρει η σειρά έτσι ώστε αυτή η ομάδα να έχει άρτιο πλήθος ατόμων. Το δεξιό μέλος μετράει το ίδιο αλλά με άλλο τρόπο. Οι τρόποι να επιλέξουμε 0 άτομα από \(n\) συνολικά είναι ίσοι με τους τρόπους να μην επιλέξουμε \(n\) άτομα από \(n\) συνολικά. Με τον ίδιο τρόπο, οι τρόποι να επιλέξουμε \(2i\) άτομα από μία ομάδα \(n\) ανθρώπων είναι ίσοι με τους τρόπους να μην επιλέξουμε \(n-2i\) ανθρώπους από \(n\) συνολικά (το \(2i\) είναι άρτιος ενώ το \(n-2i\) είναι περιττός). Αφού οι όροι \(\binom{n}{2i}\) στο αριστερό μέλος και \(\binom{n}{n-2i}\) στο δεξιό μέλος είναι ίσοι και κάθε όρος αριστερά αντιστοιχεί σε όρο δεξιά, οι δύο ποσότητες είναι ίσες.

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

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