Διακριτά Μαθηματικά — Φεβρουάριος 2022 — Ομάδα Α

Μεταγραφή από τη σελίδα 1 του αρχείου Solutions_Discrete_Exams_2021-2022_08-02-22.pdf.

Θέμα 08-02-22, σελ. 1 (ομάδα A)

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

1. (20%) Έστω ότι έχουμε ένα μεγάλο πλήθος άσπρων, κόκκινων και μπλε μπαλονιών. Με πόσους τρόπους μπορούμε να επιλέξουμε \(n\) μπαλόνια (δεν μας ενδιαφέρει η σειρά) έτσι ώστε να ισχύουν ταυτόχρονα οι εξής περιορισμοί: α) να υπάρχει τουλάχιστον ένα κόκκινο μπαλόνι, β) να υπάρχει τουλάχιστον ένα άσπρο μπαλόνι και το πλήθος τους να είναι άρτιο και γ) να υπάρχει το πολύ ένα μπλε μπαλόνι.

Υπόδειξη: Η γεννήτρια συνάρτηση \(\frac{1}{(1-x)^n}\) αντιστοιχεί σε μία ακολουθία της οποίας ο \(k\)-οστός όρος είναι ο \(\binom{n+k-1}{k}\)

2. (20%) Θεωρούμε το σύνολο \(S\) των \(10^n\) διαφορετικών λέξεων μήκους \(n\) που σχηματίζονται από τα δέκα γράμματα A, B, C, D, E, F, G, H, I και J. Έστω η διμελής σχέση \(\Sigma\) που ορίζεται ως εξής:

\[(\alpha, \beta) \in \Sigma \text{ αν η λέξη } \alpha \text{ μπορεί να προκύψει με επαναδιάταξη των γραμμάτων της λέξης } \beta\]

α.(10%) Εξετάστε ποιες από τις ιδιότητες των σχέσεων (ανακλαστική, συμμετρική, μεταβατική) πληροί η σχέση. Είναι σχέση ισοδυναμίας;

β.(10%) Αν η \(\Sigma\) είναι σχέση ισοδυναμίας τότε αυτή δημιουργεί μία διαμέριση στο σύνολο \(S\). Έστω ότι αυτή η διαμέριση αποτελείται από τα υποσύνολα \(X_1, X_2, \ldots, X_k\). Να υπολογίσετε το \(k\), δηλαδή το πλήθος των υποσυνόλων της διαμέρισης λόγω της σχέσης \(\Sigma\).

3. (10%) Να δείξετε αν ο λογικός τύπος \((p \wedge q \wedge r) \rightarrow (p \vee q)\) είναι ταυτολογία, αντίφαση ή τίποτα από τα δύο.

4. (20%) Έστω \(S_n = \{1, 2, \ldots, n\}\) το σύνολο των φυσικών από το 1 έως το \(n\) και \(P(S_n)\) το δυναμοσύνολο του \(S_n\). Έστω \(Q\) κατηγόρημα με τομέα αναφοράς το \(P(S_n)\) που ερμηνεύεται ως εξής: \(Q(x, y) =\) "\(x \subseteq y\)". Για κάθε μία από τις παρακάτω λογικές προτάσεις σας ζητείται να αναφέρετε με συνοπτική αιτιολόγηση αν είναι Αληθείς ή Ψευδείς.

1. \(\exists y \forall x Q(x, y)\)
2. \(\forall x \exists y (x \neq y \wedge Q(y, x))\)
3. \(\forall x \forall y (Q(x, y) \rightarrow (x \cap y \neq \emptyset))\) (το \(\emptyset\) είναι το κενό σύνολο)
4. \(\forall x \forall y \big(Q(x, y) \rightarrow \big(Q(x \cap y, y)\big)\big)\)

5. (10%) Υπολογίστε το εξής άθροισμα: \(\sum_{n=1}^{\ell-1} \sum_{m=1}^{\ell} nm\)

6. (30%) α. (10%) Χρησιμοποιώντας συνδυαστική απόδειξη να δείξετε ότι: \(\sum_{i=2}^{n} i(i-1)\binom{n}{i} = n(n-1)2^{n-2}\)

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

