Διακριτά Μαθηματικά — Φεβρουάριος 2025¶

Μεταγραφή από τις σελίδες 1–12 του αρχείου eClass Discrete_Exams_January_25 - All_Groups - A.pdf.

Discrete_Exams_January_25 - All_Groups - A.pdf (σελ. 1-12)¶

ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ ΕΞΕΤΑΣΗ ΣΤΟ ΜΑΘΗΜΑ «ΔΙΑΚΡΙΤΑ ΜΑΘΗΜΑΤΙΚΑ» - 28/02/2025¶

Διάρκεια Εξέτασης 2 ώρες και 40 λεπτά – Ομάδα Α

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

Ονοματεπώνυμο: _______________________________________________________________

Αρ. Μητρώου: __________________________________________________________________

Έτος: _________________________________________________________________________ Θέματα Μικρής Δυσκολίας (6 μονάδες)¹

1. (1) Έστω η σχέση \(R=\{(x,y):\) ο \(x\) κάθεται στην ίδια γραμμή με τον \(y\) μέσα στο αμφιθέατρο\(\}\) πάνω στο σύνολο \(\Phi\) των φοιτητών που είναι μέσα στο αμφιθέατρο. Αποδείξτε αν αυτή η σχέση είναι ή δεν είναι σχέση ισοδυναμίας. Αν είναι σχέση ισοδυναμίας, ποιες είναι οι κλάσεις ισοδυναμίας (συνοπτική περιγραφή); Απάντηση:

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

1

2. (1,5) Έστω ότι ψάχνετε το κινητό σας και κάνετε τους εξής συλλογισμούς:

«Αν το κινητό είναι στο τραπεζάκι του σαλονιού, τότε το χρησιμοποίησα κατά τη διάρκεια της ταινίας.»
«Αν δεν έβλεπα ταινία στο υπνοδωμάτιο, τότε θα έβλεπα ταινία στο σαλόνι.»
«Αν έβλεπα ταινία στο υπνοδωμάτιο, τότε το κινητό είναι στο κομοδίνο.»
«Δεν χρησιμοποίησα το κινητό κατά τη διάρκεια της ταινίας.»
«Αν έβλεπα ταινία στο σαλόνι, τότε το κινητό μου είναι στο τραπεζάκι του σαλονιού.»
«Το κινητό μπορεί να βρίσκεται σε ένα μέρος μόνο.»
i) (0,7) Χρησιμοποιώντας τις ακόλουθες προτασιακές μεταβλητές με την παρακάτω ερμηνεία να μετατρέψετε τους παραπάνω συλλογισμούς της φυσικής γλώσσας σε λογικές προτάσεις.

\(P\): Το κινητό είναι στο τραπεζάκι του σαλονιού.

\(Q\): Χρησιμοποίησα το κινητό κατά τη διάρκεια της ταινίας.
\(R\): Έβλεπα ταινία στο υπνοδωμάτιο.
\(S\): Έβλεπα ταινία στο σαλόνι.

\(T\): Το κινητό είναι στο κομοδίνο.

ii) (0,8) Ζητάμε να βρείτε τη θέση του κινητού. Δώστε τυπική απόδειξη για την ορθότητα του επιχειρήματός σας χρησιμοποιώντας κανόνες εξαγωγής συμπεράσματος. Υπόδειξη: Την πρόταση 6 μπορείτε να τη θεωρήσετε δεδομένη χωρίς να τη λάβετε υπόψη στην απόδειξή σας.

Απάντηση:

2

3. (0,8) Να αποδειχθεί ότι αν ο \(n^5+3\) είναι άρτιος, τότε ο \(n\) είναι περιττός, όπου ο \(n\) είναι ακέραιος. Υπόδειξη: Χρησιμοποιήστε το γεγονός ότι το γινόμενο δύο αριθμών είναι άρτιος αν και μόνο αν τουλάχιστον ένας από τους δύο είναι άρτιος και ότι το άθροισμα δύο ακέραιων είναι περιττό αν και μόνο αν ένας ακριβώς από τους δύο είναι περιττός.

Απάντηση:¶

