Διακριτά Μαθηματικά — Ιούνιος 2024 — Ομάδα Γ

Μεταγραφή από τις σελίδες 11–12 του αρχείου Discrete_Exams_June_24.pdf.

Discrete_Exams_June_24.pdf (σελ. 11-12)

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

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

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

1. (1) Όταν ένας \(n \in \mathbb{Z}\) διαιρεθεί με το 6 τότε το υπόλοιπο είναι 5. Ποιο είναι το υπόλοιπο αν ο \(7n\) διαιρεθεί με το 3;

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

3. (1,2) Ο κώδικας Morse χρησιμοποιεί ως σύμβολα “παύλες” και “τελείες” επιτρέποντας επαναλήψεις. Να υπολογιστεί το πλήθος των διαφορετικών συμβολοσειρών που μπορούν να σχηματιστούν στον κώδικα Morse εάν:

• i. Οι συμβολοσειρές πρέπει να αποτελούνται από 6 σύμβολα.

• ii. Οι συμβολοσειρές πρέπει να αποτελούνται από 10 σύμβολα και να ξεκινούν και να τελειώνουν με το ίδιο σύμβολο.

• iii. Οι συμβολοσειρές πρέπει να αποτελούνται από 10 σύμβολα, εκ των οποίων ακριβώς 4 να είναι παύλες.

• iv. Οι συμβολοσειρές πρέπει να αποτελούνται από 10 σύμβολα, εκ των οποίων τουλάχιστον 3 να είναι παύλες.

4. (0,8) Να δείξετε ότι η λογική πρόταση \(((p \to q) \to (p \land q)) \to p\) είναι ταυτολογία.

5. (1) Έστω οι ακέραιοι \(\alpha\) και \(b\). Να αποδείξετε ότι αν οι αριθμοί \(b\) και \(b^2 + a^2\) είναι περιττοί, τότε ο \(a\) είναι άρτιος.

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

6. (1,5) α) (0,5) Συμπληρώστε τα κενά στον παρακάτω υπολογισμό σχετικά με ένα άθροισμα και κάντε τη σωστή επιλογή όπου σας ζητείται κάτι τέτοιο:

«Για να αποδείξουμε ότι \(\sum_{i=1}^{m} i^3 \le \frac{(m+1)^4 - 1}{4}\) μπορούμε να χρησιμοποιήσουμε την μέθοδο ολοκληρώματος για να φράξουμε την τιμή του αθροίσματος. Συγκεκριμένα, θα πρέπει να υπολογίσουμε ένα _________________ (κάτω ή πάνω – επιλέξτε ένα από τα δύο) φράγμα του αθροίσματος που είναι ίσο με την τιμή του \(\int_b^a x^d \, dx\) όπου:

\(a =\) _________________, \(b =\) _________________, και \(d =\) _________________.»

β) (1) Να βρείτε τον κλειστό τύπο του αθροίσματος: \(\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \frac{1}{3 \cdot 4} + \cdots + \frac{1}{k \cdot (k+1)} = \sum_{j=1}^{k} \frac{1}{j(j+1)}\)

7. (2) Έστω το διμελές κατηγόρημα:

\(P(a, b) =\) "το \(a\) είναι υποσύνολο (όχι απαραίτητα γνήσιο) του \(b\) (\(a \subseteq b\))"

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

όπου ο τομέας αναφοράς είναι το δυναμοσύνολο των φυσικών αριθμών (δηλαδή όλα τα υποσύνολα του συνόλου των φυσικών αριθμών \(\mathbb{N}\)). Ποιες από τις παρακάτω προτάσεις είναι σωστές και ποιες είναι λανθασμένες με αιτιολόγηση:

1. Η λογική πρόταση \(\exists a \exists b \forall c (\neg P(a \cap b, c))\) είναι αληθής.
2. Η λογική πρόταση \(\exists a \left( (a \neq \emptyset) \land \left( \exists b \left( P(b, a) \land \left( \forall c \left( P(c, a) \to (z = b) \right) \right) \right) \right) \right)\) είναι αληθής.
3. Η λογική πρόταση \(\forall a \exists b (P(a, b) \land P(b, a))\) είναι αληθής.
4. Η λογική πρόταση \(\forall a \forall b ((a \cap b = a) \to P(a, b))\) είναι αληθής.

[sic: στη 2η πρόταση η ποσοτικοποιημένη μεταβλητή είναι το \(c\), αλλά το κατηγόρημα αναφέρει «\(z\)» όπως είναι τυπωμένο]