• i. Αν επιλέγουμε τυχαία θετικούς ακεραίους, ποιο είναι το ελάχιστο πλήθος τέτοιων ακεραίων που πρέπει να επιλέξουμε ώστε να εγγυηθούμε ότι για δύο από αυτούς τους αριθμούς \(a\) και \(b\) θα ισχύει \(a \equiv b \pmod{6}\);
• ii. Ποιο είναι το πλήθος των σχέσεων από το σύνολο \(X\) στο σύνολο \(Y\), όπου \(k = |X|\) και \(\ell = |Y|\);
• iii. Μία δημοσκόπηση στην Ελλάδα έδωσε τα εξής αποτελέσματα όσον αφορά την ερώτηση για το αν ο Γιωρίκας (Γ), ο Πανίκας (Π) ή ο Μπαμπίκας (Μ) είναι κατάλληλοι για πρωθυπουργοί. Ο Γ είναι κατάλληλος με ποσοστό 65%, ο Π με ποσοστό 57%, ο Μ με ποσοστό 58%, ενώ 28% θεώρησαν κατάλληλους τους Γ και Π, 30% τους Γ και Μ, 27% τους Π και Μ και τέλος 12% και τους τρεις. Ποιο είναι το ποσοστό των ψηφοφόρων που δεν γουστάρουν κανένα για πρωθυπουργό; Τι συμπέρασμα βγάζετε από το αποτέλεσμα που πήρατε;
• iv. Πόσοι τρόποι υπάρχουν να επιλέξουμε 12 αναψυκτικά από τρεις τύπους αναψυκτικών: σόδα, πορτοκαλάδα και λεμονάδα, όπου τουλάχιστον 3 θα πρέπει να είναι λεμονάδες;

7. (10%) Θέλουμε να αποδείξουμε την πρόταση: «Αν ο \(a\) δεν είναι περιττός, τότε \(a \leq 2\) ή ο \(a\) είναι σύνθετος αριθμός». Να κάνετε τα εξής:

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

8. (10%) Να αποδείξετε ότι ο \(\text{ΜΚΔ}(\alpha, \alpha + n)\), όπου \(n \neq 0\), διαιρεί τέλεια τον \(n\) (δηλαδή να δείξετε ότι για \(n \neq 0\) ισχύει ότι \(\text{ΜΚΔ}(\alpha, \alpha + n) \mid n\)) (ΜΚΔ: Μέγιστος Κοινός Διαιρέτης)

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

Λύσεις (🟢 official)

Κατάσταση: 🟢 official Πηγή: ενδεικτικές λύσεις (σελίδες 5–10 του αρχείου «Solutions_Discrete_Exams_2021-2022_08-02-22.pdf»)

Προσοχή

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

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

Solutions_Discrete_Exams_2021-2022_08-02-22.pdf (σελ. 5-10)

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

1(Α), 7(Β), 6(Γ), 3(Δ):

Α) Θα χρησιμοποιήσουμε γεννήτριες συναρτήσεις. Θα κωδικοποιήσουμε τους περιορισμούς ως εξής:

Κόκκινα μπαλόνια: \((x + x^2 + \cdots) = x(1 + x + x^2 + \cdots) = x\frac{1}{1-x}\) (η τελευταία ισότητα από πίνακες)

Άσπρα μπαλόνια: \((x^2 + x^4 + \cdots) = x^2(1 + x^2 + x^4 + \cdots) = x^2\frac{1}{1-x^2}\)

Μπλε μπαλόνια: \((1 + x)\)

Άρα η γεννήτρια συνάρτηση που περιγράφει το πρόβλημα είναι η εξής:

\[G(x) = x\frac{1}{1-x}\,x^2\frac{1}{1-x^2}(1+x) \Rightarrow G(x) = x^3(1+x)\frac{1}{1-x}\frac{1}{(1-x)(1+x)} \Rightarrow G(x) = \frac{x^3}{(1-x)^2}\]

Η ακολουθία που αντιστοιχεί στην γεννήτρια συνάρτηση \(\frac{1}{(1-x)^2}\) για τον \(n\)-οστό όρο είναι η εξής: \(\binom{2+n-1}{n} = \binom{n+1}{n}\).

Επειδή πολλαπλασιάζεται η συνάρτηση αυτή από το \(x^3\), χρησιμοποιώντας την ιδιότητα της ολίσθησης έχουμε ότι οι τρόποι με τους οποίους μπορούμε να επιλέξουμε \(n\) μπαλόνια είναι:

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

