2022)¶

Μεταγραφή από τη φωτογραφία IMG_20220617_133500.jpg.

IMG_20220617_133500.jpg¶

ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ ΕΞΕΤΑΣΗ ΣΤΟ ΜΑΘΗΜΑ «ΔΙΑΚΡΙΤΑ ΜΑΘΗΜΑΤΙΚΑ» - 17/06/2022 (Διάρκεια Εξέτασης 2 ώρες και 30 λεπτά)

[Λείπει από τη φωτογραφία: αριθμός και βαθμολογία της πρώτης ερώτησης· η αρχή της πρότασης είναι κομμένη]

…%) Έστω ότι έχουμε ένα μεγάλο πλήθος από ξαπλώστρες χρώματος άσπρου, κόκκινου, μπλε και πράσινου [λείπει τμήμα στο δεξιό άκρο] τοποθετήσουμε στην παραλία για το πάρτι γενεθλίων μας. Με πόσους τρόπους μπορούμε να επιλέξου[λείπει τμήμα στο δεξιό άκρο] ώστρες (δεν μας ενδιαφέρει η σειρά) έτσι ώστε να ισχύουν ταυτόχρονα οι εξής περιορισμοί: α) να υπάρχει μία κόκκινη ξαπλώστρα, β) να υπάρχει το πολύ μία πράσινη ξαπλώστρα, γ) να υπάρχουν τουλάχιστον [λείπει τμήμα στο δεξιό άκρο]νες ξαπλώστρες περιττού πλήθους και δ) να υπάρχουν τουλάχιστον δύο μπλε ξαπλώστρες άρτιου πλήθους.

Υπόδειξη: Η γεννήτρια συνάρτηση $\frac{1}{(1-x)^n}$ αντιστοιχεί σε μία ακολουθία της οποίας ο $k$-οστός όρος είναι ο $\binom{n+k-1}{k}$

2. (15%) Θεωρούμε το σύνολο $\Pi$ των $7^m$ διαφορετικών αριθμών μήκους $m$ που σχηματίζονται από τα 7 ψηφία [λείπει από τη φωτογραφία: τμήμα του καταλόγου των ψηφίων στο δεξιό άκρο της γραμμής], 3, 4, 5 και 6. Έστω η διμελής σχέση $R$ που ορίζεται ως εξής:

\[(\alpha, \beta) \in R \text{ αν η κατανομή των ψηφίων είναι ίδια και στις δύο λέξεις } \alpha \text{ και } \beta\]

(Η κατανομή των ψηφίων ενός αριθμού είναι το πλήθος των εμφανίσεων κάθε ψηφίου.)

(7%) Να δείξετε αν η $R$ είναι σχέση ισοδυναμίας.

(8%) Αν η $R$ είναι σχέση ισοδυναμίας τότε αυτή δημιουργεί μία διαμέριση στο σύνολο $\Pi$. Έστω ότι αυτή η διαμέριση αποτελείται από τα υποσύνολα $\Pi_1, \Pi_2, \ldots, \Pi_k$. Να υπολογίσετε το $k$, δηλαδή το πλήθος των υποσυνόλων της διαμέρισης λόγω της σχέσης $R$.

3. (10%) Έστω τα κατηγορήματα $P(x) = \text{«ο } 3x + 1 \text{ είναι περιττός»}$ και $Q(x) = \text{«ο } x \text{ είναι περιττός»}$. Να αποδείξετε [λείπει τμήμα στο αριστερό άκρο] ισχύει ή όχι η πρόταση $\forall x (P(x) \rightarrow Q(x))$ ξεκινώντας από την αντιθετοαντιστροφή μορφή της συνεπαγωγής. Τομέας αναφοράς του $x$ είναι όλοι οι φυσικοί αριθμοί.

