Διακριτά Μαθηματικά — Ιανουάριος 2014¶

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

examsJan14.pdf¶

ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΩΝ ΠΟΛΥΤΕΧΝΙΚΗ ΣΧΟΛΗ¶

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

ΕΞΕΤΑΣΗ ΙΑΝΟΥΑΡΙΟΥ 2014¶

ΠΑΡΑΣΚΕΥΗ 31 ΙΑΝΟΥΑΡΙΟΥ 2014¶

ΔΙΑΚΡΙΤΑ ΜΑΘΗΜΑΤΙΚΑ Ι¶

ΚΑΘΗΓΗΤΗΣ Χ. Ι. ΜΠΟΥΡΑΣ¶

ΘΕΜΑΤΑ¶

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

(25 μονάδες)

΄Εχουμε μία ομάδα 12 ατόμων που αποτελείται από 5 άνδρες και 7 γυναίκες. Χρησιμοποιώντας ΣΥΝΔΥΑΣΤΙΚΑ ΕΠΙΧΕΙΡΗΜΑΤΑ να υπολογίσετε:

(αʹ) Πόσες 5μελείς ομάδες μπορούν να σχηματστούν με 3 άνδρες και 2 γυναίκες; (βʹ) Πόσες 5μελείς ομάδες περιέχουν τουλάχιστον 1 άνδρα;

(25 μονάδες)

Υποθέτοντας ότι η βάση της πυραμίδας παραμένει σταθερή και οι συμμετρίες προκύπτουν μετά από περιστροφή της γύρω από τον κατακόρυφο άξονα, χρησιμοποιώντας το ΘΕΩΡΗΜΑ P´olya να υπολογίσετε με πόσους τρόπους μπορώ να χρωματίσω τις πλευρές μιας πυραμίδας με 2 χρώματα;

(25 μονάδες)

Χρησιμοποιώντας ΔΙΩΝΥΜΙΚΟΥΣ ΣΥΝΤΕΛΕΣΤΕΣ να αποδείξετε ότι

\[\binom{n}{0}^2 + \binom{n}{1}^2 + \ldots + \binom{n}{n}^2 = \binom{2n}{n}\]

(25 μονάδες)

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

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

Ενημερωθείτε για τα θέματα των Διπλωματικών Εργασιών για το 2013 − 14 στο http://ru6.cti.gr/bouras/diplwmatikes ~~2~~ 013-2014.pdf

Λύσεις (🟢 official)

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

Λύσεις — Διακριτά Μαθηματικά — Ιανουάριος 2014¶

solutionsJan14.pdf¶

Έστω μία ακολουθία μήκους $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}^*.$$

(αʹ) Υπάρχουν $\binom{5}{3}$ τρόποι για να επιλέξουμε 3 άνδρες από τους 5 άνδρες και $\binom{7}{2}$ τρόποι για να επιλέξουμε 2 γυναίκες από τις 7 γυναίκες.

Άρα υπάρχουν συνολικά $\binom{5}{3}\binom{7}{2} = 210$ τρόποι για να επιλέξουμε 3 άνδρες και 2 γυναίκες.

(βʹ) (πλήθος ομάδων με τουλάχιστον έναν άνδρα) = (συνολικός αριθμός πενταμελών ομάδων) - (πλήθος πενταμελών ομάδων που ΔΕΝ περιέχουν κανέναν άνδρα) $= \binom{12}{5} - \binom{7}{5} = 771$