B) Κόκκινα μπαλόνια: \((x + x^2 + \cdots) = x(1 + x + x^2 + \cdots) = x\frac{1}{1-x}\) (η τελευταία ισότητα από πίνακες)

Άσπρα μπαλόνια: \((x + x^3 + x^5 + \cdots) = x(1 + x^2 + x^4 + \cdots) = x\frac{1}{1-x^2}\)

Μπλε μπαλόνια: \((1 + x)\)

Άρα η γεννήτρια συνάρτηση που περιγράφει το πρόβλημα είναι η εξής:

\[G(x) = x\frac{1}{1-x}\,x\frac{1}{1-x^2}(1+x) \Rightarrow G(x) = x^2(1+x)\frac{1}{1-x}\frac{1}{(1-x)(1+x)} \Rightarrow G(x) = \frac{x^2}{(1-x)^2}\]

Η ακολουθία που αντιστοιχεί στην γεννήτρια συνάρτηση \(\frac{1}{(1-x)^2}\) για τον \(n\)-οστό όρο είναι η εξής: \(\binom{2+n-1}{n} = \binom{n+1}{n}\).

Επειδή πολλαπλασιάζεται η συνάρτηση αυτή από το \(x^2\), χρησιμοποιώντας την ιδιότητα της ολίσθησης έχουμε ότι οι τρόποι με τους οποίους μπορούμε να επιλέξουμε \(n\) μπαλόνια είναι:

\[\binom{n-2+1}{n-2} = \binom{n-1}{n-2} = n-1\]

Γ) Πράσινα κεριά: \((1 + x + x^2 + \cdots) = \frac{1}{1-x}\) (η τελευταία ισότητα από πίνακες)

Μπλε κεριά: \((x^2 + x^4 + x^6 + \cdots) = x^2(1 + x^2 + x^4 + \cdots) = x^2\frac{1}{1-x^2}\)

Χρυσό κερί: \((1 + x)\)

Άρα η γεννήτρια συνάρτηση που περιγράφει το πρόβλημα είναι η εξής:

\[G(x) = \frac{1}{1-x}\,x^2\frac{1}{1-x^2}(1+x) \Rightarrow G(x) = x^2(1+x)\frac{1}{1-x}\frac{1}{(1-x)(1+x)} \Rightarrow G(x) = \frac{x^2}{(1-x)^2}\]

Η ακολουθία που αντιστοιχεί στην γεννήτρια συνάρτηση \(\frac{1}{(1-x)^2}\) για τον \(n\)-οστό όρο είναι η εξής: \(\binom{2+n-1}{n} = \binom{n+1}{n}\).

Επειδή πολλαπλασιάζεται η συνάρτηση αυτή από το \(x^2\), χρησιμοποιώντας την ιδιότητα της ολίσθησης έχουμε ότι οι τρόποι με τους οποίους μπορούμε να επιλέξουμε \(n\) κεριά είναι:

\[\binom{n-2+1}{n-2} = \binom{n-1}{n-2} = n-1\]

Δ) Πράσινα κεριά: \((1 + x + x^2 + \cdots) = \frac{1}{1-x}\) (η τελευταία ισότητα από πίνακες)

Μπλε κεριά: \((x^3 + x^5 + x^7 + \cdots) = x^3(1 + x^2 + x^4 + \cdots) = x^3\frac{1}{1-x^2}\)

Χρυσό κερί: \((1 + x)\)

Άρα η γεννήτρια συνάρτηση που περιγράφει το πρόβλημα είναι η εξής:

\[G(x) = \frac{1}{1-x}\,x^3\frac{1}{1-x^2}(1+x) \Rightarrow G(x) = x^3(1+x)\frac{1}{1-x}\frac{1}{(1-x)(1+x)} \Rightarrow G(x) = \frac{x^3}{(1-x)^2}\]

Η ακολουθία που αντιστοιχεί στην γεννήτρια συνάρτηση \(\frac{1}{(1-x)^2}\) για τον \(n\)-οστό όρο είναι η εξής: \(\binom{2+n-1}{n} = \binom{n+1}{n}\).

