Διακριτά Μαθηματικά — Σεπτέμβριος 2014 (επαναληπτική)¶

Μεταγραφή από το αρχείο examsSept14.pdf (κείμενο PDF).

examsSept14.pdf¶

ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΩΝ ΠΟΛΥΤΕΧΝΙΚΗ ΣΧΟΛΗ ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ ΤΟΜΕΑΣ ΕΦΑΡΜΟΓΩΝ & ΘΕΜΕΛΙΩΣΕΩΝ ΤΗΣ ΕΠΙΣΤΗΜΗΣ ΤΩΝ ΥΠΟΛΟΓΙΣΤΩΝ¶

ΕΠΑΝΑΛΗΠΤΙΚΗ ΕΞΕΤΑΣΗ ΣΕΠΤΕΜΒΡΙΟΥ 2014¶

ΔΙΑΚΡΙΤΑ ΜΑΘΗΜΑΤΙΚΑ Ι ΚΑΘΗΓΗΤΗΣ Χ. Ι. ΜΠΟΥΡΑΣ ΣΑΒΒΑΤΟ 6 ΣΕΠΤΕΜΒΡΙΟΥ 2014¶

ΘΕΜΑΤΑ¶

Να υπολογίσετε με πόσους τρόπους μπορούμε να μοιράσουμε 4 ίδια πορτοκάλια και 6 διαφορετικά μήλα σε 5 διαφορετικά κουτιά. Επίσης, να βρείτε σε ποιο ποσοστό αυτών των τρόπων τοποθετούνται 2 ακριβώς φρούτα σε κάθε κουτί.

ΥΠΟΔΕΙΞΗ: Για την επίλυση του ερωτήματος να χρησιμοποιήσετε ΣΥΝΔΥΑΣΤΙΚΑ ΕΠΙΧΕΙΡΗΜΑΤΑ.

(20 μονάδες)

΄Εστω $a_r$ ο αριθμός των τρόπων, με τους οποίους μπορούμε να επιλέξουμε (με επαναλήψεις) $r$ γράμματα από το αλφάβητο $\{0, 1, 2\}$, με τον περιορισμό ότι το γράμμα 0 θα επιλεγεί ζυγές φορές. Να βρείτε μία σχέση αναδρομής για το πρόβλημα και να τη λύσετε.

ΥΠΟΔΕΙΞΗ: Για την επίλυση του ερωτήματος να χρησιμοποιήσετε ΣΧΕΣΕΙΣ ΑΝΑΔΡΟΜΗΣ.

(30 μονάδες)

Να υπολογίσετε τον αριθμό των σκακιέρων με διαστάσεις $2 \times 4$, που αποτελούνται από άσπρα και κόκκινα τετράγωνα, με τον περιορισμό ότι τα κόκκινα τετράγωνα θα είναι 3 και τα άσπρα 5. (Θεωρούμε ότι οι σκακιέρες αναποδογυρίζονται).

ΥΠΟΔΕΙΞΗ: Για την επίλυση του ερωτήματος να χρησιμοποιήσετε το ΘΕΩΡΗΜΑ P´olya.

(30 μονάδες)

Να υπολογίσετε πόσες λέξεις $n$ ψηφίων από το αλφάβητο $\{0, 1, 2\}$ υπάρχουν, με ένα τουλάχιστον 0, ένα τουλάχιστον 1 και ένα τουλάχιστον 2. ΥΠΟΔΕΙΞΗ: Για την επίλυση του ερωτήματος να χρησιμοποιήσετε την ΑΡΧΗ ΕΓΚΛΕΙΣΜΟΥ-ΑΠΟΚΛΕΙΣΜΟΥ.

(20 μονάδες)

ΚΑΛΗ ΕΠΙΤΥΧΙΑ¶

Οι ενδεικτικές λύσεις και τα θέματα θα αναρτηθούν στο δικτυακό τόπο του μαθήματος, μετά το τέλος της εξέτασης.

Ενημερωθείτε για τα θέματα των Διπλωματικών Εργασιών για το 2014 − 15 στο http://ru6.cti.gr/ru6/bouras?language=el

Λύσεις (🟢 official)

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

Λύσεις — Διακριτά Μαθηματικά — Σεπτέμβριος 2014 (επαναληπτική)¶

solutionsSept14.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$.

Έστω $a_r$ ο ζητούμενος αριθμός. Ως γνωστόν το συνολικό πλήθος των τρόπων επιλογής $r$ γραμμάτων από το αλφάβητο $\{0, 1, 2\}$, με επαναλήψεις, είναι, $$\binom{r+2}{2} = \frac{(r+1)(r+2)}{2}.$$