Η βάση της πυραμίδας παραμένει σταθερή και οι συμμετρίες προκύπτουν μετά από περιστροφή της γύρω από τον κατακόρυφο άξονα.
$D = \{a, b, c, d\}$, οι πλευρές
$R = \{x, y\}$, τα χρώματα με $w(x) = x$, $w(y) = y$
Έχουμε τις εξής μεταθέσεις: $\pi_1 = \begin{pmatrix} abcd \ abcd \end{pmatrix}$, $\pi_2 = \begin{pmatrix} abcd \ bcad \end{pmatrix}$ και $\pi_3 = \begin{pmatrix} abcd \ cabd \end{pmatrix}$, δηλ. $|G| = 3$.
Για την $\pi_1$ είναι: $x_1^4$
Για την $\pi_2$ είναι: $x_1^1x_3^1$
Για την $\pi_3$ είναι: $x_1^1x_3^1$
Οπότε: $P_G = \frac{x_1^4 + x_1^1x_3^1 + x_1^1x_3^1}{3} = \frac{x_1^4 + 2x_1^1x_3^1}{3}$
Έχουμε 2 χρώματα με βάρη $x, y$, οπότε:
Οπότε: $P_G = \frac{(x+y)^4 + 2(x+y)(x^3+y^3)}{3} = x^4 + y^4 + 2x^3y + 2x^2y^2 + 2xy^3$
Θέτοντας $x = y = 1$ έχουμε: $1+1+2+2+2 = 8$ τρόποι δηλ. διαφορετικοί χρωματισμοί.

[Σχήμα: τριγωνική πυραμίδα με τις έδρες/πλευρές ονομασμένες a, b, c, d]

Εναλλακτικά: Η βάση της πυραμίδας μπορεί να χρωματιστεί με δύο τρόπους (αφού 2 είναι τα διαθέσιμα χρώματα). Για κάθε έναν από αυτούς τους χρωματισμούς, οι διαφορετικοί χρωματισμοί που μπορούν να λάβουν οι υπόλοιπες πλευρές προκύπτουν ως εξής: - $D = \{a, b, c\}$, οι πλευρές (εκτός της βάσης) - $R = \{x, y\}$, τα χρώματα με $w(x) = x$, $w(y) = y$ - Έχουμε τις εξής μεταθέσεις: $\pi_1 = \begin{pmatrix} abc \ abc \end{pmatrix}$, $\pi_2 = \begin{pmatrix} abc \ bca \end{pmatrix}$ και $\pi_3 = \begin{pmatrix} abc \ cab \end{pmatrix}$, δηλ. $|G| = 3$. - Για την $\pi_1$ είναι: $x_1^3$ - Για την $\pi_2$ είναι: $x_3^1$ - Για την $\pi_3$ είναι: $x_3^1$ - Οπότε: $P_G = \frac{x_1^3 + x_3^1 + x_3^1}{3} = \frac{x_1^3 + 2x_3^1}{3}$ - Έχουμε 2 χρώματα με βάρη $x, y$, οπότε: - Οπότε: $P_G = \frac{(x+y)^3 + 2(x^3+y^3)}{3}$ - Θέτοντας $x = y = 1$ έχουμε: $\frac{2^3+2\cdot 2}{3} = 4$ τρόποι δηλ. διαφορετικοί χρωματισμοί για κάθε διαφορετικό χρωματισμό της βάσης. Επομένως, συνολικά υπάρχουν $2 \cdot 4 = 8$ διαφορετικοί χρωματισμοί.

Έχουμε: $$(1 + x)^{2n} = \sum_{k=0}^{2n}\binom{2n}{k}x^k \qquad (1)$$

Επίσης $(1 + x)^n(1 + x)^n = \sum_{i=0}^{n}\binom{n}{i}x^i \sum_{j=0}^{n}\binom{n}{j}x^j =$

Από ιδιότητες σειρών έχουμε: $$\sum_{i=0}^{n}\binom{n}{i}x^i \sum_{j=0}^{n}\binom{n}{j}x^j = \sum_{r=0}^{2n}\left(\sum_{k=0}^{r}\binom{n}{k}\binom{n}{r-k}\right)x^r \qquad (2)$$

Άρα από ιδιότητες των διωνυμικών συντελεστών και εξισώνοντας τους συντελεστές του $x^n$ από την (1) και (2) έχουμε: $$\binom{2n}{n} = \sum_{k=0}^{n}\binom{n}{k}\binom{n}{n-k} = \sum_{k=0}^{n}\binom{n}{k}\binom{n}{k} = \binom{n}{0}^2 + \binom{n}{1}^2 + \ldots + \binom{n}{n}^2$$

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

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