Επειδή πολλαπλασιάζεται η συνάρτηση αυτή από το \(x^3\), χρησιμοποιώντας την ιδιότητα της ολίσθησης έχουμε ότι οι τρόποι με τους οποίους μπορούμε να επιλέξουμε \(n\) κεριά είναι:

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

2(Α), 1(Β), 4(Γ), 7(Δ):

α. Η σχέση είναι ανακλαστική αφού για οποιοδήποτε \(\alpha \in S\) ισχύει \((\alpha, \alpha) \in \Sigma\) αφού η \(\alpha\) μπορεί να προκύψει με αναδιάταξη του \(\alpha\) (ταυτοτική).

Η σχέση είναι συμμετρική γιατί για κάθε \(\alpha, \beta \in S\), αν \((\alpha, \beta) \in \Sigma\), τότε και \((\beta, \alpha) \in \Sigma\). Αν συνέβαινε το αντίθετο τότε η λέξη \(\alpha\) δε θα μπορούσε να προκύψει με αναδιάταξη των γραμμάτων του \(\beta\), οπότε και η \(\beta\) δε θα μπορούσε να προκύψει με αναδιάταξη των στοιχείων του \(\alpha\), που είναι άτοπο.

Η σχέση είναι μεταβατική γιατί για οποιεσδήποτε λέξεις \(\alpha, \beta, \gamma\) που σχηματίζονται από τα γράμματα A, B, C, D, E, F, G, H, I και J, όταν η λέξη \(\beta\) προκύπτει με αναδιάταξη των γραμμάτων της λέξης \(\alpha\) και η λέξη \(\gamma\) προκύπτει με αναδιάταξη των γραμμάτων της λέξης \(\beta\), τότε η λέξη \(\gamma\) προκύπτει με αναδιάταξη των γραμμάτων της λέξης \(\alpha\).

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

β. Για να απαντήσουμε στο ερώτημα αυτό, αρκεί να προσέξουμε ότι σε κάθε υποσύνολο \(X_i\) περιλαμβάνονται όλοι οι δυνατές επαναδιατάξεις μιας συγκεκριμένης επιλογής \(n\) γραμμάτων από τα διαθέσιμα 10 γράμματα (προφανώς μπορούμε να έχουμε επαναλήψεις). Θα πρέπει να τονιστεί ότι δεν μπορεί να συμπεριληφθεί στο υποσύνολο \(X_i\) λέξη που δεν προκύπτει ως επαναδιάταξη των γραμμάτων κάποιου άλλου στοιχείου του υποσυνόλου, γιατί τότε δε θα ίσχυε η σχέση. Συνεπώς, το πλήθος των υποσυνόλων της διαμέρισης δεν είναι τίποτε άλλο από τους διαφορετικούς τρόπους με τους οποίους μπορούμε να επιλέξουμε \(n\) γράμματα από τα διαθέσιμα 10 γράμματα όταν επιτρέπονται επαναλήψεις γραμμάτων, δηλαδή \(\binom{n+10-1}{n}\).

(Η ίδια λύση ακριβώς για διαφορετικά γράμματα και για τις υπόλοιπες παραλλαγές.)

3(Α), 5(Β), 1(Γ), 5(Δ):

Α) Είναι ταυτολογία:

\[p \wedge q \wedge r \rightarrow p \vee q \equiv \neg(p \wedge q \wedge r) \vee p \vee q \equiv \neg p \vee \neg q \vee \neg r \vee p \vee q \equiv \neg p \vee p \vee \neg q \vee q \vee \neg r \equiv T \vee T \vee \neg r \equiv T\]

Β) Τίποτα από τα δύο:

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

Γ) Τίποτα από τα δύο:

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

Δ) Ταυτολογία:

\[\neg p \wedge \neg q \wedge \neg r \rightarrow \neg p \vee \neg q \equiv \neg(\neg p \wedge \neg q \wedge \neg r) \vee \neg p \vee \neg q \equiv p \vee q \vee r \vee \neg p \vee \neg q \equiv p \vee \neg p \vee \neg q \vee q \vee r \equiv T \vee T \vee r \equiv T\]

4(Α), 2(Β), 8(Γ), 1(Δ):

1. \(\exists y \forall x Q(x, y)\)

2. \(\forall x \exists y (x \neq y \wedge Q(y, x))\)