4. (16%) Έστω $S_m = \{1, 2, \ldots, m\}$ το σύνολο των φυσικών από το 1 έως το $m$ και $P(S_m)$ το δυναμοσύνολο του $S_m$. Έστω $Q$ κατηγόρημα με τομέα αναφοράς το $P(S_m)$ που ερμηνεύεται ως εξής: $Q(x, y) = \text{"}x \supseteq y\text{"}$. Για κάθε μία [λείπει τμήμα στο δεξιό άκρο] τις παρακάτω λογικές προτάσεις σας ζητείται να αναφέρετε με συνοπτική αιτιολόγηση αν είναι Αληθείς ή Ψευδείς [λείπει τμήμα στο δεξιό άκρο]

$\exists y \forall x Q(x, y)$
$\forall x \exists y (x \neq y \wedge Q(y, x))$
$\forall x \forall y (Q(x, y) \rightarrow (x \cap y \neq \emptyset))$ (το $\emptyset$ είναι το κενό σύνολο)
$\forall x \forall y \big(Q(x, y) \rightarrow (Q(x, x \cup y))\big)$

5. (14%) Να υπολογίσετε το εξής άθροισμα: $S_n = \sum_{k=0}^{n} k^2 2^k$, αν σας δίνεται ότι $\sum_{i=0}^{n} i 2^i = (n - 1) 2^{n+1} + $ [λείπει από τη φωτογραφία: το υπόλοιπο της ισότητας στο δεξιό άκρο] (προτείνεται να χρησιμοποιήσετε την τεχνική εξίσωσης αθροίσματος)

6. (30%) α. (10%) Χρησιμοποιώντας συνδυαστική απόδειξη να δείξετε ότι: $\binom{n}{k}\binom{k}{m} = \binom{n}{m}\binom{n-m}{k-m}$

β. (20%) Στα παρακάτω ερωτήματα δεν χρειάζεται να δώσετε αριθμητικό αποτέλεσμα. Ο τύπος με την κα[τάλληλη] συνοπτική αιτιολόγηση είναι αρκετά.

i. Πόσες διαφορετικές λέξεις (χωρίς να σημαίνει ότι έχουν νόημα) μπορούμε να φτιάξουμε από τα γ[ράμματα] της λέξης ΠΑΡΑΣΑΝΤΑΛΟΣ;
ii. Πόσες λέξεις από το ερώτημα (i) έχουν τα ίδια γράμματα γειτονικά το ένα με το άλ[λο] (π.χ. ΠΑΑΑΑΡΣΣΟΛΝΤ);
iii. Πόσες λέξεις από το ερώτημα (i) δεν έχουν γειτονικά Σ (π.χ. ΠΣΑΑΣΑΑΟΡΤΝΛ);
iv. Αν επιλέγουμε τυχαία θετικούς ακεραίους, ποιο είναι το ελάχιστο πλήθος τέτοιων ακεραίων που [λείπει τμήμα στο δεξιό άκρο] επιλέξουμε ώστε να εγγυηθούμε ότι για δύο από αυτούς τους αριθμούς $a$ και $b$ θα ισχύει $a - [\text{λείπει από τη φωτογραφία}] \equiv 1 \pmod{13}$.

[Λείπει από τη φωτογραφία: αριθμός της ερώτησης (10%)]

Να δείξετε ότι η παρακάτω έκφραση είναι ταυτολογία χωρίς τη χρήση πίνακα αληθείας.

\[((p \vee q) \wedge (p \rightarrow q)) \rightarrow q\]

(10%) Να αποδείξετε ότι ο $\text{ΜΚΔ}(\alpha + 7, \alpha + 10)$ διαιρεί τέλεια τον αριθμό 3 (δηλαδή να δείξετε ότι $\text{ΜΚΔ}(\alpha + 7, \alpha + 10) \mid 3$) (ΜΚΔ: Μέγιστος Κοινός Διαιρέτης). [λείπει τμήμα στο δεξιό άκρο]

Λύσεις (⚪ AI, μη επαληθευμένο)

Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, gemini-3.7-flash, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο

Προσοχή

Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.

AI λύσεις — 2022-06¶

Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.

Θέμα 1¶

Αξιοπιστία: δεν λύθηκε

Δεν λύθηκε: η εκφώνηση είναι κομμένη (λείπουν ο αριθμός ερωτήσεων/ξαπλωστρών και οι περιορισμοί γ, δ δεν διαβάζονται πλήρως).