4. (1,5) Οι παρακάτω ερωτήσεις πολλαπλής επιλογής δίνουν +0,3 όταν η απάντηση είναι σωστή και −0,2 όταν είναι λάθος. Αν δεν απαντήσετε σε ένα ερώτημα, δεν λαμβάνεται υπόψη στη βαθμολόγηση. Θεωρούμε το σύνολο των 24 γραμμάτων του ελληνικού αλφάβητου \(\Gamma=\{\alpha,\beta,\gamma,\ldots,\omega\}\). Να αναφέρετε ποιες είναι οι σωστές απαντήσεις χωρίς αιτιολόγηση (κυκλώστε την απάντησή σας).

1. Πόσα μη κενά υποσύνολα έχει το \(\Gamma\) συνολικά;

[ ] α) \(24!-1\)
[ ] β) \(\binom{24}{1}-1\)
[ ] γ) \(2^{24}-1\)
[ ] δ) \(24^2-1\)

2. Πόσες είναι οι διαφορετικές συμβολοσειρές 12 γραμμάτων χωρίς να επαναλαμβάνουμε κάποιο γράμμα;

[ ] α) \(12!\)
[ ] β) \(\binom{24}{12}\)
[ ] γ) \(24^{12}\)
[ ] δ) \(\frac{24!}{12!}\)

3. Πόσες είναι οι διαφορετικές συμβολοσειρές 6 γραμμάτων όταν επιτρέπονται επαναλήψεις γραμμάτων;

[ ] α) \(6!\)
[ ] β) \(\binom{24}{6}\)
[ ] γ) \(24^{6}\)
[ ] δ) \(\frac{24!}{6!}\)

4. Πόσες είναι οι διαφορετικές συμβολοσειρές μήκους 48 όπου κάθε γράμμα του \(\Gamma\) εμφανίζεται ακριβώς δύο φορές;

[ ] α) \(24^{48}\)
[ ] β) \(\frac{48!}{(2!)^{24}}\)
[ ] γ) \(\binom{48}{24}\)
[ ] δ) \(\binom{24+48-1}{48}\)

5. Πόσα είναι τα διαφορετικά σύνολα (δεν μας ενδιαφέρει η σειρά) 5 ή 6 γραμμάτων όταν επιτρέπονται οι επαναλήψεις;

[ ] α) \(\binom{24}{5}+\binom{24}{6}\)
[ ] β) \(\binom{24+5-1}{5}+\binom{24+6-1}{6}\)
[ ] γ) \(\binom{24}{5}\cdot\binom{24}{6}\)
[ ] δ) \(\binom{24+5-1}{5}\cdot\binom{24+6-1}{6}\)

3

5. (1,2) α) (0,7) Το διπλανό γράφημα αναπαριστά το πρόβλημα των γεφυρών του Königsberg, όπου οι αριθμοί είναι ετικέτες των ακμών και τα γράμματα ετικέτες των κορυφών. Απαντήστε τα εξής: i) Γιατί το συγκεκριμένο γράφημα δεν έχει κύκλωμα Euler; ii) Πως θα αλλάζατε το γράφημα με το ελάχιστο πλήθος προσθαφαιρέσεων ακμών ώστε να έχει κύκλωμα Euler;

β) (0.5) Να αποδείξετε αν υπάρχει απλό μη-κατευθυνόμενο γράφημα με 6 κορυφές και 16 ακμές.

[Σχήμα: γράφημα με τέσσερις κορυφές α, β, γ, δ. Ακμές: α–β (ετικέτα 1), α–δ (ετικέτα 2), α–γ (ετικέτα 3), β–γ με δύο ακμές (ετικέτες 4 και 6), γ–δ με δύο ακμές (ετικέτες 5 και 7).]

Απάντηση:

4

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

6. (1,5) Έστω ένα διμελές κατηγόρημα \(P(x,y)=\) "οι κορυφές \(x\) και \(y\) συνδέονται με μία ακμή" που εφαρμόζεται πάνω σε απλά μη-κατευθυνόμενα γραφήματα \(G=(V,E)\) – \(V\) είναι το σύνολο των κορυφών και \(E\) το σύνολο των ακμών – και ο τομέας αναφοράς των μεταβλητών είναι οι κορυφές του. Αφού το γράφημα είναι απλό, για κάθε κορυφή \(x\) θα ισχύει ότι \(P(x,x)\) είναι ψευδές.

