Διακριτά Μαθηματικά — Ιούνιος 2013 (πτυχιακή)¶
Μεταγραφή από το αρχείο exams.pdf (κείμενο PDF).
exams.pdf¶
ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΩΝ ΠΟΛΥΤΕΧΝΙΚΗ ΣΧΟΛΗ ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ ΤΟΜΕΑΣ ΕΦΑΡΜΟΓΩΝ & ΘΕΜΕΛΙΩΣΕΩΝ ΤΗΣ ΕΠΙΣΤΗΜΗΣ ΤΩΝ ΥΠΟΛΟΓΙΣΤΩΝ¶
ΠΤΥΧΙΑΚΗ ΕΞΕΤΑΣΗ ΙΟΥΝΙΟΥ 2013¶
ΔΙΑΚΡΙΤΑ ΜΑΘΗΜΑΤΙΚΑ Ι ΚΑΘΗΓΗΤΗΣ Χ. Ι. ΜΠΟΥΡΑΣ ΤΕΤΑΡΤΗ 26 ΙΟΥΝΙΟΥ 2013¶
ΘΕΜΑΤΑ¶
- Να υπολογίσετε με πόσους τρόπους μπορούμε να μοιράσουμε 4 ίδια πορτοκάλια και 6 διαφορετικά μήλα σε 5 διαφορετικά κουτιά. Επίσης, να βρείτε σε ποιο ποσοστό αυτών των τρόπων τοποθετούνται 2 ακριβώς φρούτα σε κάθε κουτί.
ΥΠΟΔΕΙΞΗ: Για την επίλυση του ερωτήματος να χρησιμοποιήσετε ΣΥΝΔΥΑΣΤΙΚΑ ΕΠΙΧΕΙΡΗΜΑΤΑ.
(25 μονάδες)
- Να υπολογίσετε με πόσους τρόπους μπορούμε να εκτυπώσουμε 25 διαφορετικά αρχεία σε 3 διαφορετικούς εκτυπωτές με τον περιορισμό ότι κάθε εκτυπωτής πρέπει να εκτυπώσει τουλάχιστον ένα αρχείο.
ΥΠΟΔΕΙΞΗ: Για την επίλυση του ερωτήματος να χρησιμοποιήσετε ΕΚΘΕΤΙΚΕΣ ΓΕΝΝΗΤΡΙΕΣ ΣΥΝΑΡΤΗΣΕΙΣ.
(25 μονάδες)
- Να υπολογίσετε τον αριθμό των λέξεων μήκους \(n\) από το αλφάβητο \(\{0, 1, 2\}\), στις οποίες γειτονικά ψηφία διαφέρουν ΤΟ ΠΟΛΥ κατά 1.
ΥΠΟΔΕΙΞΗ: Για την επίλυση του ερωτήματος να χρησιμοποιήσετε ΑΠΟΚΛΕΙΣΤΙΚΑ ΣΧΕΣΕΙΣ ΑΝΑΔΡΟΜΗΣ.
(25 μονάδες)
- Να υπολογίσετε τον αριθμό των τρόπων με τους οποίους μπορούν να χρωματιστούν οι όψεις ενός κύβου με 3 χρώματα.
ΥΠΟΔΕΙΞΗ: Για την επίλυση του ερωτήματος να χρησιμοποιήσετε το ΘΕΩΡΗΜΑ P´olya.
(25 μονάδες)
ΚΑΛΗ ΕΠΙΤΥΧΙΑ & ΚΑΛΟ ΚΑΛΟΚΑΙΡΙ¶
Οι ενδεικτικές λύσεις και τα θέματα θα αναρτηθούν στο δικτυακό τόπο του μαθήματος, μετά το τέλος της εξέτασης.
Λύσεις (🟢 official)
Κατάσταση: 🟢 official Πηγή: ενδεικτικές λύσεις (αρχείο «solutions.pdf» της συλλογής)
Λύσεις — Διακριτά Μαθηματικά — Ιούνιος 2013 (πτυχιακή)¶
solutions.pdf¶
- Υπάρχουν κατά τα γνωστά \(\binom{4+5-1}{4} = 70\) τρόποι για να τοποθετηθούν τέσσερα όμοια αντικείμενα σε πέντε διακεκριμένα κουτιά και \(5^6 = 15625\) τρόποι για να τοποθετηθούν έξι διαφορετικά μήλα σε πέντε διαφορετικά κουτιά. Επειδή οι τοποθετήσεις αυτές είναι ανεξάρτητες, σύμφωνα με τον κανόνα του γινομένου, υπάρχουν συνολικά \(70 \cdot 15625 = 1093750\) τρόποι για να μοιραστούν τα τέσσερα όμοια και τα έξι διαφορετικά φρούτα στα πέντε διακεκριμένα κουτιά.
Για να απαντήσουμε στο δεύτερο ερώτημα σκεφτόμαστε ως εξής: Ξεκινούμε τη διαδικασία της μοιρασιάς από τα τέσσερα όμοια πορτοκάλια και διακρίνουμε τρεις περιπτώσεις:
Έστω ότι τοποθετούνται από δύο πορτοκάλια σε δύο από τα πέντε κουτιά και κανένα πορτοκάλι στα υπόλοιπα κουτιά. Τα δύο κουτιά μπορεί να επιλεγούν κατά \(\binom{5}{2} = 10\) τρόπους και τα έξι διαφορετικά μήλα μπορούν να μοιραστούν στα υπόλοιπα τρία κουτιά κατά \(\frac{6!}{2!\,2!\,2!} = 90\) τρόπους. Έτσι, σύμφωνα με τον κανόνα του γινομένου, σ' αυτήν την κατηγορία υπάρχουν \(10 \cdot 90 = 900\) τρόποι τοποθέτησης.
Έστω ότι τοποθετούνται δύο όμοια πορτοκάλια σ' ένα από τα κουτιά, από ένα πορτοκάλι σε δύο από τα υπόλοιπα τέσσερα κουτιά και τα άλλα δύο κουτιά μένουν χωρίς πορτοκάλι. Το κουτί με τα δύο πορτοκάλια μπορεί να επιλεγεί κατά 5 τρόπους, τα δύο κουτιά που θα πάρουν από ένα πορτοκάλι μπορεί να επιλεγούν κατά \(\binom{4}{2} = 6\) τρόπους και τέλος τα έξι διαφορετικά μήλα μπορούν να μοιραστούν στις θέσεις, που περισσεύουν κατά \(\frac{6!}{2!\,2!} = 180\) τρόπους. Συνεπώς, σύμφωνα με τον κανόνα του γινομένου, η κατηγορία αυτή περιλαμβάνει \(5 \cdot 6 \cdot 180 = 5400\) τρόπους τοποθέτησης.
Έστω, τέλος, ότι τοποθετείται από ένα πορτοκάλι σε καθένα από τέσσερα διακεκριμένα κουτιά. Αυτό μπορεί να γίνει με \(\binom{5}{4} = 5\) τρόπους και τα έξι διαφορετικά μήλα θα μοιραστούν στις θέσεις που περισσεύουν κατά \(\frac{6!}{2!} = 360\) τρόπους. Έτσι η κατηγορία αυτή περιλαμβάνει \(5 \cdot 360 = 1800\) τρόπους τοποθέτησης.
Από τα παραπάνω και αφού έχουμε εξαντλήσει κάθε δυνατό τρόπο τοποθέτησης δύο φρούτων σε κάθε διακεκριμένο κουτί γίνεται φανερό ότι έχουμε συνολικά \(900 + 5400 + 1800 = 8100\) τρόπους τοποθέτησης. Το κλάσμα των τρόπων αυτών ως προς το συνολικό αριθμό των τρόπων που υπολογίστηκε παραπάνω είναι: \(\frac{8100}{1093750} = 0.0074\).
- Ουσιαστικά ψάχνουμε το πλήθος των τρόπων με τους οποίους μπορούμε να διατάξουμε 25 αντικείμενα επιλεγμένα από 3 αντικείμενα όταν επιτρέπονται επαναλήψεις των 3 αντικειμένων.
Για τον 1ο εκτυπωτή - αφού πρέπει οπωσδήποτε να λάβει ένα τουλάχιστον αρχείο - η γεννήτρια συνάρτηση είναι: $\(z + \frac{z^2}{2!} + \frac{z^3}{3!} + \ldots + \frac{z^{25}}{25!} = e^z - 1.\)$
Όμοια για το 2ο και 3ο εκτυπωτή. Η τελική γεννήτρια συνάρτηση για όλους τους εκτυπωτές είναι \((e^z - 1)^3\) και το πλήθος των ζητούμενων τρόπων δίνεται από το συντελεστή του \(\frac{z^{25}}{25!}\) στο \((e^z - 1)^3\).
Κάνοντας πράξεις έχουμε: $\((e^z - 1)^3 = e^{3z} - 3e^{2z} + 3e^z - 1 = \sum_{r=0}^{\infty} 3^r \frac{z^r}{r!} - 3\sum_{r=0}^{\infty} 2^r \frac{z^r}{r!} + 3\sum_{r=0}^{\infty} \frac{z^r}{r!} - 1 = \sum_{r=0}^{\infty} (3^r - 3\cdot 2^r + 3)\frac{z^r}{r!} - 1\)$
Επομένως, ο συντελεστής του \(\frac{z^{25}}{25!}\) είναι: \(3^{25} - 3 \cdot 2^{25} + 3\).
- Ας είναι:
- \(a_n\) - ο αριθμός τέτοιων λέξεων που τελειώνουν σε 0.
- \(b_n\) - ο αριθμός τέτοιων λέξεων που τελειώνουν σε 1.
- \(c_n\) - ο αριθμός τέτοιων λέξεων που τελειώνουν σε 2.
- \(x_n = a_n + b_n + c_n\)
Αλλάζοντας τα 0 και 2 παίρνουμε μία αντιστοιχία 1-σε-1 μεταξύ του συνόλου των λέξεων (της ζητούμενης μορφής) που τελειώνουν σε 0 και του συνόλου των λέξεων (της ζητούμενης μορφής) που τελειώνουν σε 2. Επομένως έχουμε: $\(a_n = c_n \quad \text{και} \quad x_n = 2a_n + b_n\)$ με $\(a_1 = b_1 = 1 \quad \text{και} \quad a_{n+1} = a_n + b_n, \qquad b_{n+1} = a_n + b_n + c_n = 2a_n + b_n = x_n\)$
Επομένως: $\(b_{n+2} = 2a_{n+1} + b_{n+1} = 2(a_n + b_n) + b_{n+1} = (2a_n + b_n) + b_n + b_{n+1} = b_{n+1} + b_n + b_{n+1} = 2b_{n+1} + b_n\)$
Άρα έχουμε τη σχέση αναδρομής: $\(b_{n+2} - 2b_{n+1} - b_n = 0\)$
Η χαρακτηριστική εξίσωση είναι: \(\lambda^2 - 2\lambda - 1 = 0\) και \(\lambda_{1,2} = 1 \pm \sqrt{2}\).
Επομένως: \(b_n = A(1 + \sqrt{2})^n + B(1 - \sqrt{2})^n\), με \(A = B = 1/2\), οπότε $\(b_n = \frac{1}{2}\left((1 + \sqrt{2})^n + (1 - \sqrt{2})^n\right)\)$
Επομένως ο αριθμός των λέξεων της κατάλληλης μορφής είναι: $\(x_n = b_{n+1} = \frac{1}{2}\left((1 + \sqrt{2})^{n+1} + (1 - \sqrt{2})^{n+1}\right)\)$
- Έστω:
- \(D = \{a, b, c, d, e, f\}\), οι πλευρές
- \(R = \{c_1, c_2, c_3\}\), τα χρώματα με \(w(c_i) = i\), \(1 \le i \le 3\)
Αριθμούμε τις όψεις του κύβου ως εξής: 1 την πάνω, 2 την κάτω, 3,4,5,6 τις πλαϊνές κατά τη φορά του ρολογιού. Οι συμμετρίες στον κύβο είναι οι εξής: - Να αφήσω τον κύβο όπως είναι. \((1)(2)(3)(4)(5)(6)\). Με κυκλική αναπαράσταση: \(x_1^6\) - Να κάνω περιστροφές \(180^o\) γύρω από τον άξονα που ενώνει μέσα απέναντι όψεων. \((1)(2)(35)(46)\). Υπάρχουν 3 περιπτώσεις ανάλογα με το αν κοιτάω τον κατακόρυφο, τον οριζόντιο ή τον άξονα βάθους. Με κυκλική αναπαράσταση: \(3x_1^2x_2^2\) - Να κάνω περιστροφές \(90^o\) και \(-90^o\) γύρω από τον άξονα που ενώνει μέσα απέναντι όψεων. \((1)(2)(3456)\). Υπάρχουν 3 περιπτώσεις ανάλογα με το αν κοιτάω τον κατακόρυφο, τον οριζόντιο ή τον άξονα βάθους. Συνολικά 6. Με κυκλική αναπαράσταση: \(6x_1^2x_4^1\) - Να κάνω περιστροφές \(180^o\) γύρω από άξονες που ενώνουν μέσα απέναντι ακμών. \((15)(23)(46)\). Υπάρχουν 6 περιπτώσεις. Με κυκλική αναπαράσταση: \(6x_2^3\) - Να κάνω περιστροφές \(120^o\) και \(-120^o\) γύρω από άξονες που ενώνουν απέναντι κορυφές. \((154)(236)\). Υπάρχουν 8 περιπτώσεις. Με κυκλική αναπαράσταση: \(8x_3^2\)
Άρα συνολικά \(|G| = 24\) και $\(P_G = \frac{x_1^6 + 3x_1^2x_2^2 + 6x_1^2x_4^1 + 6x_2^3 + 8x_3^2}{24}\)$
Έχουμε 3 χρώματα: \(c_1 + c_2 + c_3\), οπότε: $\(P_G = \frac{1}{24}\Big[(c_1+c_2+c_3)^6 + 3(c_1+c_2+c_3)^2(c_1^2+c_2^2+c_3^2)^2 + 6(c_1+c_2+c_3)^2(c_1^4+c_2^4+c_3^4)^1 + 6(c_1^2+c_2^2+c_3^2)^3 + 8(c_1^3+c_2^3+c_3^3)^2\Big]\)$
Θέτοντας \(w(c_1) = w(c_2) = w(c_3) = 1\) έχουμε: $\(P_G = \frac{3^6 + 3\cdot 3^2\cdot 3^2 + 6\cdot 3^2\cdot 3 + 6\cdot 3^3 + 8\cdot 3^2}{24} = \frac{729 + 243 + 162 + 162 + 72}{24} = \frac{1368}{24} = 57\)$