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

Μεταγραφή από τις φωτογραφίες της 27/01/2026 (η 20260127_092200.jpg είναι διπλότυπο).

20260127_091937.jpg

Θέματα Μικρής Δυσκολίας (6 μονάδες)\(^1\)

[Λείπει από τη φωτογραφία: το κείμενο της υποσημείωσης 1]

1. (1) Έστω η σχέση: \(R = \{(X, Y)\text{: το σύνολο } X \text{ έχει τον ίδιο πληθάριθμο με το σύνολο } Y\text{, δηλαδή, } |X| = |Y|\}\) πάνω στο δυναμοσύνολο \(P(E)\) του συνόλου των ελληνικών λέξεων \(E\). Αποδείξτε αν αυτή η σχέση είναι ή δεν είναι σχέση ισοδυναμίας. Αν είναι σχέση ισοδυναμίας, να περιγράψετε τις κλάσεις ισοδυναμίας (περιγραφή 1-2 γραμμών). Υπόδειξη: Θεωρείστε δεδομένο ότι η ισότητα αριθμών είναι σχέση ισοδυναμίας. Απάντηση:

20260127_092051.jpg

1. (0,8) Να αποδείξετε αν ισχύει η εξής πρόταση για όλους τους ακέραιους \(x, y\) εκτός του μηδέν: «Αν \(x|y\) και \(y|x\) τότε \(x = y\)», όπου «\(x|y\)» σημαίνει ότι ο ακέραιος \(x\) διαιρεί τέλεια τον ακέραιο \(y\) (αφήνει υπόλοιπο 0). Απάντηση:

2. (1,5) Οι παρακάτω ερωτήσεις πολλαπλής επιλογής δίνουν +0,3 όταν η απάντηση είναι σωστή και \(-0,2\) όταν είναι λάθος. Αν δεν απαντήσετε σε ένα ερώτημα, δεν λαμβάνεται υπόψη στη βαθμολόγηση. Η αρνητική βαθμολογία μεταφέρεται στο συνολικό βαθμό.

3. Σε μια πιτσαρία υπάρχουν 9 διαφορετικά υλικά. Θέλουμε να επιλέξουμε 4 διαφορετικά υλικά για μια πίτσα. Πόσοι διαφορετικοί συνδυασμοί υπάρχουν;
4. [ ] Α. \(9^4\)
5. [ ] Β. \(P(9,4)\)
6. [ ] Γ. \(4!\)
7. [ ] Δ. \(\binom{9}{4}\)
8. 5 ίδια τετράδια τοποθετούνται σε ένα ράφι. Πόσοι διαφορετικοί τρόποι τοποθέτησης υπάρχουν;
9. [ ] Α. \(5!\)
10. [ ] Β. 1
11. [ ] Γ. \(5^5\)
12. [ ] Δ. \(\binom{5+2-1}{2}\)
13. Σε ένα χώρο στάθμευσης υπάρχουν 5 διαφορετικές στεγασμένες θέσεις και 9 ίδιες ακάλυπτες θέσεις. Ένα αυτοκίνητο θέλει να σταθμεύσει. Με πόσους τρόπους μπορεί να γίνει αυτό;
14. [ ] Α. 40
15. [ ] Β. 13
16. [ ] Γ. 2
17. [ ] Δ. 6
18. Ένας κωδικός PIN αποτελείται από 4 ψηφία (0-9). Πόσοι διαφορετικοί κωδικοί μπορούν να σχηματιστούν;
19. [ ] Α. \(4!\)
20. [ ] Β. \(10^4\)
21. [ ] Γ. \(P(10,4)\)
22. [ ] Δ. \(\binom{10}{4}\)
23. 5 φίλοι στέκονται στη σειρά για να βγάλουν φωτογραφία. Με πόσους διαφορετικούς τρόπους μπορούν να σταθούν;
24. [ ] Α. \(5!\)
25. [ ] Β. \(2^5\)
26. [ ] Γ. 5
27. [ ] Δ. \(\binom{5}{2}\)