8. (2) α) (0,7) Να δείξετε ότι μεταξύ 19 οποιωνδήποτε λογικών προτάσεων που χρησιμοποιούν ακριβώς δύο προτασιακά σύμβολα \(s\) και \(t\), υπάρχουν δύο προτάσεις τουλάχιστον που είναι λογικά ισοδύναμες. (Υπόδειξη: χρησιμοποιείστε την αρχή των περιστερώνων)

β) (0,6) Να υπολογιστεί το πλήθος των διαφορετικών μη αρνητικών ακέραιων λύσεων της εξίσωσης \(5x_1 + x_2 + x_3 + x_4 + \cdots + x_{10} = 7\). (Υπόδειξη: να βρείτε αρχικά ποιες είναι οι δυνατές τιμές που μπορεί να πάρει το \(x_1\).)

γ) (0,7) Να αποδείξετε συνδυαστικά (και όχι αλγεβρικά) την ισότητα: \(\sum_{i=2}^{k} C(k, i) = 2^k - (k + 1)\) (Υπόδειξη: το αριστερό μέλος μπορεί να αντιστοιχηθεί στο πλήθος των υποσυνόλων ενός \(k\)-συνόλου με τουλάχιστον 2 στοιχεία.)

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

9. (2,5) Ο Χάρυ Πότερ κάνει μία εργασία για το μάθημα φίλτρων που έχει με τον καθηγητή Σνέιπ. Ο Σνέιπ του δίνει 5 διαφορετικούς μεγάλους δοκιμαστικούς σωλήνες και 13 φιαλίδια με μία σταγόνα η κάθε μία από κάποια ουσία, όπου όλες οι ουσίες είναι διαφορετικές ανά δύο μεταξύ τους. Η σταγόνα κάθε φιαλιδίου πρέπει να πέσει αυτούσια σε ένα δοκιμαστικό σωλήνα (δεν μπορείται να χωρίσετε τη σταγόνα σε δύο ή περισσότερους δοκιμαστικούς σωλήνες). Ο Χάρυ λοιπόν, έχοντας παρακολουθήσει το μάθημα των μαγικών Μαθηματικών, αρχίζει και αναρωτιέται διάφορα, για τα οποία χρειάζεται τη βοήθειά σας:

α) (0,5) Με πόσους τρόπους μπορεί να ρίξει τις 13 σταγόνες των φιαλιδίων στους 5 δοκιμαστικούς σωλήνες χωρίς κάποιο περιορισμό στους δοκιμαστικούς σωλήνες (κάθε δοκιμαστικός σωλήνας μπορεί να περιέχει μεταξύ 0 και 13 σταγόνων), όταν μας ενδιαφέρει η σειρά με την οποία θα πέσουν μέσα σε κάθε σωλήνα οι σταγόνες;

β) (1) Ο Χάρυ συνειδητοποιεί ότι οι συγκεκριμένες ουσίες θέλουν χρόνο να αντιδράσουν μεταξύ τους και άρα δεν τον ενδιαφέρει στην πραγματικότητα η σειρά με την οποία θα πέσουν μέσα στο σωλήνα. Θυμήθηκε τον καθηγητή Τσίχλορν που μίλαγε για σχέσεις ισοδυναμίας και σκέφτηκε να ορίσει την εξής σχέση \(R\) πάνω στο σύνολο όλων των τοποθετήσεων (όπως ορίστηκαν στο ερώτημα (α)) των 13 σταγόνων στους 5 δοκιμαστικούς σωλήνες: Για δύο τοποθετήσεις \(p\) και \(q\) (όπως αυτές ορίστηκαν στο ερώτημα (α)) θα ισχύει ότι \((p, q) \in R\) αν η \(q\) μπορεί να προκύψει από την \(p\) με μεταθέσεις των σταγόνων εντός του κάθε δοκιμαστικού σωλήνα (με αυτό τον τρόπο μοντελοποιούμε το γεγονός ότι δεν μας ενδιαφέρει η σειρά που θα πέσουν οι σταγόνες μέσα σε κάθε δοκιμαστικό σωλήνα). Να δείξετε ότι η σχέση \(R\) είναι σχέση ισοδυναμίας.