Εάν πάρουμε μία τυχαία επιλογή $r$ γραμμάτων, τότε αυτή μπορεί να προκύψει κατά μοναδικό τρόπο είτε από μία έγκυρη επιλογή $r - 1$ γραμμάτων με την προσθήκη ενός μηδενικού, εάν η τυχαία επιλογή είναι άκυρη, είτε από μία έγκυρη επιλογή $r$ γραμμάτων χωρίς αλλαγή, εάν η τυχαία επιλογή είναι έγκυρη. Έτσι έχουμε τη σχέση αναδρομής $$a_{r-1} + a_r = \frac{(r+1)(r+2)}{2} \quad \text{ή} \quad a_n + a_{n-1} = \frac{(n+1)(n+2)}{2}$$

Αυτή είναι μη ομογενής γραμμική αναδρομική εξίσωση με αντίστοιχη ομογενή, $$a_n + a_{n-1} = 0$$ που έχει χαρακτηριστική εξίσωση $x + 1 = 0$ και απλή ρίζα $x = -1$. Άρα η ομογενής λύσις της γραμμικής είναι $a_n^{(h)} = A(-1)^n$. Για να βρούμε την ειδική λύση δοκιμάζουμε την $a_n^{(p)} = Bn^2 + Cn + D$. Είναι, $$Bn^2 + Cn + D + Bn^2 - 2Bn + B + Cn - C + D = \frac{n^2}{2} + \frac{3n}{2} + \frac{2}{2} \implies \begin{cases} 2B = \frac{1}{2} \ -2B + 2C = \frac{3}{2} \ B - C + 2D = 1 \end{cases} \implies \begin{cases} B = \frac{1}{4} \ C = 1 \ D = \frac{7}{8} \end{cases}$$

Άρα $a_n^{(p)} = \frac{1}{4}n^2 + n + \frac{7}{8}$, επομένως, $$a_n = A(-1)^n + \frac{1}{4}n^2 + n + \frac{7}{8} \stackrel{n=1}{\implies} \frac{1}{4} + 1 + \frac{7}{8} - A = 2 \implies A = \frac{1}{8}.$$

Συνεπώς, $$a_n = \frac{2n^2 + 8n + 7 + (-1)^n}{8}, \quad \forall n \in \mathbb{N}^*$$

Έστω $G$ η ομάδα μεταθέσεων, που αντιστοιχεί σε όλες τις δυνατές περιστροφές της σκακιέρας. Έχουμε $|G| = 4$, γιατί στην $G$ ανήκουν,
η ταυτοτική μετάθεση με κυκλική αναπαράσταση $x_1^8$
η μετάθεση, που αντιστοιχεί σε περιστροφή της σκακιέρας γύρω από άξονα, που είναι κάθετος στη σκακιέρα και διέρχεται από το κέντρο της, κατά $180^o$, με κυκλική αναπαράσταση $x_2^4$
η μετάθεση, που αντιστοιχεί σε περιστροφή κατά $180^o$ γύρω από τον οριζόντιο άξονα, που κόβει τις δύο γραμμές της σκακιέρας, με αναπαράσταση $x_2^4$ και
η μετάθεση, που αντιστοιχεί σε περιστροφή γύρω από τον κάθετο άξονα, που κόβει στη μέση τις 4 στήλες της σκακιέρας, κατά $180^o$, με αναπαράσταση $x_2^4$

[Σχήμα: σκακιέρα 2×4 με τους τρεις άξονες περιστροφής (1), (2), (3)]

Έτσι ο δείκτης κύκλων της $G$ είναι, $$\frac{1}{4}\left(x_1^8 + 3x_2^4\right)$$ και για τον αριθμό εύρεσης κλάσεων ισοδυναμίας έχουμε, $$\frac{1}{4}\left[(x+y)^8 + 3(x^2+y^2)^4\right] = \frac{1}{4}\left[\sum_{k=0}^{8}\binom{8}{k}x^k y^{8-k} + 3\sum_{k=0}^{4}\binom{4}{k}x^{2k}y^{8-2k}\right]$$ θέλουμε το συντελεστή του $x^3y^5$, οπότε έχουμε, $$\frac{1}{4}\left[\binom{8}{3} + 3 \cdot 0\right]x^3y^5 = 14x^3y^5$$

Έστω $S$ το σύνολο των λέξεων $n$ ψηφίων από το αλφάβητο $\{0, 1, 2\}$ με $N = |S| = 3^n$. Έστω επίσης $c_i$ με $0 \le i \le 2$ το γεγονός μία λέξη $n$ ψηφίων του $S$ να μην περιέχει το ψηφίο $i$. Τότε ζητάμε το $N(\overline{c_0}\,\overline{c_1}\,\overline{c_2})$ και έχουμε, $$N(\overline{c_0}\,\overline{c_1}\,\overline{c_2}) = N - N(c_0) - N(c_1) - N(c_2) + N(c_0c_1) + N(c_0c_2) + N(c_1c_2) - N(c_0c_1c_2) =$$ $$= 3^n - 2^n - 2^n - 2^n + 1 + 1 + 1 - 0 = 3^n - 3 \cdot 2^n + 3 = 3\left(3^{n-1} - 2^n + 1\right)$$

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

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