20260127_092157.jpg

[Λείπει από τη φωτογραφία: ο αριθμός του θέματος «4.»]

(1,5) 1. (1) Μια νυχτερινή περιπολία στο ιστορικό κέντρο της Θεσσαλονίκης πρέπει να περάσει ακριβώς μία φορά από κάθε δρόμο και να επιστρέψει στο σημείο εκκίνησης. Το γράφημα \(G = (V, E)\) αναπαριστά το δίκτυο δρόμων της περιοχής. Οι κορυφές \(V = \{\kappa, \lambda, \mu, \nu, \xi\}\) είναι πλατείες και οι ακμές \(E = \{\kappa\mu, \kappa\nu, \lambda\mu, \lambda\nu, \mu\nu, \mu\xi, \nu\xi\}\) είναι οι δρόμοι. Το γράφημα \(G\) είναι απλό, μη κατευθυνόμενο και συνεκτικό. α) (0,5) Να βρείτε ένα κύκλωμα Euler στο γράφημα. β) (0,5) Θέλουμε να κάνουμε την ελάχιστη δυνατή αλλαγή στις ακμές του γραφήματος ώστε να μην υπάρχει πλέον κύκλωμα Euler. Επιτρέπονται προσθέσεις και αφαιρέσεις ακμών. Αναφέρετε την αλλαγή (τις αλλαγές) και αιτιολογήστε γιατί το νέο γράφημα δεν έχει κύκλωμα Euler. 2. (0,5) Σε ένα επιστημονικό συνέδριο συμμετέχουν 10 άτομα. Κατά τη διάρκεια του συνεδρίου, κάθε χειραψία γίνεται μεταξύ δύο διαφορετικών ατόμων, και κανένα ζευγάρι δεν ανταλλάσσει περισσότερες από μία χειραψίες. Είναι δυνατόν ακριβώς 7 άτομα να έχουν ανταλλάξει περιττό αριθμό χειραψιών; Να αιτιολογήσετε την απάντησή σας. Απάντηση:

20260127_105509.jpg

1. (1,2) Έστω ότι ψάχνετε έναν φακό κάμερας στο σπίτι και κάνετε τους εξής συλλογισμούς:
2. «Αν ο φακός είναι στο τραπέζι του σαλονιού, τότε τον χρησιμοποίησα κατά τη διάρκεια της φωτογράφισης.»
3. «Αν δεν φωτογράφιζα στο υπνοδωμάτιο, τότε φωτογράφιζα στο σαλόνι.»
4. «Αν φωτογράφιζα στο υπνοδωμάτιο, τότε ο φακός είναι στη βάση της κάμερας.»
5. «Δεν χρησιμοποίησα τον φακό κατά τη διάρκεια της φωτογράφισης.»
6. «Αν φωτογράφιζα στο σαλόνι, τότε ο φακός βρίσκεται στο τραπέζι του σαλονιού.»
7. «Αν φωτογράφιζα στο υπνοδωμάτιο, τότε ο φακός δεν βρίσκεται στην αποθήκη.» (α) (0,6) Χρησιμοποιώντας τις ακόλουθες προτασιακές μεταβλητές με την παρακάτω ερμηνεία, να μετατρέψετε τις παραπάνω δηλώσεις σε λογικές προτάσεις:
8. \(W\): Ο φακός είναι στο τραπέζι του σαλονιού.
9. \(T\): Τον χρησιμοποίησα κατά τη διάρκεια της φωτογράφισης.
10. \(S\): Φωτογράφιζα στο υπνοδωμάτιο.
11. \(R\): Φωτογράφιζα στο σαλόνι.
12. \(Q\): Ο φακός είναι στη βάση της κάμερας.
13. \(P\): Ο φακός βρίσκεται στην αποθήκη. (β) (0,6) Δεδομένου ότι ο φακός βρίσκεται σε μία θέση (δεν χρειάζεται να κωδικοποιήσετε αυτή την πληροφορία), σας ζητείται να βρείτε τη θέση του φακού (εφόσον είναι δυνατό δεδομένης της αλήθειας αυτών των δηλώσεων). Δώστε τυπική απόδειξη για την ορθότητα του επιχειρήματός σας, χρησιμοποιώντας κανόνες εξαγωγής συμπερασμάτων. Απάντηση:

20260127_111031.jpg

Θέματα Μεσαίας Δυσκολίας (5 μονάδες)

1. (1,2) Έστω ότι \(S\) είναι το υποσύνολο του συνόλου των διατεταγμένων ζευγών μη-αρνητικών ακεραίων που ορίζονται αναδρομικά ως εξής: Βάση: \((0,0) \in S\) Αναδρομικό Βήμα: Αν \((x, y) \in S\) τότε \((x+2, y+3) \in S\) και \((x+3, y+2) \in S\). α) (0,2) Να παραθέσετε τα στοιχεία που παράγονται από τις δύο πρώτες εφαρμογές του αναδρομικού ορισμού. β) (1) Να χρησιμοποιήσετε δομική επαγωγή για να δείξετε ότι το 5 διαιρεί τέλεια το \(x+y\) (δηλ. \(5 | x+y\)), όταν \((x, y) \in S\). Απάντηση:

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

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

Προσοχή

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

AI λύσεις — 2026-01

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

Θέμα 1

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή

Η \(R\) είναι «\(|X|=|Y|\)». - Ανακλαστική: \(|X|=|X|\). Συμμετρική: \(|X|=|Y|\Rightarrow|Y|=|X|\). Μεταβατική: \(|X|=|Y|,|Y|=|Z|\Rightarrow|X|=|Z|\) (από την ισότητα αριθμών).

Άρα είναι σχέση ισοδυναμίας. Κάθε κλάση ισοδυναμίας είναι το σύνολο όλων των συνόλων λέξεων με συγκεκριμένο πληθάριθμο, π.χ. η κλάση του \(0\) είναι \(\{\emptyset\}\), του \(1\) όλα τα μονοσύνολα λέξεων, του \(k\) όλα τα υποσύνολα του \(E\) με ακριβώς \(k\) λέξεις (αν \(E\) πεπερασμένο με \(n\) λέξεις: \(n+1\) κλάσεις, η \(k\)-οστή με \(\binom nk\) στοιχεία).

Θέμα 2

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή

Η πρόταση δεν ισχύει. Αντιπαράδειγμα: \(x=1,\ y=-1\). Τότε \(1\mid-1\) και \(-1\mid1\), αλλά \(x\ne y\). (Γενικά από \(x\mid y\) και \(y\mid x\) προκύπτει μόνο \(|x|=|y|\), δηλ. \(x=\pm y\). Θα ίσχυε για φυσικούς αριθμούς.)

Θέμα 3

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή

1. 4 από 9 υλικά, χωρίς σειρά: Δ. \(\binom94\).
2. 5 ίδια τετράδια: μία διάταξη: Β. 1.
3. Το αυτοκίνητο διαλέγει μία από 5 διαφορετικές στεγασμένες θέσεις ή μία από τις (όμοιες) ακάλυπτες: \(5+1=\) Δ. 6 (αν οι ακάλυπτες θεωρούνται ίδιες, όπως λέει η εκφώνηση).
4. Κωδικός 4 ψηφίων με επανάληψη: Β. \(10^4\).
5. Μεταθέσεις 5 φίλων: Α. \(5!\).

Θέμα 4.1 α)

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή

Βαθμοί: \(\kappa:2\) (\(\mu,\nu\)), \(\lambda:2\) (\(\mu,\nu\)), \(\mu:4\) (\(\kappa,\lambda,\nu,\xi\)), \(\nu:4\) (\(\kappa,\lambda,\mu,\xi\)), \(\xi:2\) (\(\mu,\nu\)). Όλοι άρτιοι και το γράφημα συνεκτικό, άρα υπάρχει κύκλωμα Euler. Ένα τέτοιο: $\(\kappa\to\mu\to\lambda\to\nu\to\mu\to\xi\to\nu\to\kappa\)$ Χρησιμοποιεί τις 7 ακμές \(\kappa\mu,\mu\lambda,\lambda\nu,\nu\mu,\mu\xi,\xi\nu,\nu\kappa\) από μία φορά και επιστρέφει στο \(\kappa\).

