Διακριτά Μαθηματικά — Σεπτέμβριος 2018¶

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

examsSep2018.pdf¶

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

ΕΞΕΤΑΣΤΙΚΗ ΣΕΠΤΕΜΒΡΙΟΥ 2018¶

ΔΙΑΚΡΙΤΑ ΜΑΘΗΜΑΤΙΚΑ ΚΑΘΗΓΗΤΗΣ Χ. Ι. ΜΠΟΥΡΑΣ ΔΕΥΤΕΡΑ 27 ΑΥΓΟΥΣΤΟΥ 2018

ΘΕΜΑΤΑ

Να δείξετε πως για κάθε φυσικό αριθμό $n$ ισχύει: $\sum_{i=0}^{n} \binom{n}{i}^2 = \binom{2n}{n}$

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

(2.5 μονάδες)

Να υπολογίσετε την ακολουθία με γεννήτρια συνάρτηση $\frac{1 + 2x - x^2 - x^3}{1 + x - x^2 - x^3}$

(2.5 μονάδες)

΄Εστω ότι στρίβουμε ένα νόμισμα $n$ φορές. Υπάρχουν προφανώς $2^n$ ακολουθίες πιθανών αποτελεσμάτων. Χρησιμοποιώντας ΣΧΕΣΕΙΣ ΑΝΑΔΡΟΜΗΣ, να υπολογίσετε ποιος είναι ο αριθμός των ακολουθιών των αποτελεσμάτων, στις οποίες ποτέ δεν εμφανίζεται ‘Κεφάλι’ (Κ) σε διαδοχικά στριψίματα;

(2.5 μονάδες)

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

(2.5 μονάδες)

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

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

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

Λύσεις (🟢 official)

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

Λύσεις — Διακριτά Μαθηματικά — Σεπτέμβριος 2018¶

solutionsSep2018.pdf¶

Επειδή $\binom{n}{i} = \binom{n}{n-i}$, είναι $\sum_{i=0}^{n}\binom{n}{i}^2 = \sum_{i=0}^{n}\binom{n}{i}\binom{n}{n-i}$.

$\binom{2n}{n}$ σημαίνει να διαλέξουμε $n$ από $2n$ αντικείμενα. Αυτό μπορεί να γίνει ως εξής: Χωρίζουμε τα $2n$ αντικείμενα σε 2 ομάδες ώστε κάθε μία να έχει $n$ αντικείμενα.

Για $i = 0, 1, 2, 3, \ldots, n$, διαλέγουμε $i$ αντικείμενα από την πρώτη ομάδα με $\binom{n}{i}$ τρόπους και $n - i$ αντικείμενα από τη δεύτερη ομάδα με $\binom{n}{n-i}$ τρόπους.

Για $i = 0, 1, 2, 3, \ldots, n$, υπάρχουν $\binom{n}{i}\binom{n}{n-i}$ τρόποι επιλογής.

Τα ενδεχόμενα για διαφορετικές τιμές του $i$ είναι αμοιβαία αποκλειόμενα, οπότε με κανόνα αθροίσματος έχουμε: $$\binom{2n}{n} = \sum_{i=0}^{n}\binom{n}{i}\binom{n}{n-i}$$

$A(x) = \dfrac{1+x-x^2-x^3}{1+x-x^2-x^3} + \dfrac{x}{1+x-x^2-x^3} = 1 + \dfrac{x}{1+x-x^2(1+x)} = 1 + \dfrac{x}{(1+x)(1-x^2)} = 1 + \dfrac{x}{(1+x)^2(1-x)}$

Αναλύουμε το κλάσμα $\dfrac{x}{(1+x)^2(1-x)}$ σε άθροισμα απλών κλασμάτων: $$\frac{x}{(1+x)^2(1-x)} = \frac{A}{1-x} + \frac{B}{1+x} + \frac{C}{(1+x)^2} \iff x = A(1+x)^2 + B(1-x)(1+x) + C(1-x) \quad (1)$$

Για $x = 1$ στην (1): $1 = A \cdot 2^2 \Rightarrow A = \frac{1}{4}$. Αντικαθιστούμε στην (1): $x - \frac{1}{4}(1+x)^2 = B(1-x)(1+x) + C(1-x) \quad (2)$
Για $x = -1$ στην (2): $-1 = C \cdot 2 \Rightarrow C = -\frac{1}{2}$. Αντικαθιστούμε στην (2): $x - \frac{1}{4}(1+x)^2 + \frac{1}{2}(1-x) = B(1-x^2)$. Παραγωγίζουμε και τα δύο μέλη $\Rightarrow$ $1 - \frac{2}{4}(1+x) - \frac{1}{2} = -2Bx \quad (3)$
Για $x = 1$ στην (3): $1 - \frac{1}{2}\cdot 2 - \frac{1}{2} = -2B \Rightarrow -\frac{1}{2} = -2B \Rightarrow B = \frac{1}{4}$

Έχουμε: $A(x) = 1 + \frac{1}{4}(1-x)^{-1} + \frac{1}{4}(1+x)^{-1} - \frac{1}{2}(1+x)^{-2} =$ $$1 + \frac{1}{4}\sum_{k=0}^{\infty}\binom{-1}{k}(-1)^k x^k + \frac{1}{4}\sum_{k=0}^{\infty}\binom{-1}{k}x^k - \frac{1}{2}\sum_{k=0}^{\infty}\binom{-2}{k}x^k =$$ $$1 + \frac{1}{4}\sum_{k=0}^{\infty}x^k + \frac{1}{4}\sum_{k=0}^{\infty}(-1)^k x^k - \frac{1}{2}\sum_{k=0}^{\infty}(-1)^k(k+1)x^k =$$ $$1 + \sum_{k=0}^{\infty}\left[\frac{1}{4} + \frac{1}{4}(-1)^k - \frac{1}{2}(-1)^k(k+1)\right]x^k = 1 + x - x^2 + 2x^3 - 2x^4 + 3x^5 - 3x^6 + \ldots$$