Υπόδειξη: η μετάθεση σε κάθε δοκιμαστικό σωλήνα, μπορεί να θεωρηθεί ως μία συνάρτηση \(f\) έτσι ώστε \(q = f(p)\) , όταν η τοποθέτηση \(q\) προκύπτει από την \(p\) με κάποια μετάθεση των σταγόνων της εντός κάθε δοκιμαστικού σωλήνα. Θεωρείστε δεδομένο ότι η \(f\) είναι μία αντιστρέψιμη συνάρτηση. Επίσης, αν \(f\) και \(g\) είναι μεταθέσεις, τότε και η σύνθεσή τους \(f \circ g\) είναι επίσης μετάθεση.

γ) (0,5) Να αποδείξετε ότι υπάρχουν κλάσεις ισοδυναμίας της \(R\) που δεν έχουν το ίδιο μέγεθος (πληθάριθμο).

δ) (0,5) Πόσες είναι οι κλάσεις ισοδυναμίας της σχέσης \(R\);

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

Λύσεις (🟢 official)

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

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

Discrete_Exams_June_24.pdf (σελ. 13-15)

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

1.

Με βάση το δεδομένο έχουμε ότι ο n γράφεται για κάποιον ακέραιο k ως:

\[n = 6k+5\]

Αν πολλαπλασιάσουμε με 7 έχουμε:

7𝑛= 42𝑘+ 35

το οποίοι γράφεται ως:

\[7n = 3(14k+11)+2\]

Αυτό σημαίνει ότι το υπόλοιπο που αφήνει το 7n όταν διαιρεθεί με το 3 είναι 2.

2.

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

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

Η R είναι συμμετρική αφού το (𝑥, 𝑦) ∈𝑅 συνεπάγεται ότι 𝑥= −𝑦, από όπου προκύπτει ότι 𝑦= −𝑥, το οποίο σημαίνει ότι (𝑦, 𝑥) ∈𝑅.

Η R δεν είναι αντισυμμετρική αφού (5, −5) ∈𝑅 και (−5,5) ∈𝑅, αλλά 5 ≠−5.

Η R δεν είναι μεταβατική αφού το (2,-2) ∈ R και (-2,2) ∈ R ενώ το (2,2) ∉ R.

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

3.

• i. Κάθε σύμβολο αντιστοιχεί σε συγκεκριμένη θέση που μπορεί να καλυφθεί είτε από “παύλα” είτε από “τελεία”. Επομένως έχουμε 6-δείγμα από 2-σύνολο, δηλ. 2⁶ διαφορετικές συμβολοσειρές.

• ii. Ακολουθώντας το (i), οι 8 θέσεις (εξαιρώντας την πρώτη και την τελευταία που θα πρέπει υποχρεωτικά να έχουν το ίδιο σύμβολο) συμπληρώνονται με 2⁸ διαφορετικούς τρόπους. Για κάθε έναν από αυτούς υπάρχουν 2 δυνατότητες κάλυψης των ακριανών θέσεων (είτε και οι δύο με “παύλα” είτε και οι δύο με “τελεία”). Από κανόνα γινομένου έπεται ότι συνολικά υπάρχουν 2 ∙2⁸ τέτοιες λέξεις.