3. \(\forall x f(x)\), όπου \(f(x) = \exists y Q(x, y)\) είναι μία λογική συνάρτηση

4. \(\exists x \exists y (Q(x, y) \wedge Q(y, x) \wedge x \neq y)\)

5. \(\forall y \exists x Q(x, y)\)

6. \(\forall x \forall y (Q(x, y) \rightarrow (x \cap y \neq \emptyset))\) (το \(\emptyset\) είναι το κενό σύνολο)

7. \(\forall x \forall y \big(Q(x, y) \rightarrow (Q(x \cap y, y))\big)\)

8. \(\forall x \forall y \forall z \big((Q(x, y) \wedge Q(y, z)) \rightarrow (Q(x, z))\big)\)

α)

1. Αληθής: αναφέρει ότι υπάρχει ένα σύνολο που είναι υπερσύνολο κάθε στοιχείου του \(P(S_n)\). Αυτό το σύνολο είναι το \(S_n\) και για αυτό είναι αληθές.

2. Ψευδής: Δεν ισχύει όταν το \(x\) είναι το κενό σύνολο. Το μόνο υποσύνολό του είναι ο εαυτός του.

3. Αληθής: Όλα τα στοιχεία του \(P(S_n)\) είναι \(2^n\), και άρα μιλάμε για όλα τα στοιχεία του δυναμοσυνόλου. Πράγματι, ό,τι \(x\) και να βάλουμε αυτό θα είναι υποσύνολο του \(S_n\).

4. Ψευδής: Δεν ισχύει αφού λέει ότι υπάρχουν δύο υποσύνολα του \(S_n\) έτσι ώστε το ένα να είναι υποσύνολο του άλλου (και άρα ίσα) αλλά ταυτόχρονα να είναι διαφορετικά.

5. Αληθής: Αυτό που λέει είναι ότι για κάθε υποσύνολο \(y\) υπάρχει ένα υποσύνολο \(x\) που είναι υποσύνολό του. Πράγματι αν διαλέξουμε το \(x\) να είναι το κενό σύνολο αυτό ισχύει – προφανώς το κενό σύνολο ανήκει στο δυναμοσύνολο \(P(S_n)\).

6. Ψευδής: Αν το \(x\) είναι το κενό σύνολο προφανώς ισχύει ότι αυτό είναι υποσύνολο κάποιου άλλου συνόλου αλλά η τομή του με οποιοδήποτε σύνολο είναι πάλι το κενό σύνολο.

7. Αληθής: Αφού το \(x\) είναι υποσύνολο του \(y\) συνεπάγεται ότι και η τομή του με το \(y\) (που είναι πάλι \(x\)) θα είναι υποσύνολο του \(y\).

8. Αληθής: Είναι η μεταβατική ιδιότητα της σχέσης \(\subseteq\).

5(Α), 3(Β), 2(Γ), 4(Δ):

\[\sum_{n=1}^{k-1}\sum_{m=1}^{k} nm = \sum_{n=1}^{k-1} n \sum_{m=1}^{k} m = \frac{k(k+1)}{2}\sum_{n=1}^{k-1} n = \frac{k^2(k+1)(k-1)}{4}\]

Παρόμοια με το παραπάνω λύνονται όλα τα σχετικά θέματα.

6(Α), 8(Β), 5(Γ), 2(Δ):

α. Α,Δ) Το αριστερό μέλος της ισότητας περιγράφει με πόσους τρόπους μπορούμε να επιλέξουμε ομάδες με πληθάριθμο τουλάχιστον 2 από ένα σύνολο \(n\) ανθρώπων χωρίς να μας ενδιαφέρει η σειρά και χωρίς επανατοποθέτηση. Από αυτούς που επιλέχθηκαν στην ομάδα, έστω με πληθάριθμο \(i\), ορίζουμε έναν ως αρχηγό με \(i\) τρόπους και έναν ως υπαρχηγό με \(i-1\) τρόπους.

Το δεξιό μέλος αναφέρει ότι μπορούμε να επιλέξουμε πρώτα τον αρχηγό με \(n\) τρόπους, μετά τον υπαρχηγό με \(n-1\) τρόπους και έπειτα τους υπόλοιπους της ομάδας με τόσους τρόπους όσους και το πλήθος των υποσυνόλων από ένα σύνολο με \(n-2\) ανθρώπους.

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