Έστω μία ακολουθία μήκους $n$ από Κ και Γ που δίνει ένα πιθανό αποτέλεσμα. Ας πάρουμε την τελευταία θέση στην ακολουθία και ας τη σημειώσουμε σαν 'ξεχωριστή θέση'. Τότε αν $a_n$ είναι ο αριθμός των ακολουθιών μήκους $n$, στις οποίες δεν έχουμε δύο διαδοχικά Κ, θα έχουμε την εξής σχέση: Εάν στη θέση $n$, που ξεχωρίσαμε, έχουμε Γ, τότε θεωρούμε τις θέσεις από 1 εώς $n - 1$ σαν μία νέα ακολουθία μήκους $n - 1$, στην οποία πάλι δεν πρέπει να έχουμε δύο Κ γειτονικά, ενώ αν στη θέση $n$ έχουμε Κ, τότε επειδή στη θέση $n - 1$ πρέπει υποχρεωτικά να έχουμε Γ, παίρνουμε σαν νέα ακολουθία τις θέσεις από 1 έως $n - 2$. Σ' αυτές η ακολουθία μήκους $n - 2$ δεν πρέπει να έχει δύο διαδοχικά Κ. Έτσι έχουμε την ομογενή αναδρομική σχέση $a_n = a_{n-1} + a_{n-2}$, με αρχικές συνθήκες $a_1 = 2$ και $a_2 = 3$.

Αυτή έχει χαρακτηριστική εξίσωση, $$x^2 - x - 1 = 0 \implies \left(x_1 = \frac{1}{2} + \frac{\sqrt{5}}{2} \vee x_2 = \frac{1}{2} - \frac{\sqrt{5}}{2}\right)$$

Έτσι, $$a_n = A\left(\frac{1 + \sqrt{5}}{2}\right)^n + B\left(\frac{1 - \sqrt{5}}{2}\right)^n \stackrel{n=1,2}{\implies} \begin{cases} \frac{1+\sqrt{5}}{2}A + \frac{1-\sqrt{5}}{2}B = 2 \ \frac{3+\sqrt{5}}{2}A + \frac{3-\sqrt{5}}{2}B = 3 \end{cases} \implies \begin{cases} A = \frac{5+3\sqrt{5}}{10} \ B = \frac{5-3\sqrt{5}}{10} \end{cases}$$

Άρα, $$a_n = \frac{5 + 3\sqrt{5}}{10}\left(\frac{1 + \sqrt{5}}{2}\right)^n + \frac{5 - 3\sqrt{5}}{10}\left(\frac{1 - \sqrt{5}}{2}\right)^n, \quad \forall n \in \mathbb{N}^*.$$

Θεωρούμε το σύνολο $D$ των 8 κορυφών του κύβου, το σύνολο $R = \{x, y\}$ των 2 χρωμάτων με $w(x) = x$ και $w(y) = y$. Αν $G$ είναι η ομάδα μεταθέσεων, που αντιστοιχούν σε όλες τις δυνατές περιστροφές του κύβου, θα έχουμε $|G| = 24$ μεταθέσεις, που είναι οι εξής:
Η ταυτοτική μετάθεση με κυκλική αναπαράσταση $x_1^8$.
3 μεταθέσεις, που αντιστοιχούν σε περιστροφές $180^\circ$ γύρω από άξονες, που συνδέουν τα κέντρα απέναντι όψεων, με κυκλική αναπαράσταση $x_2^4$.
6 μεταθέσεις, που αντιστοιχούν σε περιστροφές $90^\circ$ γύρω από άξονες, που συνδέουν τα κέντρα απέναντι όψεων, με κυκλική αναπαράσταση $x_4^2$.
6 μεταθέσεις, που αντιστοιχούν σε περιστροφές γύρω από άξονες, που ενώνουν τα μέσα απέναντι ακμών, με κυκλική αναπαράσταση $x_2^4$.
8 μεταθέσεις, που αντιστοιχούν σε περιστροφές $120^\circ$ γύρω από άξονες, που συνδέουν απέναντι κορυφές, με κυκλική αναπαράσταση $x_1^2x_3^2$.

Συνεπώς, ο δείκτης κύκλων $P_G$ της ομάδας $G$ είναι: $$P_G = \frac{1}{24}\left(x_1^8 + 9x_2^4 + 6x_4^2 + 8x_1^2x_3^2\right)$$ και ο αριθμός εύρεσης σχηματισμών: $$\frac{1}{24}\left[(x+y)^8 + 9(x^2+y^2)^4 + 6(x^4+y^4)^2 + 8(x+y)^2(x^3+y^3)^2\right]$$

Θέτουμε $x = y = 1$ και υπολογίζουμε τον αριθμό των διαφορετικών σχηματισμών $$\frac{1}{24}\left(2^8 + 9 \cdot 2^4 + 6 \cdot 2^2 + 8 \cdot 2^2 \cdot 2^2\right) = 23$$ που είναι ο ζητούμενος αριθμός.

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

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