α) Να γράψετε προτάσεις της κατηγορηματικής λογικής που να εκφράζουν ότι:
Το γράφημα περιέχει τουλάχιστον μία μεμονωμένη κορυφή (κορυφή με βαθμό 0)
Κάθε κορυφή έχει βαθμό τουλάχιστον 1
Το γράφημα είναι πλήρες (περιέχονται όλες οι δυνατές ακμές)
β) Φτιάξτε ένα γράφημα με 5 κορυφές που να ικανοποιεί την παρακάτω λογική πρόταση:

\[\exists x\,\forall y\,\big((x\neq y)\rightarrow\big(P(x,y)\wedge\forall z\,((z\neq x)\rightarrow\neg P(z,y))\big)\big)\]

Έπειτα, φτιάξτε ένα ακόμα γράφημα με 5 κορυφές που να μην ικανοποιεί την παραπάνω λογική πρόταση αλλά να ικανοποιεί την παρακάτω:

\[\forall x\,\forall y\,\big((x\neq y)\rightarrow\big(P(x,y)\vee\exists z\,(P(x,z)\wedge P(z,y))\big)\big)\]

Απάντηση:¶

5

7. (1,5) Έστω η αναδρομική σχέση \(p(n)=p\left(\frac{n}{2}\right)+n\) με αρχική συνθήκη \(p(1)=1\), που περιγράφει προσεγγιστικά το αναμενόμενο πλήθος των συγκρίσεων του αλγορίθμου εύρεσης του μεσαίου στοιχείου σε έναν πίνακα με \(n\) στοιχεία. Υποθέστε ότι το \(n\) είναι δύναμη του 2.

α) Να εκφράσετε το \(p(n)\) σε σχέση με ένα άθροισμα, χρησιμοποιώντας τη μέθοδο της επανάληψης.

β) Βρείτε τον κλειστό τύπο για το άθροισμα. Υπόδειξη: ο κλειστός τύπος στον οποίο πρέπει να καταλήξετε είναι ο \(p(n)=n\left(2-2^{-\log n}\right)\)

γ) Αποδείξτε με επαγωγή ότι πράγματι ο κλειστός σας τύπος αποτελεί λύση της αναδρομικής σχέσης \(p(n)\) έτσι ώστε να αποκλείσετε την περίπτωση κάποιου σφάλματος. Προτείνεται να κάνετε επαγωγή στη μεταβλητή \(k\), όπου \(n=2^{k}\), αφού το \(n\) είναι δύναμη του 2 σύμφωνα με την εκφώνηση.

Απάντηση:

6

8. (1,5) Στις απαντήσεις σας, δεν χρειάζεται να δώσετε αριθμητική τιμή. Ο τύπος μαζί με μία σύντομη αιτιολόγηση μίας γραμμής είναι αρκετός.

α) (0,6) Ένα σχολείο έχει 100 (διαφορετικούς) μαθητές, και διαθέτει 8 διαφορετικούς τίτλους βιβλίων, σε απεριόριστο αριθμό αντιγράφων τον καθένα. Να υπολογιστούν:

i. Οι τρόποι με τους οποίους μπορούμε να δώσουμε 1 βιβλίο σε κάθε μαθητή.
ii. Οι τρόποι με τους οποίους μπορούν να διανεμηθούν 10 βιβλία (όχι κατ’ ανάγκη διαφορετικά μεταξύ τους) σε κάθε μαθητή, αν δεν παίζει ρόλο η σειρά με την οποία διανέμονται τα βιβλία σε κάθε μαθητή.

β) (0.9) Μια πιτσαρία προσφέρει για τις πίτσες της δυνατότητα επιλογής από 10 διαφορετικά υλικά που μπορούν να προστεθούν επάνω στη βάση της ζύμης χωρίς να τους ενδιαφέρει η σειρά. Να υπολογιστούν:

i. Οι διαφορετικές πίτσες με ακριβώς 3 διαφορετικά υλικά (δηλαδή, δεν επιτρέπεται η επιλογή του ίδιου υλικού πάνω από μία φορά στην ίδια πίτσα) που μπορούν να αναφερθούν στο μενού της πιτσαρίας.
ii. Οι διαφορετικές πίτσες που μπορούν να αναφερθούν στο μενού της πιτσαρίας, με τουλάχιστον 1 και το πολύ 10 υλικά.
ii. Οι διαφορετικές πίτσες με ακριβώς 3 διαφορετικά υλικά ή 5 διαφορετικά υλικά (ισχύουν τα ίδια όπως στο ερώτημα i) που μπορούν να αναφερθούν στο μενού της πιτσαρίας. [sic: η ένδειξη «ii.» επαναλαμβάνεται στο πρωτότυπο]