Θέμα 2¶

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

Ισοδυναμία. Η $R$ είναι «$f(\alpha)=f(\beta)$» όπου $f(\alpha)$ = η κατανομή (το διάνυσμα των πλήθων εμφάνισης των 7 ψηφίων). - Ανακλαστική: $f(\alpha)=f(\alpha)$. - Συμμετρική: αν $f(\alpha)=f(\beta)$ τότε $f(\beta)=f(\alpha)$. - Μεταβατική: από $f(\alpha)=f(\beta)$, $f(\beta)=f(\gamma)$ προκύπτει $f(\alpha)=f(\gamma)$.

Άρα η $R$ είναι σχέση ισοδυναμίας.

Πλήθος κλάσεων. Δύο λέξεις μήκους $m$ είναι στην ίδια κλάση ακριβώς όταν έχουν την ίδια κατανομή· μια κλάση αντιστοιχεί σε διάνυσμα $(c_1,\dots,c_7)$ με $c_i\ge0$, $\sum c_i=m$ (κάθε τέτοιο διάνυσμα πραγματοποιείται). Το πλήθος είναι οι μη αρνητικές λύσεις: $k=\binom{m+6}{6}$ (έλεγχος σε Python για $m=3$: 84).

(Σημ.: το μήκος των ψηφίων είναι 7 από το $7^m$· ο κατάλογος των ψηφίων είναι κομμένος στη φωτογραφία.)

Θέμα 3¶

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

Ισχύει $3x+1$ περιττός ⇔ $3x$ άρτιος ⇔ $x$ άρτιος. Η αντιθετοαντιστροφή του $P(x)\to Q(x)$ είναι $\neg Q(x)\to\neg P(x)$: «αν ο $x$ είναι άρτιος, τότε ο $3x+1$ είναι άρτιος». Όμως για $x=2k$ ο $3x+1=6k+1$ είναι περιττός. Άρα η αντιθετοαντιστροφή (και ισοδύναμα η αρχική) αποτυγχάνει, π.χ. $x=2$: $3\cdot2+1=7$ περιττός ενώ ο $2$ δεν είναι περιττός.

Η πρόταση $\forall x\,(P(x)\to Q(x))$ δεν ισχύει (αντιπαράδειγμα $x=2$).

Θέμα 4¶

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

Τομέας: υποσύνολα του $S_m$, $Q(x,y)$: $x\supseteq y$. 1. $\exists y\forall x\,Q(x,y)$: Αληθής· $y=\emptyset$, κάθε $x\supseteq\emptyset$. 2. $\forall x\exists y\,(x\ne y\land y\supseteq x)$: Ψευδής· για $x=S_m$ το μόνο $y\supseteq S_m$ είναι το $S_m=x$. 3. $\forall x\forall y\,(x\supseteq y\to x\cap y\neq\emptyset)$: Ψευδής· $x=y=\emptyset$: $\emptyset\supseteq\emptyset$ αλλά $\emptyset\cap\emptyset=\emptyset$. 4. $\forall x\forall y\,(x\supseteq y\to x\supseteq x\cup y)$: Αληθής· αν $x\supseteq y$ τότε $x\cup y=x$, και $x\supseteq x$.

Θέμα 5¶

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

Η τιμή που λείπει στο δοθέν είναι $+2$: $T_n=\sum_{i=0}^n i2^i=(n-1)2^{n+1}+2$ (επαληθεύτηκε σε Python).

Τεχνική εξίσωσης αθροίσματος: $$S_n+(n+1)^22^{n+1}=\sum_{k=0}^n(k+1)^22^{k+1}=2\sum_{k=0}^n(k^2+2k+1)2^k=2S_n+4T_n+2(2^{n+1}-1).$$ Άρα $S_n=(n+1)^22^{n+1}-4T_n-2^{n+2}+2=2^{n+1}\big[(n+1)^2-4(n-1)-2\big]-8+2$, δηλαδή $$\boxed{S_n=(n^2-2n+3)\,2^{n+1}-6}$$ (επαληθεύτηκε σε Python για $n=0..11$).