• iii. Αυτό είναι ίδιο με τους τρόπους να τοποθετήσουμε 4 παύλες σε 10 θέσεις. Άρα επιλέγουμε 4 θέσεις χωρίς επανατοποθέτηση (κάθε θέση έχει 1 σύμβολο) και χωρίς να μας ενδιαφέρει η σειρά (οι τέσσερις παύλες είναι ίδιες). Άρα έχουμε έναν 4-συνδυασμό από 10-σύνολο, δηλαδή: (¹⁰ 4⁾

• iv. Σύμφωνα με το (i), όλες οι συμβολοσειρές με 10 σύμβολα είναι 2¹⁰ . Από αυτές αφαιρούμε όσες έχουν 0 “παύλες”, που είναι (¹⁰ 0^{) = 1, 1 “παύλα”, που είναι (10} 1^{) = 10, και 2 “παύλες”, που είναι} (¹⁰ 2^{) = 45. Άρα έχουμε 212 −(1 + 10 + 45) τέτοιες συμβολοσειρές συνολικά.}

4.

Θα το δείξουμε με πίνακα αληθείας.

p	q	𝑝→𝑞	𝑝∧𝑞	(𝑝→𝑞) →(𝑝∧𝑞)	((𝑝→𝑞) →(𝑝∧𝑞)) →𝑝
T	T	T	T	T	T
T	F	F	F	T	T
F	T	T	F	F	T
F	F	T	F	F	T

Άρα είναι ταυτολογία. Εναλλακτικά:

• ((𝑝→𝑞) →(𝑝∧𝑞)) →𝑝≡(( ¬ 𝑝∨𝑞) →(𝑝∧𝑞)) →𝑝

• ≡( ¬ ( ¬ 𝑝∨𝑞) ∨(𝑝∧𝑞)) →𝑝≡((𝑝∧ ¬ 𝑞) ∨(𝑝∧𝑞)) →𝑝

• ≡((𝑝∧ ¬ 𝑞) ∨(𝑝∧𝑞)) →𝑝≡ ¬ ((𝑝∧ ¬ 𝑞) ∨(𝑝∧𝑞)) ∨𝑝

• ≡(( ¬ 𝑝∨𝑞) ∧( ¬ 𝑝∨ ¬ 𝑞)) ∨𝑝≡(( ¬ 𝑝∨𝑞) ∧( ¬ 𝑝∨ ¬ 𝑞)) ∨𝑝

• ≡(( ¬ 𝑝∧ ¬ 𝑝) ∨( ¬ 𝑝∧ ¬ 𝑞) ∨(𝑞∧ ¬ 𝑝) ∨(𝑞∧ ¬ 𝑞)) ∨𝑝

• ≡ ¬ 𝑝∨( ¬ 𝑝∧ ¬ 𝑞) ∨(𝑞∧ ¬ 𝑝) ∨𝐹∨𝑝≡ ¬ 𝑝∨𝑝∨( ¬ 𝑝∧ ¬ 𝑞) ∨(𝑞∧ ¬ 𝑝) ≡T ∨( ¬ 𝑝∧ ¬ 𝑞) ∨(𝑞∧ ¬ 𝑝) ≡T

5.

Θα το αποδείξουμε με αντίφαση. Θα αποδείξουμε την πρόταση: Οι αριθμοί 𝑏 και 𝑏² + 𝑎² είναι περιττοί και ο 𝑎 είναι περιττός.

Αφού οι 𝑏 και 𝑎 είναι περιττοί σημαίνει ότι υπάρχουν ακέραιοι 𝑘, 𝑙 έτσι ώστε να ισχύει:

𝑏= 2𝑘+ 1 𝑎= 2𝑙+ 1

Αντικαθιστώντας στο 𝑏² + 𝑎² έχουμε:

𝑏² + 𝑎² = (2𝑘+ 1)² + (2𝑙+ 1)² = 4𝑘² + 4𝑘+ 1 + 4𝑙² + 4𝑙+ 1 = 2(2𝑘² + 2𝑙² + 2𝑘+ 2𝑙+ 1) το οποίο σημαίνει ότι το 𝑏² + 𝑎² είναι άρτιος αριθμός. Αυτό είναι άτοπο όμως αφού θεωρήσαμε ότι το 𝑏² + 𝑎² είναι περιττός. Επομένως αποδείχτηκε η αρχική πρόταση.

6.

(α) άνω φράγμα , 𝑎= 𝑚+ 1, 𝑏= 1, 𝑑= 3

1 1 1 = − (β) Έχουμε ότι: από διάσπαση σε απλά κλάσματα. 𝑘∙(𝑘+1) 𝑘 𝑘+1 𝑚 1 − 1 1 Άρα ∑𝑗=1 𝑗 𝑗+1 = 1 − 𝑚+1, από το τηλεσκοπικό άθροισμα.

7.

1. Λάθος. Η δεδομένη λογική πρόταση δηλώνει ότι υπάρχουν δύο σύνολα φυσικών αριθμών, η τομή των οποίων δεν έχει κανένα υπερσύνολο το οποίο να είναι σύνολο φυσικών αριθμών. Αυτό δεν αληθεύει, καθώς οποιοδήποτε σύνολο ακεραίων έχει ως υπερσύνολο του το ℕ. Συνεπώς αν το 𝑐 είναι το σύνολο των φυσικών αριθμών ℕ, τότε η ∀𝑎∀𝑏𝑃(𝑎∩𝑏, 𝑐= ℕ) είναι αληθής και άρα η ¬(∀𝑎∀𝑏𝑃(𝑎∩𝑏, 𝑐= ℕ)) ≡∃𝑎∃𝑏¬𝑃(𝑎∩𝑏, 𝑐= ℕ) είναι ψευδής, για οποιαδήποτε σύνολα φυσικών αριθμών 𝑎 και 𝑏.

2. Λάθος. Η δεδομένη λογική πρόταση δηλώνει ότι υπάρχει ένα μη κενό σύνολο φυσικών αριθμών, το οποίο έχει ακριβώς ένα υποσύνολο. Αυτό είναι ψευδές, καθώς κάθε μη κενό υποσύνολο του ℕ έχει τουλάχιστον δύο υποσύνολα: τον εαυτό του και το κενό σύνολο.

3. Σωστό. Επειδή κάθε σύνολο είναι υποσύνολο του εαυτού του, για κάθε σύνολο 𝑎 θέτουμε 𝑏= 𝑎, έτσι ώστε η πρόταση 𝑃(𝑎, 𝑏) ∧𝑃(𝑏, 𝑎) να αληθεύει.

4. Σωστό. Αν το 𝑎∩𝑏= 𝑎 είναι αληθές, τότε για κάθε φυσικό αριθμό 𝑛, ισχύει ότι αν 𝑛∈𝑎 τότε 𝑛∈𝑎∩ 𝑏, που συνεπάγεται 𝑛∈𝑏. Άρα το 𝑎 είναι υποσύνολο του 𝑏, που συνεπάγεται ότι το 𝑃(𝑎, 𝑏) είναι αληθές. Συνεπώς για οποιαδήποτε σύνολα 𝑎 και 𝑏, η συνεπαγωγή 𝑎∩𝑏= 𝑎→𝑃(𝑎, 𝑏) αληθεύει.

8.

α) Δύο λογικές προτάσεις είναι λογικά ισοδύναμες στις μεταβλητές s και t όταν έχουν τις ίδιες τιμές αληθείας. Με δύο μεταβλητές μπορούν να φτιαχτούν 4 συνδυασμοί (ο πίνακας αληθείας μίας πρότασης έχει 4 γραμμές). Για κάθε γραμμή του πίνακα υπάρχουν 2 δυνατότητες για την τιμή αληθείας μίας πρότασης. Άρα μπορούν να φτιαχτούν 2⁴ = 16 διαφορετικές στήλες, που αντιστοιχούν σε 16 λογικές προτάσεις που ανά δύο δεν είναι λογικά ισοδύναμες. Αν αυτές είναι οι περιστερώνες και οι 19 λογικές προτάσεις της εκφώνησης είναι τα περιστέρια, αναγκαστικά 2 από αυτές θα είναι λογικά ισοδύναμες αφού θα έχουν τον ίδιο πίνακα αληθείας (αρχή των περιστερώνων).