Απάντηση:

7

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

9. (1) Να αποδείξετε συνδυαστικά (και όχι αλγεβρικά) την ισότητα:

\[\frac{n!}{r_1!\cdot r_2!\cdot r_3!\cdot\ldots\cdot r_k!}=\binom{n}{r_1}\cdot\binom{n-r_1}{r_2}\cdot\binom{n-r_1-r_2}{r_3}\cdot\ldots\cdot\binom{n-\sum_{i=1}^{j}r_i}{r_{j+1}}\cdot\ldots\cdot\binom{r_k}{r_k}\]

όπου ισχύει ότι \(r_1+r_2+\cdots+r_k=n\). Απάντηση:

8

10. (2) Ένας τρελός επιστήμονας στον πλανήτη των Άσγκαρντ κατασκεύασε έναν αντιγραφέα, το οποίο είναι ένα νοήμον τεχνητό είδος που έχει την ιδιότητα να αντιγράφεται καταναλώνοντας οτιδήποτε. Συγκεκριμένα, παρουσία πρώτων υλών λειτουργεί ως εξής: την επόμενη μέρα της κατασκευής του παράγει τρία νέα αντίγραφα του εαυτού του και τις υπόλοιπες μέρες απλά προστατεύει αυτά που αντιγράφονται. Τα εξής συμβαίνουν τις πρώτες μέρες:

Μέρα 0 : Ο επιστήμονας φτιάχνει τον αντιγραφέα \(P_1\).

Μέρα 1 : Το \(P_1\) κατασκευάζει τα \(P_2\), \(P_3\) και \(P_4\).

Μέρα 2 : Το \(P_2\) κατασκευάζει τα \(P_5\), \(P_6\) και \(P_7\), το \(P_3\) κατασκευάζει τα \(P_8\), \(P_9\) και \(P_{10}\) ενώ το \(P_4\) κατασκευάζει τα \(P_{11}\), \(P_{12}\) και \(P_{13}\) ενώ το \(P_1\) απλά προστατεύει τα υπόλοιπα.

Οι Άσγκαρντ έχουν τα σχέδια για ένα νέο όπλο με στόχο να καταστρέψουν τους αντιγραφείς πάνω στον πλανήτη τους ώστε να αποτρέψουν τον αφανισμό τους. Το πρόβλημα είναι ότι αυτό το όπλο χρησιμοποιείται μία φορά και έπειτα αχρηστεύεται αφού όμως πρώτα καταστρέψει \(3^{20}\) αντιγραφείς στον πλανήτη.

α) Δώστε την αναδρομική σχέση που περιγράφει το πλήθος των αντιγραφέων στον πλανήτη την ημέρα \(n\). β) Πόσες μέρες έχουν στη διάθεσή τους οι Άσγκαρντ για να κατασκευάσουν το νέο όπλο (μπορούν να κατασκευάσουν μόνο ένα) αν θέλουν να τους καταστρέψουν εντελώς; (δεν χρειάζεται να βρείτε ακριβές αριθμητικό αποτέλεσμα – απλά τον κλειστό τύπο της αναδρομής και την ανίσωση που πρέπει να λυθεί) Απάντηση:

9

10

Πρόχειρο

11

Πρόχειρο

12

Λύσεις (🟢 official)

Κατάσταση: 🟢 official Πηγή: ενδεικτικές λύσεις (σελίδες 13–15 του αρχείου eClass «Discrete_Exams_January_25 - All_Groups - A.pdf»)

Προσοχή

Η ενδεικτική λύση φέρει κεφαλίδα «(A)» και δεν υπάρχει κλειδί για τις άλλες ομάδες στο αρχείο.

Λύσεις — Διακριτά Μαθηματικά — Φεβρουάριος 2025¶

Discrete_Exams_January_25 - All_Groups - A.pdf (σελ. 13-15)¶

ΕΝΔΕΙΚΤΙΚΕΣ ΛΥΣΕΙΣ (A)¶

1.¶

Η 𝑅 είναι ανακλαστική. Πράγματι, για κάθε φοιτητή 𝑤∈𝛷 μέσα στο αμφιθέατρο, ισχύει ότι (𝑤, 𝑤) ∈𝑅 αφού ο φοιτητής κάθεται στην ίδια γραμμή με τον εαυτό του.