Β,Γ) Το αριστερό μέλος της ισότητας περιγράφει με πόσους τρόπους μπορούμε να επιλέξουμε ομάδες με πληθάριθμο τουλάχιστον 3 από ένα σύνολο \(n\) ανθρώπων χωρίς να μας ενδιαφέρει η σειρά και χωρίς επανατοποθέτηση. Από αυτούς που επιλέχθηκαν στην ομάδα, έστω με πληθάριθμο \(i\), ορίζουμε έναν ως αρχηγό με \(i\) τρόπους, έναν ως υπαρχηγό με \(i-1\) τρόπους και έναν ως γραμματέα με \(i-2\) τρόπους.

Το δεξιό μέλος αναφέρει ότι μπορούμε να επιλέξουμε πρώτα τον αρχηγό με \(n\) τρόπους, μετά τον υπαρχηγό με \(n-1\) τρόπους, μετά τον γραμματέα με \(n-2\) τρόπους και έπειτα τους υπόλοιπους της ομάδας με τόσους τρόπους όσους και το πλήθος των υποσυνόλων από ένα σύνολο με \(n-3\) ανθρώπους.

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

β.

1. Πλήθος συναρτήσεων από το σύνολο Α στο σύνολο Β, όπου \(|A| = n\) και \(|B| = m\).

2. Πλήθος σχέσεων από το σύνολο Α στο σύνολο Β, όπου \(|A| = n\) και \(|B| = m\).

3. Πόσοι τρόποι υπάρχουν να επιλέξουμε 10 αναψυκτικά από τρεις τύπους αναψυκτικών: σόδα, πορτοκαλάδα και λεμονάδα, όπου τουλάχιστον 5 θα πρέπει να είναι λεμονάδες;

4. Αν επιλέγουμε τυχαία θετικούς ακεραίους, ποιο είναι το ελάχιστο πλήθος τέτοιων ακεραίων που πρέπει να επιλέξουμε ώστε να εγγυηθούμε ότι για δύο από αυτούς τους αριθμούς \(a\) και \(b\) θα ισχύει \(a \equiv b \pmod{6}\);

5. Μία δημοσκόπηση στην Ελλάδα έδωσε τα εξής αποτελέσματα όσον αφορά την ερώτηση για το αν ο Γιωρίκας (Γ), ο Πανίκας (Π) ή ο Μπαμπίκας (Μ) είναι κατάλληλοι για πρωθυπουργοί. Ο Γ είναι κατάλληλος με ποσοστό 65%, ο Π με ποσοστό 57%, ο Μ με ποσοστό 58%, ενώ 28% θεώρησαν κατάλληλους τους Γ και Π, 30% τους Γ και Μ, 27% τους Π και Μ και τέλος 12% και τους τρεις. Ποιο είναι το ποσοστό των ψηφοφόρων που δεν γουστάρουν κανένα για πρωθυπουργό; Τι συμπέρασμα βγάζετε από το αποτέλεσμα που πήρατε;

Λύσεις (οι παραλλαγές λύνονται με ίδιο τρόπο):

1. Κάθε τιμή του πεδίου ορισμού μπορεί να απεικονίζεται σε οποιαδήποτε τιμή του πεδίου τιμών. Δηλαδή, κάθε τιμή του πεδίου ορισμού μπορεί να αντιστοιχεί σε \(m\) τιμές από το πεδίο τιμών. Άρα, τόσοι τρόποι αντιστοίχισης υπάρχουν μεταξύ των δύο συνόλων και άρα τόσες είναι οι διαφορετικές συναρτήσεις: \(m^n\).

2. Το πλήθος των διατεταγμένων ζευγών από Α σε Β είναι \(nm\). Το πλήθος όλων των δυνατών σχέσεων είναι ίσο με το πλήθος όλων των δυνατών υποσυνόλων αυτών των διατεταγμένων ζευγών. Άρα το πλήθος των σχέσεων είναι \(2^{mn}\).

3. Αυτό είναι ισοδύναμο με το να επιλέξουμε 5 αναψυκτικά από τρεις τύπους αφού τα υπόλοιπα 5 θα πρέπει να είναι λεμονάδες. Αυτό μπορεί να γίνει με \(\binom{7}{5}\) τρόπους.