β) Δύο αμοιβαία αποκλειόμενες περιπτώσεις 𝑥1 = 0 ή 𝑥1 = 1.

Εάν 𝑥1 = 0 υπάρχουν (^{9 + 7 −1} 7 ) (7 επιλογή από 9-σύνολο) διαφορετικές μη αρνητικές ακέραιες λύσεις. Εάν 𝑥1 = 1 υπάρχουν (^{9 + 2 −1} 2 ) (2 επιλογή από 9-σύνολο) διαφορετικές μη αρνητικές ακέραιες λύσεις.

Από τον κανόνα αθροίσματος, υπάρχουν συνολικά (¹⁵ 7^{) + (10} 2^{) διαφορετικές μη αρνητικές ακέραιες} λύσεις της αρχικής εξίσωσης.

γ) Χρησιμοποιώντας την υπόδειξη έχουμε αντιστοιχήσει το αριστερό μέλος της ισότητας σε ένα πρόβλημα μέτρησης. Αρκεί να εκφράσουμε τη λύση σε αυτό το πρόβλημα με την έκφραση στο δεξιό μέλος. Πράγματι, όλα τα δυνατά υποσύνολα ενός 𝑘-συνόλου είναι 2^𝑘 . Από αυτά όμως δεν πρέπει να υπολογίσουμε το κενό υποσύνολο ((^𝑘 0^{) συνολικά) καθώς και όλα τα υποσύνολα με ένα στοιχείο που είναι (𝑘} 1^{) συνολικά. Άρα το} πλήθος των υποσυνόλων με τουλάχιστον 2 στοιχεία είναι 2^𝑘 −(^𝑘 0^{) −(𝑘} 1^{) = 2𝑘−(𝑘+ 1). Αποδείχτηκε το} ζητούμενο.