Η 𝑅 είναι συμμετρική αφού αν (𝑤1, 𝑤2) ∈𝑅, τότε ο 𝑤1 κάθεται στην ίδια σειρά με τον 𝑤2 και άρα και αντίστροφα ο 𝑤2 κάθεται στην ίδια σειρά με τον 𝑤1. Επομένως, (𝑤2, 𝑤1) ∈𝑅, και άρα είναι συμμετρική. Η 𝑅 είναι μεταβατική αφού αν (𝑤1, 𝑤2) ∈𝑅 και (𝑤2, 𝑤3) ∈𝑅, τότε ο 𝑤1 είναι στην ίδια σειρά με τον 𝑤2 και ο 𝑤2 είναι στην ίδια σειρά με τον 𝑤3. Άρα, και ο 𝑤1 είναι στην ίδια σειρά με τον 𝑤3. Επομένως, (𝑤1, 𝑤3) ∈𝑅, και άρα είναι μεταβατική.

Οι κλάσεις ισοδυναμίας είναι τα υποσύνολα φοιτητών που κάθονται στις ίδιες γραμμές του αμφιθεάτρου.

2.¶

i) Οι προτάσεις που αντιστοιχούν σε κάθε συλλογισμό-δήλωση με την ίδια σειρά είναι:

𝑃→𝑄
¬𝑅→𝑆
𝑅→𝑇
¬𝑄
𝑆→𝑃
Εδώ θα πρέπει να εκφράσουμε ότι το κινητό μπορεί να είναι μόνο σε μία θέση. Δηλαδή, να είναι στο κομοδίνο ή στο τραπεζάκι αλλά να μην μπορεί να είναι σε δύο ή σε καμία από αυτές τις θέσεις. Αυτό το εκφράζουμε ως εξής:

(𝑃∧¬𝑇) ∨(¬𝑃∧𝑇)

ii)

¬𝑃 (MT:4,1) 8. ¬𝑆 (MT:7,5) 9. ¬¬𝑅 (MT:8,2) 10. 𝑅 (διπλή άρνηση στο 9) 11. 𝛵 (MP:10,3)

Άρα, αποδείχτηκε ότι το κινητό είναι στο κομοδίνο δεδομένης και της πρότασης 6 που αποκλείει να βρίσκεται ταυτόχρονα και σε άλλη θέση.

3.¶

Με απαγωγή σε άτοπο. Έστω ότι n⁵ +3 είναι άρτιος και n άρτιος. Τότε και το n⁵ θα είναι άρτιος αριθμός αφού το γινόμενο άρτιων αριθμών δίνει άρτιο αριθμό. Όμως το άθροισμα άρτιου και περιττού (το 3) είναι περιττός αριθμός. Άρα ο n⁵ +3 είναι περιττός που είναι άτοπο.

4.¶

γ
δ
γ
β
β

5.¶

α) i. Γνωρίζουμε ότι σε κάθε γράφημα, αν ο βαθμός ενός κόμβου είναι περιττός αριθμός τότε ο κόμβος αυτός δεν μπορεί να είναι εσωτερικός κόμβος του συγκεκριμένου μονοπατιού Euler. Όμως σε ένα κύκλο Euler όλοι οι κόμβοι είναι εσωτερικοί και άρα όλοι πρέπει να έχουν άρτιο βαθμό. Αφού το γράφημα έχει 4 κόμβους με περιττό βαθμό δεν υπάρχει κύκλος Euler.

ii. Προσθέτουμε δύο ακμές μεταξύ των a και b και μεταξύ των c και d, τις οποίες τις ονομάζουμε 8 και 9 αντίστοιχα.

β) Όχι δεν υπάρχει. Σε ένα απλό μη-κατευθυνόμενο γράφημα με 6 κορυφές το μέγιστο πλήθος ακμών που μπορούμε να έχουμε είναι \(\binom{6}{2} = 15\). Επομένως δεν μπορεί να υπάρχει τέτοιο γράφημα με 16 ακμές.

13

6.¶

α)

∃𝑥∀𝑦¬𝑃(𝑥, 𝑦)
∀𝑥∃𝑦𝑃(𝑥, 𝑦) (πρόκειται για την άρνηση της πρότασης 1).
∀𝑥∀𝑦(𝑥 ≠ 𝑦 → 𝑃(𝑥, 𝑦))

β)

