Διακριτά Μαθηματικά — Ιούλιος 2014 (πτυχιακή)¶
Μεταγραφή από το αρχείο examsJul14.pdf (κείμενο PDF).
examsJul14.pdf¶
ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΩΝ ΠΟΛΥΤΕΧΝΙΚΗ ΣΧΟΛΗ ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ ΤΟΜΕΑΣ ΕΦΑΡΜΟΓΩΝ & ΘΕΜΕΛΙΩΣΕΩΝ ΤΗΣ ΕΠΙΣΤΗΜΗΣ ΤΩΝ ΥΠΟΛΟΓΙΣΤΩΝ¶
ΠΤΥΧΙΑΚΗ ΕΞΕΤΑΣΗ ΙΟΥΝΙΟΥ 2014¶
ΔΙΑΚΡΙΤΑ ΜΑΘΗΜΑΤΙΚΑ Ι ΚΑΘΗΓΗΤΗΣ Χ. Ι. ΜΠΟΥΡΑΣ ΠΕΜΠΤΗ 3 ΙΟΥΛΙΟΥ 2014
ΘΕΜΑΤΑ¶
- Με πόσους τρόπους \(r\) ίδιες μπάλες μπορούν να τοποθετηθούν σε \(n\) διαφορετικά κουτιά έτσι ώστε κάθε κουτί να περιέχει τουλάχιστον 9 μπάλες;
ΥΠΟΔΕΙΞΗ: Για την επίλυση του ερωτήματος να χρησιμοποιήσετε ΣΥΝΔΥΑΣΤΙΚΑ ΕΠΙΧΕΙΡΗΜΑΤΑ.
(30 μονάδες)
- Με πόσους τρόπους μπορούμε να εκτυπώσουμε 25 διαφορετικά αρχεία σε 3 διαφορετικούς εκτυπωτές με τον περιορισμό ότι κάθε εκτυπωτής πρέπει να εκτυπώσει τουλάχιστον ένα αρχείο;
ΥΠΟΔΕΙΞΗ: Για την επίλυση του ερωτήματος να χρησιμοποιήσετε ΓΕΝΝΗΤΡΙΕΣ ΣΥΝΑΡΤΗΣΕΙΣ.
(30 μονάδες)
- Τα τετράγωνα μιας \(4 \times 4\) σκακιέρας θα χρωματιστούν με μαύρη και άσπρη μπογιά. Πόσα διαφορετικά σχήματα πρέπει να κάνουμε, για να δημιουργήσουμε όλους τους μαυρόασπρους σχηματισμούς;
ΥΠΟΔΕΙΞΗ: Για την επίλυση του ερωτήματος να χρησιμοποιήσετε το ΘΕΩΡΗΜΑ P´olya ΚΑΙ να θεωρήσετε πως η σκακιέρα περιστρέφεται ΜΟΝΟ γύρω από τον άξονα που περνάει από το κέντρο της.
(40 μονάδες)
ΚΑΛΗ ΕΠΙΤΥΧΙΑ¶
Οι ενδεικτικές λύσεις και τα θέματα θα αναρτηθούν στο δικτυακό τόπο του μαθήματος, μετά το τέλος της εξέτασης.
Λύσεις (🟢 official)
Κατάσταση: 🟢 official Πηγή: ενδεικτικές λύσεις (αρχείο «solutionsJul14.pdf» της συλλογής)
Λύσεις — Διακριτά Μαθηματικά — Ιούλιος 2014 (πτυχιακή)¶
solutionsJul14.pdf¶
- Αφού θέλουμε 'τουλάχιστον 9 μπάλες σε κάθε κουτί' δεσμεύουμε \(9n\) μπάλες.
Συνεπώς, μένουν \(r - 9n\) ίδιες μπάλες τις οποίες μπορούμε να τοποθετήσουμε στα \(n\) διαφορετικά κουτιά με όλους τους δυνατούς τρόπους \(\Rightarrow\) $\(\frac{(r-9n+n-1)!}{(n-1)!\,(r-9n)!} = \binom{r-9n+n-1}{r-9n}\)$
- Ουσιαστικά ψάχνουμε το πλήθος των τρόπων με τους οποίους μπορούμε να διατάξουμε 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\).
- Έστω \(D = \{\alpha_1, \alpha_2, \ldots, \alpha_{16}\}\) το σύνολο των 16 τετραγώνων της \(4 \times 4\) σκακιέρας και \(G = \{\pi_1, \pi_2, \pi_3, \pi_4\}\) η ομάδα μεταθέσεων επί του \(D\) με \(\pi_1\) την ταυτοτική μετάθεση, με κυκλική αναπαράσταση \(x_1^{16}\), \(\pi_2\) τη μετάθεση, που αντιστοιχεί σε αριστερόστροφη περιστροφή της σκακιέρας κατά \(90^o\) γύρω από άξονα, κάθετο στο κέντρο της, με κυκλική αναπαράσταση \(x_4^4\), και \(\pi_3\), \(\pi_4\) μεταθέσεις, που αντιστοιχούν σε περιστροφές κατά \(180^o\) και \(270^o\), αντίστοιχα, γύρω από τον ίδιο άξονα, με κυκλικές αναπαραστάσεις \(x_2^8\), \(x_4^4\), αντίστοιχα.
Τότε ο δείκτης κύκλων της \(G\) είναι, $\(P_G = \frac{1}{4}\left(x_1^{16} + x_2^8 + 2x_4^4\right)\)$
Έστω \(R = \{x, y\}\) το σύνολο των 2 χρωμάτων, μαύρο και άσπρο. Έστω επίσης \(w(x) = x\) και \(w(y) = y\). Τότε ο αριθμός εύρεσης σχηματισμών γίνεται, $\(\frac{1}{4}\left[(x + y)^{16} + (x^2 + y^2)^8 + 2(x^4 + y^4)^4\right]\)$
Θέτοντας \(x = y = 1\) παίρνουμε για το ζητούμενο αριθμό σχημάτων, $\(\frac{1}{4}\left(2^{16} + 2^8 + 2 \cdot 2^4\right) = 16456\)$