9. α) Στην πραγματικότητα το πρόβλημα αναφέρεται στους τρόπους με τους οποίους μπορούμε να τοποθετήσουμε 13 διαφορετικές σφαίρες (οι 13 σταγόνες) σε 5 διαφορετικές υποδοχές (οι 5 δοκιμαστικοί σωλήνες) όπου μας ενδιαφέρει η σειρά με την οποία θα πέσουν οι σφαίρες σε κάθε υποδοχή. Από τον σχετικό τύπο έχουμε ότι οι τρόποι να συμβεί αυτό είναι:

\[\frac{(n+r-1)!}{(n-1)!} = \frac{(5+13-1)!}{(5-1)!} = \frac{17!}{4!} = 14.820.309.504.000 \text{ τρόποι}\]

β) Θα δείξουμε ότι είναι σχέση ισοδυναμίας, αποδεικνύοντας ότι έχει τις τρεις γνωστές ιδιότητες. Έστω 𝑝, 𝑞, 𝑟 τοποθετήσεις 13 σταγονιδίων (σφαιρών) σε 5 δοκιμαστικούς σωλήνες (υποδοχές) όπου μας ενδιαφέρει η σειρά με την οποία τοποθετούνται οι σταγόνες στους σωλήνες.

Ανακλαστική: (𝑝, 𝑝) ∈𝑅 Ισχύει, αφού η τοποθέτηση 𝑝 προκύπτει από τον εαυτό της χωρίς καμία μετάθεση των σταγόνων μέσα σε κάθε φιαλίδιο. (ταυτοτική μετάθεση εντός κάθε σωλήνα). Άρα είναι ανακλαστική. Συμμετρική: Έστω ότι (𝑝, 𝑞) ∈𝑅. Αυτό σημαίνει ότι υπάρχει μία μετάθεση των σταγόνων σε κάθε φιαλίδιο της τοποθέτησης 𝑝 ώστε από αυτή να προκύψει η 𝑞. Αν πάρουμε την αντίστροφη μετάθεση (πάντα υπάρχει σύμφωνα με την υπόδειξη) τότε από την 𝑞 προκύπτει η 𝑝. Άρα (𝑞, 𝑝) ∈𝑅 και επομένως είναι συμμετρική. Μεταβατική: Έστω ότι (𝑝, 𝑞) ∈𝑅 και (𝑞, 𝑟) ∈𝑅. Αυτό σημαίνει ότι υπάρχει μετάθεση από 𝑝 προς 𝑞 και από 𝑞 προς 𝑟. Συνθέτοντας τις δύο μεταθέσεις παίρνουμε μία μετάθεση από 𝑝 προς 𝑟. Άρα (𝑝, 𝑟) ∈𝑅 και άρα είναι μεταβατική.

Επομένως η σχέση 𝑅 είναι σχέση ισοδυναμίας.

γ) Αν ρίξουμε και τις 13 σταγόνες στον πρώτο δοκιμαστικό σωλήνα τότε αυτή η κλάση ισοδυναμίας περιέχει 13! τοποθετήσεις, όσες είναι δηλαδή και οι μεταθέσεις των 13 σταγόνων. Αν ρίξουμε 6 σταγόνες στον πρώτο σωλήνα και 7 στον δεύτερο, τότε η κλάση ισοδυναμίας θα περιέχει 6! × 7! τοποθετήσεις, όσοι δηλαδή οι συνδυασμοί των διαφορετικών μεταθέσεων των δύο σωλήνων. Ισχύει ότι 13! > 6! × 7!. δ) Από το ερώτημα (γ) προκύπτει ότι δεν μπορούμε να χρησιμοποιήσουμε την αρχή της διαίρεσης στο ερώτημα (α) για να πάρουμε την απάντηση. Όμως προκύπτει πιο εύκολα:

Οι κλάσεις ισοδυναμίας της 𝑅 είναι το πλήθος των διαφορετικών τρόπων που μπορούμε να ρίξουμε τις 13 σταγόνες σε 5 δοκιμαστικούς σωλήνες χωρίς κανένα περιορισμό και χωρίς να μας ενδιαφέρει η σειρά με την οποία θα πέσουν. Αυτό είναι ισοδύναμο με το να τοποθετήσουμε 13 διαφορετικές σφαίρες σε 5 διαφορετικές υποδοχές χωρίς να μας ενδιαφέρει η σειρά εντός κάθε υποδοχής. Από τον σχετικό γνωστό τύπο αυτό είναι:

\[n^r = 5^{13} = 1.220.703.125 \text{ τρόπους}\]

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

---

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