Η πρώτη πρόταση εκφράζει το εξής: “Υπάρχει κάποια κορυφή x τέτοια ώστε κάθε άλλη κορυφή y συνδέεται με την x και δε συνδέεται με καμία άλλη κορυφή.” Πρόκειται δηλαδή για γράφημα “αστέρι”. Άρα ένα τέτοιο γράφημα με 5 κορυφές φαίνεται δίπλα.

[Σχήμα: γράφημα με 5 κορυφές· μία κεντρική κορυφή συνδέεται με τις υπόλοιπες τέσσερις, οι οποίες δεν συνδέονται μεταξύ τους (αστέρι).]

Η δεύτερη πρόταση εκφράζει το εξής: «Κάθε ζευγάρι διαφορετικών κορυφών είτε συνδέεται με ακμή (είναι γειτονικές) ή έχουν κοινό γείτονα.” Πρόκειται δηλαδή για γράφημα στο οποίο η απόσταση μεταξύ δύο οποιονδήποτε κορυφών είναι το πολύ 2. Το πλήρες γράφημα 5 κορυφών είναι μία τέτοια περίπτωση για το οποίο δεν ισχύει η πρώτη πρόταση.

7.¶

α) Ξετυλίγουμε την αναδρομή και έχουμε:

\[p(n) = p\left(\frac{n}{2}\right)+n = \left(p\left(\frac{n}{2^2}\right)+\frac{n}{2}\right)+n = \left(p\left(\frac{n}{2^3}\right)+\frac{n}{2^2}\right)+\frac{n}{2}+n = \ldots = \left(p\left(\frac{n}{2^{\log n}}\right)+\frac{n}{2^{\log n-1}}\right)+\sum_{i=0}^{\log n-2}\frac{n}{2^i} = p(1)+\sum_{i=0}^{\log n-1}\frac{n}{2^i} = 1+\sum_{i=0}^{\log n-1}\frac{n}{2^i} = \sum_{i=0}^{\log n}\frac{n}{2^i}\]

β) Έχουμε:

\[p(n) = \sum_{i=0}^{\log n}\frac{n}{2^i} = n\sum_{i=0}^{\log n}2^{-i} = n\,\frac{1-2^{-\log n-1}}{1-\frac{1}{2}} = n\left(2-2^{-\log n}\right)\]

γ) Εδώ θα εκφράσουμε το 𝑛 ως 2^𝑘 για να κάνουμε επαγωγή στο 𝑘 σύμφωνα με την εκφώνηση. Βάση: για 𝑘= 0, ισχύει αφού 𝑝(2⁰ ) = 𝑝(1) = 1 και 2⁰ (2 −2^{−log 20} ) = 1(2 −1) = 1. Επαγωγική υπόθεση: Έστω ότι ισχύει για 𝑘. Δηλαδή ισχύει ότι: 𝑝(2^𝑘 ) = 2^𝑘 (2 −2^{−log 2𝑘} ) = 2^𝑘 (2 −2^−𝑘 ) Θα δείξουμε ότι ισχύει για 𝑘+ 1. Έχουμε:

\[p(2^{k+1}) = p(2^{k})+2^{k+1}\]

Από την επαγωγική υπόθεση έχουμε:

𝑝(2^𝑘+1 ) = 2^𝑘 (2 −2^−𝑘 ) + 2^𝑘+1 = 2^𝑘+1 (1 −2^−𝑘−1 ) + 2^𝑘+1 = 2^𝑘+1 (2 −2^−(𝑘+1) ) που πράγματι είναι ο κλειστός τύπος για το άθροισμα που θέλουμε να αποδείξουμε.

8.¶

α) i. Έχουμε πρόβλημα διατάξεων 100 αντικειμένων από 8 διαφορετικά αντικείμενα με επανάληψη. Άρα έχουμε 8¹⁰⁰ τρόπους.

ii. Για κάθε συγκεκριμένο μαθητή, η διανομή 10 βιβλίων από τους 8 διαθέσιμους τίτλους αντιστοιχεί σε ένα πρόβλημα συνδυασμών 10 αντικειμένων από 8 διαφορετικά αντικείμενα με επανάληψη. Άρα έχουμε 𝐶(8 + 10 −1,10) = 𝐶(17,10) τρόπους να δώσουμε 10 βιβλία σε κάθε μαθητή. Αφού έχουμε απεριόριστο αριθμό αντιγράφων από κάθε βιβλίο, η διανομή σε κάθε μαθητή είναι ανεξάρτητη, οπότε έχουμε συνολικά 𝐶(17,10)¹⁰⁰ τρόπους.