4. Για να είναι ισοδύναμοι mod 6 οι θετικοί ακέραιοι \(a\) και \(b\) θα πρέπει το υπόλοιπο της διαίρεσης με το 6 να είναι ίδιο. Υπάρχουν 6 δυνατές τιμές για το υπόλοιπο της διαίρεσης με το 6 (0, 1, 2, 3, 4, 5). Επομένως 7 αριθμοί θα πρέπει να επιλεγούν ώστε να εγγυηθούμε ότι δύο θα είναι ισοδύναμοι mod 6.

5. Έστω \(\Gamma\), \(\Pi\) και \(M\) τα σύνολα των ψηφοφόρων που θεωρούν κατάλληλους τους Γ, Π και Μ αντίστοιχα. Από την αρχή του εγκλεισμού/αποκλεισμού έχουμε:

\[|\Gamma \cup \Pi \cup M| = |\Gamma| + |\Pi| + |M| - |\Gamma \cap \Pi| - |\Gamma \cap M| - |\Pi \cap M| + |\Gamma \cap \Pi \cap M|\]

Εμείς όμως ψάχνουμε να βρούμε το ποσοστό που αναλογεί στο συμπλήρωμα του συνόλου \(\Gamma \cup \Pi \cup M\), το οποίο θα είναι ίσο με \(100 - |\Gamma \cup \Pi \cup M|\). Με βάση τα δεδομένα της άσκησης έχουμε:

\[100 - |\Gamma \cup \Pi \cup M| = 100 - |\Gamma| - |\Pi| - |M| + |\Gamma \cap \Pi| + |\Gamma \cap M| + |\Pi \cap M| - |\Gamma \cap \Pi \cap M| = 100 - 65 - 57 - 58 + 28 + 30 + 27 - 12 = -7\]

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

7(Α), 6(Β), 7(Γ), 8(Δ):

Α,Β,Γ,Δ:

Η πρόταση είναι ισοδύναμη με «Αν ο \(a\) είναι άρτιος, τότε \(a \leq 2\) ή ο \(a\) είναι σύνθετος αριθμός».

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

\(p\): ο \(a\) είναι άρτιος

\(q\): \(a \leq 2\)

\(r\): ο \(a\) είναι σύνθετος αριθμός

1. \(p \rightarrow q \vee r\)

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

Αν \(a > 2\) και ο \(a\) είναι πρώτος αριθμός τότε ο \(a\) είναι περιττός.

Αντίθετη: \(\neg(p \rightarrow q \vee r) \equiv \neg(\neg p \vee q \vee r) \equiv (p \wedge \neg q \wedge \neg r)\)

Ο \(a\) είναι άρτιος και \(a > 2\) και ο \(a\) είναι πρώτος αριθμός.

1. Αντιθετοαντίστροφο: Αν \(a > 2\) και ο \(a\) είναι πρώτος αριθμός, τότε ο \(a\) είναι περιττός.

Πράγματι, όλοι οι αριθμοί μεγαλύτεροι του 2 που είναι πρώτοι δεν μπορεί να είναι άρτιοι αφού διαιρούνται από το 2. Άρα όλοι είναι περιττοί.

Αντίφαση: Αφού \(a > 2\) και ο \(a\) είναι πρώτος αριθμός σημαίνει ότι ο \(a\) είναι περιττός, το οποίο έρχεται σε αντίφαση με την υπόθεση ότι ο \(a\) είναι άρτιος.

8(Α), 4(Β), 3(Γ), 6(Δ):

Να αποδείξετε ότι ο \(\text{ΜΚΔ}(\alpha, \alpha + n)\), όπου \(n \neq 0\), διαιρεί τέλεια τον \(n\) (δηλαδή να δείξετε ότι για \(n \neq 0\) ισχύει ότι \(\text{ΜΚΔ}(\alpha, \alpha + n) \mid n\))

Λύση:

Έστω ότι \(d = \text{ΜΚΔ}(\alpha, \alpha + n)\). Τότε \(d \mid \alpha\) και \(d \mid \alpha + n\). Άρα διαιρεί και οποιοδήποτε γραμμικό τους συνδυασμό. Άρα:

\[d \mid (\alpha + n - \alpha) \Rightarrow d \mid n\]

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

---

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