Θέμα 4.1 β)

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή

Αρκεί μία αλλαγή, π.χ. να αφαιρέσουμε την ακμή \(\kappa\mu\) (ή να προσθέσουμε την \(\kappa\lambda\)). Η αφαίρεση/προσθήκη μιας ακμής αλλάζει την ισοτιμία του βαθμού ακριβώς δύο κορυφών: εδώ οι \(\kappa\) και \(\mu\) γίνονται βαθμού \(1\) και \(3\) (περιττοί). Κύκλωμα Euler υπάρχει μόνο αν όλοι οι βαθμοί είναι άρτιοι· άρα δεν υπάρχει. Αλλαγή 0 ακμών δεν αρκεί (το αρχικό έχει κύκλωμα), άρα μία είναι το ελάχιστο.

Θέμα 4.2

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή

Όχι. Σε κάθε γράφημα το άθροισμα των βαθμών είναι \(2|E|\) (άρτιο), άρα το πλήθος των κορυφών περιττού βαθμού είναι άρτιο (λήμμα χειραψιών). Το 7 είναι περιττό, άρα αδύνατο.

Θέμα 5α

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή

1. \(W\to T\)
2. \(\neg S\to R\)
3. \(S\to Q\)
4. \(\neg T\)
5. \(R\to W\)
6. \(S\to\neg P\)

Θέμα 5β

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή

Τυπική απόδειξη: 1. \(\neg T\) (υπόθεση 4) 2. \(W\to T\) (υπόθεση 1) 3. \(\neg W\) (Modus Tollens, 1,2) 4. \(R\to W\) (υπόθεση 5) 5. \(\neg R\) (Modus Tollens, 3,4) 6. \(\neg S\to R\) (υπόθεση 2) 7. \(\neg\neg S\) (Modus Tollens, 5,6), άρα \(S\) 8. \(S\to Q\) (υπόθεση 3) 9. \(Q\) (Modus Ponens, 7,8) 10. \(S\to\neg P\) (υπόθεση 6), άρα \(\neg P\) (Modus Ponens)

Ο φακός βρίσκεται στη βάση της κάμερας (\(Q\)), όχι στο τραπέζι του σαλονιού (\(\neg W\)) και όχι στην αποθήκη (\(\neg P\)). Η θέση είναι μία, άρα μοναδικά καθορισμένη.

Θέμα 6α

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή

Στοιχεία που παράγονται: - 1η εφαρμογή (από \((0,0)\)): \((2,3)\) και \((3,2)\). - 2η εφαρμογή (από αυτά): \((4,6),(5,5)\) από το \((2,3)\) και \((5,5),(6,4)\) από το \((3,2)\), δηλ. νέα στοιχεία \((4,6),(5,5),(6,4)\).

Θέμα 6β

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή

Δομική επαγωγή στον ορισμό του \(S\), ισχυρισμός \(P(x,y)\): \(5\mid x+y\). - Βάση: \((0,0)\): \(0+0=0\) και \(5\mid0\). - Επαγωγικό βήμα: έστω \((x,y)\in S\) με \(5\mid x+y\) (επαγωγική υπόθεση). Για \((x+2,y+3)\): \((x+2)+(y+3)=(x+y)+5\). Για \((x+3,y+2)\): \((x+3)+(y+2)=(x+y)+5\). Και τα δύο είναι άθροισμα πολλαπλασίων του 5.

Άρα \(5\mid x+y\) για κάθε \((x,y)\in S\) (επαληθεύτηκε και υπολογιστικά για τα πρώτα 8 επίπεδα).

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

---

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