β) i. Έχουμε επιλογή 3 αντικειμένων από 10 διαφορετικά αντικείμενα, χωρίς επανάληψη, δηλαδή 𝐶(10,3) = 120 τρόπους.

ii. Είναι ίσο με το πλήθος των μη κενών υποσυνόλων των 10 υλικών, δηλαδή 2¹⁰ – 1 = 1023.

iii. Για την επιλογή 3 υλικών η απάντηση προέκυψε από το ερώτημα i. Με τον ίδιο τρόπο για 5 υλικά έχουμε 𝐶(10,5) τρόπους. Άρα, από την αρχή του αθροίσματος, προκύπτει ότι η λύση είναι 𝐶(10,3) + 𝐶(10,5).

14

9.¶

Το αριστερό μέλος είναι ένα πολυωνυμικός συντελεστής και εκφράζει τους τρόπους να τοποθετήσουμε 𝑘 διαφορετικούς τύπους αντικειμένων σε σειρά όπου κάθε αντικείμενο 𝑖 έχει πολλαπλότητα 𝑟𝑖. Το δεξιό μέλος λύνει το ίδιο πρόβλημα μέτρησης ως εξής: Από τις 𝑛 διαφορετικές διαθέσιμες θέσεις επιλέγουμε να τοποθετήσουμε πρώτα τα 𝑟1 αντικείμενα τύπου 1 χωρίς να μας ενδιαφέρει η σειρά (αφού όλα είναι ίδια) και χωρίς επανατοποθέτηση (αφού κάθε θέση παίρνει ένα αντικείμενο). Από τις εναπομείνασες 𝑛−𝑟1 θέσεις θα επιλέξουμε με το ίδιο τρόπο 𝑟2 θέσεις και θα συνεχίσουμε μέχρι να φτάσουμε και στα τελευταία 𝑟𝑘 αντικείμενα για τα οποία έχουμε μόνο 𝑟𝑘 θέσεις. Από την αρχή του γινομένου προκύπτει η ισότητα.

10.¶

α) Έστω 𝑇(𝑛) το πλήθος των αντιγραφέων την ημέρα n . Το πλήθος των αντιγραφέων τη μέρα n είναι ίσο με το πλήθος των αντιγραφέων την ημέρα n -1, συν το τριπλάσιο του πλήθους των αντιγραφέων που κατασκευάσθηκαν την ημέρα n -1.Το πλήθος των αντιγραφέων που κατασκευάσθηκαν την ημέρα n -1 είναι ίσο με το πλήθος των αντιγραφέων την ημέρα n -1 μείον το πλήθος των αντιγραφέων την ημέρα n -2. Άρα:

\[T(0)=1\]

\[T(1)=4\]

\[T(n)=4T(n-1)-3T(n-2), \quad n\geq 2\]

β)

Η χαρακτηριστική εξίσωση είναι x² -4 x +3=0, που δίνει λύσεις x =3 και x =1. Επομένως η λύση θα είναι της μορφής 𝛵(𝑛) = 𝛼3^𝑛 + 𝑏. Αντικαθιστώντας στην αναδρομή και με βάση τις αρχικές συνθήκες έχουμε ότι \(\alpha=\frac{3}{2}\) και \(b=-\frac{1}{2}\). Άρα η λύση της αναδρομικής είναι:

\[T(n)=\frac{1}{2}\cdot 3^{n+1}-\frac{1}{2}\]

Για να καταστραφούν οι αντιγραφείς από το όπλο θα πρέπει ο συνολικός αριθμός τους στον πλανήτη να είναι μικρότερος από 3²⁰ . Άρα θέλουμε να βρούμε το μέγιστο n έτσι ώστε 𝑇(𝑛) ≤3²⁰ :

\[\frac{1}{2}3^{n+1}-\frac{1}{2}\leq 3^{20} \Rightarrow 3^{n+1}-1\leq 2\cdot 3^{20} \Rightarrow n+1\leq \log_3\left(2\cdot 3^{20}+1\right) \Rightarrow n\leq \log_3\left(2\cdot 3^{20}+1\right)-1\]

Από όπου προκύπτει ότι οι Άσγκαρντ έχουν το πολύ 19 ημέρες.

15

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

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