.jpg)
🎮 2026 MATH MARATHON - GAME THEORY #1
Game Theory Mastery
Part 1: Nim Games & Basic Strategy - Τα Θεμέλια των Παιχνιδιών
🎮 Καλωσορίσατε στο Game Theory Marathon!
Τα combinatorial games είναι από τα πιο συναρπαστικά κομμάτια των μαθηματικών! Εμφανίζονται σε κάθε Ολυμπιάδα και χρειάζονται ειδική στρατηγική σκέψη.
Σήμερα (Part 1):
✅ Τι είναι Nim Games
✅ Winning vs Losing Positions
✅ Graph Theory Representation
✅ Simple Pairing Strategy
✅ Bachet's Game (Classic!)
✅ 7 αναλυτικά παραδείγματα
✅ Competition framework
Τα combinatorial games είναι από τα πιο συναρπαστικά κομμάτια των μαθηματικών! Εμφανίζονται σε κάθε Ολυμπιάδα και χρειάζονται ειδική στρατηγική σκέψη.
Σήμερα (Part 1):
✅ Τι είναι Nim Games
✅ Winning vs Losing Positions
✅ Graph Theory Representation
✅ Simple Pairing Strategy
✅ Bachet's Game (Classic!)
✅ 7 αναλυτικά παραδείγματα
✅ Competition framework
🤔 Ερώτηση Προβληματισμού:
Γιατί τα game theory problems είναι τόσο δύσκολα; Επειδή δεν αρκεί να βρούμε **μία κίνηση** - πρέπει να βρούμε μια **στρατηγική** που κερδίζει **σίγουρα** ανεξάρτητα από το τι κάνει ο αντίπαλος!
Γιατί τα game theory problems είναι τόσο δύσκολα; Επειδή δεν αρκεί να βρούμε **μία κίνηση** - πρέπει να βρούμε μια **στρατηγική** που κερδίζει **σίγουρα** ανεξάρτητα από το τι κάνει ο αντίπαλος!
🎯 1. Τι είναι Nim Games;
📌 Ορισμός: Nim Game
Ένα Nim Game (ή impartial game) είναι ένα παιχνίδι όπου:
1. Δύο παίκτες: Παίκτες \(A\) και \(B\) που παίζουν εναλλάξ
2. Κανόνες ίδιοι: Οι κανόνες είναι οι ίδιοι και για τους δύο παίκτες (impartial)
3. Τέλος παιχνιδιού: Η ισοπαλία δεν μπορεί να συμβεί. Ένας παίκτης φτάνει σε θέση όπου δεν μπορεί να κάνει νόμιμη κίνηση και χάνει
4. Πεπερασμένες καταστάσεις: Το παιχνίδι τελειώνει σε πεπερασμένο αριθμό κινήσεων
5. Πλήρης πληροφορία: Και οι δύο παίκτες γνωρίζουν την κατάσταση του παιχνιδιού
Ένα Nim Game (ή impartial game) είναι ένα παιχνίδι όπου:
1. Δύο παίκτες: Παίκτες \(A\) και \(B\) που παίζουν εναλλάξ
2. Κανόνες ίδιοι: Οι κανόνες είναι οι ίδιοι και για τους δύο παίκτες (impartial)
3. Τέλος παιχνιδιού: Η ισοπαλία δεν μπορεί να συμβεί. Ένας παίκτης φτάνει σε θέση όπου δεν μπορεί να κάνει νόμιμη κίνηση και χάνει
4. Πεπερασμένες καταστάσεις: Το παιχνίδι τελειώνει σε πεπερασμένο αριθμό κινήσεων
5. Πλήρης πληροφορία: Και οι δύο παίκτες γνωρίζουν την κατάσταση του παιχνιδιού
🎲 Graph Theory Representation
Μπορούμε να σκεφτόμαστε κάθε θέση ως κορυφή γράφου και κάθε κίνηση ως κατευθυνόμενη ακμή.
Κορυφές: Όλες οι δυνατές θέσεις του παιχνιδιού
Ακμές: Νόμιμες κινήσεις από μία θέση σε άλλη
Κύκλοι: Δεν υπάρχουν (το παιχνίδι προχωράει μόνο μπροστά)
Σημαντικό: Το γράφος είναι acyclic (χωρίς κύκλους) - εξασφαλίζει ότι το παιχνίδι τελειώνει!
Μπορούμε να σκεφτόμαστε κάθε θέση ως κορυφή γράφου και κάθε κίνηση ως κατευθυνόμενη ακμή.
Κορυφές: Όλες οι δυνατές θέσεις του παιχνιδιού
Ακμές: Νόμιμες κινήσεις από μία θέση σε άλλη
Κύκλοι: Δεν υπάρχουν (το παιχνίδι προχωράει μόνο μπροστά)
Σημαντικό: Το γράφος είναι acyclic (χωρίς κύκλους) - εξασφαλίζει ότι το παιχνίδι τελειώνει!
🏆 2. Winning vs Losing Positions
📐 Βασικοί Ορισμοί
Έστω \(P\) το σύνολο όλων των θέσεων και \(L, W\) τα υποσύνολα:
Losing Position (L):
Μια θέση ανήκει στο \(L\) αν ο παίκτης που βρίσκεται σε αυτή τη θέση θα χάσει με βέλτιστο παιχνίδι.
Winning Position (W):
Μια θέση ανήκει στο \(W\) αν ο παίκτης που βρίσκεται σε αυτή τη θέση μπορεί να κερδίσει με κατάλληλη στρατηγική.
Ιδιότητες:
• \(P = L \cup W\) (κάθε θέση είναι είτε \(L\) είτε \(W\))
• \(L \cap W = \emptyset\) (μία θέση δεν μπορεί να είναι και τα δύο)
Έστω \(P\) το σύνολο όλων των θέσεων και \(L, W\) τα υποσύνολα:
Losing Position (L):
Μια θέση ανήκει στο \(L\) αν ο παίκτης που βρίσκεται σε αυτή τη θέση θα χάσει με βέλτιστο παιχνίδι.
Winning Position (W):
Μια θέση ανήκει στο \(W\) αν ο παίκτης που βρίσκεται σε αυτή τη θέση μπορεί να κερδίσει με κατάλληλη στρατηγική.
Ιδιότητες:
• \(P = L \cup W\) (κάθε θέση είναι είτε \(L\) είτε \(W\))
• \(L \cap W = \emptyset\) (μία θέση δεν μπορεί να είναι και τα δύο)
📌 Θεώρημα: Χαρακτηρισμός L και W
Μια θέση ανήκει στο \(L\) αν και μόνο αν:
Μια θέση ανήκει στο \(W\) αν και μόνο αν:
💡 Με απλά λόγια:
• Από \(L\) → όλες οι κινήσεις πάνε σε \(W\)
• Από \(W\) → υπάρχει κίνηση που πάει σε \(L\)
Μια θέση ανήκει στο \(L\) αν και μόνο αν:
Από κάθε θέση στο \(L\), κάθε κίνηση οδηγεί σε θέση στο \(W\).
Μια θέση ανήκει στο \(W\) αν και μόνο αν:
Από κάθε θέση στο \(W\), υπάρχει τουλάχιστον μία κίνηση που οδηγεί σε θέση στο \(L\).
💡 Με απλά λόγια:
• Από \(L\) → όλες οι κινήσεις πάνε σε \(W\)
• Από \(W\) → υπάρχει κίνηση που πάει σε \(L\)
🎯 Winning Strategy:
Για να κερδίσεις ένα Nim game:
1. Βρες όλες τις Losing positions \(L\)
2. Αν βρίσκεσαι σε Winning position \(W\), κάνε κίνηση που στέλνει τον αντίπαλο σε \(L\)
3. Αν βρίσκεσαι σε Losing position \(L\), με βέλτιστο παιχνίδι θα χάσεις - οποιαδήποτε κίνηση στέλνει τον αντίπαλο σε \(W\)
Το κλειδί: Κάθε φορά που στέλνεις τον αντίπαλο σε \(L\), αυτός αναγκαστικά θα σε στείλει πίσω σε \(W\), και εσύ πάλι τον στέλνεις σε \(L\), μέχρι να φτάσει στην τελική \(L\) (χωρίς κινήσεις)!
Για να κερδίσεις ένα Nim game:
1. Βρες όλες τις Losing positions \(L\)
2. Αν βρίσκεσαι σε Winning position \(W\), κάνε κίνηση που στέλνει τον αντίπαλο σε \(L\)
3. Αν βρίσκεσαι σε Losing position \(L\), με βέλτιστο παιχνίδι θα χάσεις - οποιαδήποτε κίνηση στέλνει τον αντίπαλο σε \(W\)
Το κλειδί: Κάθε φορά που στέλνεις τον αντίπαλο σε \(L\), αυτός αναγκαστικά θα σε στείλει πίσω σε \(W\), και εσύ πάλι τον στέλνεις σε \(L\), μέχρι να φτάσει στην τελική \(L\) (χωρίς κινήσεις)!
📚 3. Η Simple Pairing Strategy
🎲 The Pairing Strategy
Πολλά προβλήματα λύνονται με την pairing strategy:
Ιδέα:
Χώρισε όλες τις θέσεις σε ζεύγη έτσι ώστε υπάρχει κίνηση από το ένα στοιχείο του ζεύγους στο άλλο.
Στρατηγική:
• Αν υπάρχει θέση χωρίς ζευγάρι, κατάλαβέ την πρώτος!
• Διαφορετικά, αν ο αντίπαλος κινηθεί από μία θέση ενός ζεύγους, εσύ κινήσου στο άλλο στοιχείο του ζεύγους.
Αποτέλεσμα:
Κερδίζεις επειδή ο αντίπαλος θα μείνει χωρίς κινήσεις πρώτος!
Πολλά προβλήματα λύνονται με την pairing strategy:
Ιδέα:
Χώρισε όλες τις θέσεις σε ζεύγη έτσι ώστε υπάρχει κίνηση από το ένα στοιχείο του ζεύγους στο άλλο.
Στρατηγική:
• Αν υπάρχει θέση χωρίς ζευγάρι, κατάλαβέ την πρώτος!
• Διαφορετικά, αν ο αντίπαλος κινηθεί από μία θέση ενός ζεύγους, εσύ κινήσου στο άλλο στοιχείο του ζεύγους.
Αποτέλεσμα:
Κερδίζεις επειδή ο αντίπαλος θα μείνει χωρίς κινήσεις πρώτος!
🎮 4. Bachet's Game - The Classic
🔹 Παράδειγμα 1: Bachet's Game (Classic)
Πρόβλημα: Υπάρχουν αρχικά \(n\) πούλια σε ένα τραπέζι. Ο σύνολο νόμιμων κινήσεων είναι \(M = \{1, 2, 3, \ldots, k\}\). Ο παίκτης που παίρνει το τελευταίο πούλι κερδίζει. Βρείτε τις losing positions.
Λύση:
Λύση:
Ανάλυση:
Το σύνολο \(L\) αποτελείται από όλα τα πολλαπλάσια του \(k+1\).
Δηλαδή:
\[ L = \{0, k+1, 2(k+1), 3(k+1), \ldots\} = \{m(k+1) : m \in \mathbb{N} \cup \{0\}\} \]
Το σύνολο \(L\) αποτελείται από όλα τα πολλαπλάσια του \(k+1\).
Δηλαδή:
\[ L = \{0, k+1, 2(k+1), 3(k+1), \ldots\} = \{m(k+1) : m \in \mathbb{N} \cup \{0\}\} \]
Απόδειξη:
Βήμα 1: Αν \(n\) δεν είναι πολλαπλάσιο του \(k+1\), μπορώ πάντα να κινηθώ σε πολλαπλάσιο του \(k+1\).
Γιατί: Έστω \(n = q(k+1) + r\) όπου \(0 < r \leq k\).
Παίρνω \(r\) πούλια → απομένουν \(q(k+1)\) (πολλαπλάσιο του \(k+1\)!).
Βήμα 2: Αν \(n\) είναι πολλαπλάσιο του \(k+1\), ο αντίπαλός μου δεν μπορεί να με αφήσει σε πολλαπλάσιο του \(k+1\).
Γιατί: Αν παίρνει \(1, 2, \ldots, k\) πούλια από \(m(k+1)\), μένουν:
\[ m(k+1) - j \quad (j \in \{1,2,\ldots,k\}) \]
που δεν είναι πολλαπλάσιο του \(k+1\)!
Βήμα 3: Αν ακολουθήσω τη στρατηγική "κάθε φορά αφήνω πολλαπλάσιο του \(k+1\)", τελικά θα φτάσω στο 0, άρα κερδίζω!
Απάντηση:Βήμα 1: Αν \(n\) δεν είναι πολλαπλάσιο του \(k+1\), μπορώ πάντα να κινηθώ σε πολλαπλάσιο του \(k+1\).
Γιατί: Έστω \(n = q(k+1) + r\) όπου \(0 < r \leq k\).
Παίρνω \(r\) πούλια → απομένουν \(q(k+1)\) (πολλαπλάσιο του \(k+1\)!).
Βήμα 2: Αν \(n\) είναι πολλαπλάσιο του \(k+1\), ο αντίπαλός μου δεν μπορεί να με αφήσει σε πολλαπλάσιο του \(k+1\).
Γιατί: Αν παίρνει \(1, 2, \ldots, k\) πούλια από \(m(k+1)\), μένουν:
\[ m(k+1) - j \quad (j \in \{1,2,\ldots,k\}) \]
που δεν είναι πολλαπλάσιο του \(k+1\)!
Βήμα 3: Αν ακολουθήσω τη στρατηγική "κάθε φορά αφήνω πολλαπλάσιο του \(k+1\)", τελικά θα φτάσω στο 0, άρα κερδίζω!
Οι losing positions είναι:
\[ L = \{0, k+1, 2(k+1), 3(k+1), \ldots\} \]
Winning strategy: Πάντα αφήνε τον αντίπαλο με πολλαπλάσιο του \(k+1\) πούλια!
\[ L = \{0, k+1, 2(k+1), 3(k+1), \ldots\} \]
Winning strategy: Πάντα αφήνε τον αντίπαλο με πολλαπλάσιο του \(k+1\) πούλια!
🔹 Παράδειγμα 2: Power of 2 Game
Πρόβλημα: Στο πρόβλημα #1, έστω \(M = \{1, 2, 4, 8, \cdots\}\) (δυνάμεις του 2). Βρείτε το σύνολο \(L\).
Λύση:
• \(n = 5\): \(5 \equiv 2 \pmod{3}\), παίρνω 2 → μένουν 3 ✓
• \(n = 7\): \(7 \equiv 1 \pmod{3}\), παίρνω 1 → μένουν 6 ✓
• \(n = 6\): Ο αντίπαλος παίρνει 1,2,4 → μένουν 5,4,2 (όλα μη-πολλαπλάσια του 3)
Απάντηση:
Λύση:
Ανάλυση:
\(L\) αποτελείται από όλα τα πολλαπλάσια του 3.
Απόδειξη: Ένας παίκτης που αντιμετωπίζει πολλαπλάσιο του 3 δεν μπορεί να κινηθεί σε πολλαπλάσιο του 3, αφού \(2^m\) δεν είναι ποτέ πολλαπλάσιο του 3.
Γιατί; Οι δυνάμεις του 2 mod 3 είναι:
• \(2^0 = 1 \equiv 1 \pmod{3}\)
• \(2^1 = 2 \equiv 2 \pmod{3}\)
• \(2^2 = 4 \equiv 1 \pmod{3}\)
• \(2^3 = 8 \equiv 2 \pmod{3}\)
• Pattern: \(1, 2, 1, 2, 1, 2, \ldots\)
Άρα καμία δύναμη του 2 δεν είναι \(\equiv 0 \pmod{3}\)!
Αλλά από μη-πολλαπλάσιο του 3, μπορώ πάντα να κινηθώ σε πολλαπλάσιο του 3:
• Αν \(n \equiv 1 \pmod{3}\): Αφαιρώ 1 → \(n-1 \equiv 0 \pmod{3}\)
• Αν \(n \equiv 2 \pmod{3}\): Αφαιρώ 2 → \(n-2 \equiv 0 \pmod{3}\)
Παράδειγμα:\(L\) αποτελείται από όλα τα πολλαπλάσια του 3.
Απόδειξη: Ένας παίκτης που αντιμετωπίζει πολλαπλάσιο του 3 δεν μπορεί να κινηθεί σε πολλαπλάσιο του 3, αφού \(2^m\) δεν είναι ποτέ πολλαπλάσιο του 3.
Γιατί; Οι δυνάμεις του 2 mod 3 είναι:
• \(2^0 = 1 \equiv 1 \pmod{3}\)
• \(2^1 = 2 \equiv 2 \pmod{3}\)
• \(2^2 = 4 \equiv 1 \pmod{3}\)
• \(2^3 = 8 \equiv 2 \pmod{3}\)
• Pattern: \(1, 2, 1, 2, 1, 2, \ldots\)
Άρα καμία δύναμη του 2 δεν είναι \(\equiv 0 \pmod{3}\)!
Αλλά από μη-πολλαπλάσιο του 3, μπορώ πάντα να κινηθώ σε πολλαπλάσιο του 3:
• Αν \(n \equiv 1 \pmod{3}\): Αφαιρώ 1 → \(n-1 \equiv 0 \pmod{3}\)
• Αν \(n \equiv 2 \pmod{3}\): Αφαιρώ 2 → \(n-2 \equiv 0 \pmod{3}\)
• \(n = 5\): \(5 \equiv 2 \pmod{3}\), παίρνω 2 → μένουν 3 ✓
• \(n = 7\): \(7 \equiv 1 \pmod{3}\), παίρνω 1 → μένουν 6 ✓
• \(n = 6\): Ο αντίπαλος παίρνει 1,2,4 → μένουν 5,4,2 (όλα μη-πολλαπλάσια του 3)
Απάντηση:
\[ L = \{0, 3, 6, 9, 12, 15, \ldots\} = \{3k : k \in \mathbb{N} \cup \{0\}\} \]
🔹 Παράδειγμα 3: Primes and 1 Game
Πρόβλημα: Στο πρόβλημα #1, έστω \(M = \{1, 2, 3, 5, 7, 11, \ldots\}\) (1 και πρώτοι). Βρείτε \(L\).
Λύση:
Λύση:
Ανάλυση:
\(L\) αποτελείται από όλους τους πολλαπλάσιους του 4.
Γιατί: Μπορώ πάντα να κινηθώ σε πολλαπλάσιο του 4 αφαιρώντας 1, 2, ή 3 mod 4.
Από πολλαπλάσιο του 4, δεν μπορώ να παραμείνω σε πολλαπλάσιο του 4:
• Αφαιρώντας 1: \(4k - 1 \equiv 3 \pmod{4}\)
• Αφαιρώντας 2: \(4k - 2 \equiv 2 \pmod{4}\)
• Αφαιρώντας 3: \(4k - 3 \equiv 1 \pmod{4}\)
• Αφαιρώντας πρώτο \(p > 3\): Όλοι οι πρώτοι \(> 3\) είναι περιττοί, άρα \(p \equiv 1\) ή \(3 \pmod{4}\)
Άρα \(4k - p \not\equiv 0 \pmod{4}\) για κάθε επιλογή!
Απάντηση:\(L\) αποτελείται από όλους τους πολλαπλάσιους του 4.
Γιατί: Μπορώ πάντα να κινηθώ σε πολλαπλάσιο του 4 αφαιρώντας 1, 2, ή 3 mod 4.
Από πολλαπλάσιο του 4, δεν μπορώ να παραμείνω σε πολλαπλάσιο του 4:
• Αφαιρώντας 1: \(4k - 1 \equiv 3 \pmod{4}\)
• Αφαιρώντας 2: \(4k - 2 \equiv 2 \pmod{4}\)
• Αφαιρώντας 3: \(4k - 3 \equiv 1 \pmod{4}\)
• Αφαιρώντας πρώτο \(p > 3\): Όλοι οι πρώτοι \(> 3\) είναι περιττοί, άρα \(p \equiv 1\) ή \(3 \pmod{4}\)
Άρα \(4k - p \not\equiv 0 \pmod{4}\) για κάθε επιλογή!
\[ L = \{0, 4, 8, 12, 16, \ldots\} = \{4k : k \in \mathbb{N} \cup \{0\}\} \]
🔹 Παράδειγμα 4: Board Game Translation (από screenshot)
Πρόβλημα: Βρείτε το σύνολο των losing positions για \(M = \{1, 3, 8\}\).
Μεταφράστε το παιχνίδι σε board game: Ξεκινώντας με σειρά κενών κελιών, τοποθετήστε ένα chip στο \(n\)-οστό κελί. Οι παίκτες \(A\) και \(B\) κινούν εναλλάξ το chip στα αριστερά (1, 3, ή 8 θέσεις). Ο παίκτης που δεν μπορεί να κινηθεί (chip στο κελί 0) χάνει.
Λύση:
Μεταφράστε το παιχνίδι σε board game: Ξεκινώντας με σειρά κενών κελιών, τοποθετήστε ένα chip στο \(n\)-οστό κελί. Οι παίκτες \(A\) και \(B\) κινούν εναλλάξ το chip στα αριστερά (1, 3, ή 8 θέσεις). Ο παίκτης που δεν μπορεί να κινηθεί (chip στο κελί 0) χάνει.
Λύση:
Ανάλυση με Υπολογισμό:
Υπολογίζουμε \(L\) και \(W\) για κάθε position:
Συνεχίζοντας, βρίσκουμε periodicity!
Τα losing positions έχουν τη μορφή:
\[ L = \{0, 2, 5, 7, 10, 12, 15, 17, 20, \ldots\} \]
Παρατηρούμε: \(L\) περιέχει \(0, 2, 5\) στο \([0,7)\) και μετά επαναλαμβάνεται με περίοδο που σχετίζεται με τους αριθμούς \(\{0, 2, 5\}\) mod κάποιου modulus.
Υπολογίζουμε \(L\) και \(W\) για κάθε position:
Position 0: L (terminal - χωρίς κινήσεις)
Position 1: W (κινούμαι 1 → 0)
Position 2: L (μόνο 1 → 1 που είναι W)
Position 3: W (3 → 0 ή 1 → 2)
Position 4: W (3 → 1 ή 1 → 3)
Position 5: L (1→4, 3→2 όλα W)
Position 6: W (1 → 5)
Position 7: L (1→6, 3→4 όλα W)
Position 8: W (8 → 0 ή 1 → 7)
Position 9: W (8 → 1 ή 1 → 8)
Position 10: W (8 → 2 ή 1 → 9)
Position 11: W (8 → 3 ή 3 → 8 ή 1 → 10)
Pattern Discovery:Συνεχίζοντας, βρίσκουμε periodicity!
Τα losing positions έχουν τη μορφή:
\[ L = \{0, 2, 5, 7, 10, 12, 15, 17, 20, \ldots\} \]
Παρατηρούμε: \(L\) περιέχει \(0, 2, 5\) στο \([0,7)\) και μετά επαναλαμβάνεται με περίοδο που σχετίζεται με τους αριθμούς \(\{0, 2, 5\}\) mod κάποιου modulus.
Board Visualization:
Winning Strategy: Πάντα κινήσου σε μία από τις \(L\) positions!
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |11 |12 |...
L W L W W L W L W W L W L
Οι θέσεις με \(L\) είναι losing, με \(W\) είναι winning.Winning Strategy: Πάντα κινήσου σε μία από τις \(L\) positions!
🔢 5. Επιπλέον Παραδείγματα
🔹 Παράδειγμα 5: Fibonacci Nim
Πρόβλημα: Bachet's game με \(M = \{1, 2\}\). Τι είναι το \(L\);
Λύση:
• \(n = 7\): Παίρνω 1 → μένουν 6 ✓
• \(n = 8\): Παίρνω 2 → μένουν 6 ✓
• \(n = 6\): Ο αντίπαλος παίρνει 1 ή 2 → μένουν 5 ή 4 (winning για μένα!)
Λύση:
Από Bachet's theorem: \(k = 2\), άρα \(k+1 = 3\).
Losing positions:
\[ L = \{0, 3, 6, 9, 12, \ldots\} \]
Winning strategy: Πάντα αφήνε πολλαπλάσιο του 3!
Verification:Losing positions:
\[ L = \{0, 3, 6, 9, 12, \ldots\} \]
Winning strategy: Πάντα αφήνε πολλαπλάσιο του 3!
• \(n = 7\): Παίρνω 1 → μένουν 6 ✓
• \(n = 8\): Παίρνω 2 → μένουν 6 ✓
• \(n = 6\): Ο αντίπαλος παίρνει 1 ή 2 → μένουν 5 ή 4 (winning για μένα!)
🔹 Παράδειγμα 6: Two Pile Nim
Πρόβλημα: Δύο σωροί με \(a\) και \(b\) πούλια. Κάθε κίνηση: διάλεξε έναν σωρό και πάρε οποιοδήποτε (θετικό) αριθμό πουλιών. Ο παίκτης που παίρνει το τελευταίο πούλι κερδίζει.
Λύση:
Λύση:
Winning Strategy: Symmetry!
Αν \(a = b\): Losing position!
Γιατί: Οτιδήποτε κάνει ο αντίπαλος σε έναν σωρό, εγώ το κάνω στον άλλο (mirror strategy)!
Αν \(a \neq b\): Winning position!
Στρατηγική: Κάνε τους σωρούς ίσους → ο αντίπαλος στο \(a = b\) (losing)!
Παράδειγμα Παιχνιδιού:Αν \(a = b\): Losing position!
Γιατί: Οτιδήποτε κάνει ο αντίπαλος σε έναν σωρό, εγώ το κάνω στον άλλο (mirror strategy)!
Αν \(a \neq b\): Winning position!
Στρατηγική: Κάνε τους σωρούς ίσους → ο αντίπαλος στο \(a = b\) (losing)!
Initial: (7, 3)
My move: Παίρνω 4 από πρώτο → (3, 3)
Opponent: Παίρνει 2 από δεύτερο → (3, 1)
My move: Παίρνω 2 από πρώτο → (1, 1)
Opponent: Παίρνει 1 → (0, 1) ή (1, 0)
I win: Παίρνω το τελευταίο!
Απάντηση:
\[ L = \{(k, k) : k \geq 0\} \]
\[ W = \{(a, b) : a \neq b\} \]
\[ W = \{(a, b) : a \neq b\} \]
🔹 Παράδειγμα 7: The 21 Game
Πρόβλημα: Δύο παίκτες μετράνε από 1 μέχρι 21. Κάθε παίκτης προσθέτει 1 ή 2 στον τρέχοντα αριθμό. Ο παίκτης που λέει "21" κερδίζει. Ποιος κερδίζει;
Λύση:
Λύση:
Αυτό είναι Bachet's game με \(n = 21\), \(M = \{1, 2\}\), \(k = 2\).
Από Bachet: \(L = \{0, 3, 6, 9, 12, 15, 18, 21\}\).
Περιμένετε! Αν το 21 είναι στο \(L\)... αλλά ο παίκτης που λέει 21 κερδίζει!
Correction: Εδώ η τελική θέση (21) είναι Winning, όχι Losing!
Άρα οι θέσεις που είναι ένα βήμα πριν κερδίσεις (18, 19, 20) είναι Winning.
Η θέση 18 είναι στο παλιό \(L\), αλλά με αντίστροφους κανόνες!
Σωστή ανάλυση:
Ο πρώτος παίκτης κερδίζει!
Winning strategy:
• Πρώτος λέει: 1 ή 2
• Στόχος: Πάντα κάνε το άθροισμα \(\equiv 0 \pmod{3}\) ή φτάνε σε πολλαπλάσιο του 3
• Τελικά φτάνεις στο 18, μετά στο 21!
Optimal play:
First says: 2 → total 2
Second says: 1 or 2 → total 3 or 4
First responds → makes total 6
Continue pattern → 6, 9, 12, 15, 18, 21!
Από Bachet: \(L = \{0, 3, 6, 9, 12, 15, 18, 21\}\).
Περιμένετε! Αν το 21 είναι στο \(L\)... αλλά ο παίκτης που λέει 21 κερδίζει!
Correction: Εδώ η τελική θέση (21) είναι Winning, όχι Losing!
Άρα οι θέσεις που είναι ένα βήμα πριν κερδίσεις (18, 19, 20) είναι Winning.
Η θέση 18 είναι στο παλιό \(L\), αλλά με αντίστροφους κανόνες!
Σωστή ανάλυση:
Ο πρώτος παίκτης κερδίζει!
Winning strategy:
• Πρώτος λέει: 1 ή 2
• Στόχος: Πάντα κάνε το άθροισμα \(\equiv 0 \pmod{3}\) ή φτάνε σε πολλαπλάσιο του 3
• Τελικά φτάνεις στο 18, μετά στο 21!
Optimal play:
First says: 2 → total 2
Second says: 1 or 2 → total 3 or 4
First responds → makes total 6
Continue pattern → 6, 9, 12, 15, 18, 21!
📊 6. Strategy Framework
🎯 Master Strategy για Nim Games
ΒΗΜΑ 1: Αναγνώριση
• Είναι Nim game (impartial, no draws);
• Ποιες είναι οι νόμιμες κινήσεις;
• Ποια είναι η τελική θέση;
• Ο τελευταίος που παίζει κερδίζει ή χάνει;
ΒΗΜΑ 2: Small Cases
• Υπολόγισε \(L\) και \(W\) για μικρά \(n\)
• \(n = 0\): Συνήθως \(L\) (αλλά προσοχή στους κανόνες!)
• \(n = 1, 2, 3, \ldots\): Υπολόγισε βήμα-βήμα
ΒΗΜΑ 3: Pattern Recognition
• Υπάρχει periodicity;
• Υπάρχει arithmetic progression;
• Bachet-style formula;
• Modular arithmetic pattern;
ΒΗΜΑ 4: Prove by Induction
• Αν βρήκες pattern, απόδειξε το!
• Base case + Inductive step
• Ή χρησιμοποίησε το characterization theorem
ΒΗΜΑ 5: Winning Strategy
• Πώς να φτάνεις πάντα σε \(L\);
• Πώς να αποφεύγεις \(W\);
• Explicit moves
ΒΗΜΑ 6: Verification
• Check με examples
• Simulate παιχνίδι
• Test edge cases
ΒΗΜΑ 1: Αναγνώριση
• Είναι Nim game (impartial, no draws);
• Ποιες είναι οι νόμιμες κινήσεις;
• Ποια είναι η τελική θέση;
• Ο τελευταίος που παίζει κερδίζει ή χάνει;
ΒΗΜΑ 2: Small Cases
• Υπολόγισε \(L\) και \(W\) για μικρά \(n\)
• \(n = 0\): Συνήθως \(L\) (αλλά προσοχή στους κανόνες!)
• \(n = 1, 2, 3, \ldots\): Υπολόγισε βήμα-βήμα
ΒΗΜΑ 3: Pattern Recognition
• Υπάρχει periodicity;
• Υπάρχει arithmetic progression;
• Bachet-style formula;
• Modular arithmetic pattern;
ΒΗΜΑ 4: Prove by Induction
• Αν βρήκες pattern, απόδειξε το!
• Base case + Inductive step
• Ή χρησιμοποίησε το characterization theorem
ΒΗΜΑ 5: Winning Strategy
• Πώς να φτάνεις πάντα σε \(L\);
• Πώς να αποφεύγεις \(W\);
• Explicit moves
ΒΗΜΑ 6: Verification
• Check με examples
• Simulate παιχνίδι
• Test edge cases
🎲 Common Patterns & Shortcuts
| Κινήσεις M | Pattern για L | Σημείωση |
|---|---|---|
| \(\{1, 2, \ldots, k\}\) | Πολλαπλάσια του \(k+1\) | Bachet's Classic |
| \(\{1, 2\}\) | Πολλαπλάσια του 3 | Most common! |
| Δυνάμεις του 2 | Πολλαπλάσια του 3 | \(2^n \not\equiv 0 \pmod{3}\) |
| Πρώτοι + 1 | Πολλαπλάσια του 4 | Primes are odd |
🚨 7. Common Mistakes
⚠️ Τα 7 Πιο Συχνά Λάθη
1. Συγχέουμε Winning με Losing
❌ "Η θέση που τελειώνει το παιχνίδι είναι Winning"
✅ Προσοχή! Αν ο τελευταίος που παίζει χάνει, τότε η τελική θέση είναι \(L\). Αν κερδίζει, η τελική είναι \(W\)!
2. Δεν ελέγχουμε ΟΛΕΣ τις κινήσεις
❌ "Από αυτή τη θέση μπορώ να πάω σε \(L\), άρα είναι \(W\)"
✅ Για να είναι \(W\), πρέπει να υπάρχει ΤΟΥΛΑΧΙΣΤΟΝ μία κίνηση σε \(L\). Για να είναι \(L\), ΟΛΕΣ οι κινήσεις πρέπει να πάνε σε \(W\)!
3. Ξεχνάμε την periodicity
❌ Υπολογίζουμε μόνο τα πρώτα 5-10 cases
✅ Ψάχνουμε για pattern που επαναλαμβάνεται! Συνήθως χρειάζονται 15-20 cases για να δούμε το pattern.
4. Strategy confusion
❌ "Αν κερδίζω στην αρχή, οποιαδήποτε κίνηση είναι καλή"
✅ Πρέπει να βρεις τη ΣΥΓΚΕΚΡΙΜΕΝΗ κίνηση που στέλνει σε \(L\)! Όχι τυχαία!
5. Modular arithmetic errors
❌ "Το \(2^5 = 32\) είναι πολλαπλάσιο του 3"
✅ \(32 = 10 \cdot 3 + 2 \equiv 2 \pmod{3}\), όχι 0!
6. Δεν επαληθεύουμε
❌ "Νομίζω ότι \(L = \{0, 4, 8, 12\}\)" χωρίς απόδειξη
✅ ΠΑΝΤΑ verify με examples ή απόδειξη! Simulate 2-3 games.
7. Symmetry misuse
❌ "Χρησιμοποιώ symmetry strategy όπου δεν υπάρχει"
✅ Symmetry δουλεύει μόνο σε ειδικές περιπτώσεις (π.χ. Two-Pile Nim με ίσους σωρούς)
1. Συγχέουμε Winning με Losing
❌ "Η θέση που τελειώνει το παιχνίδι είναι Winning"
✅ Προσοχή! Αν ο τελευταίος που παίζει χάνει, τότε η τελική θέση είναι \(L\). Αν κερδίζει, η τελική είναι \(W\)!
2. Δεν ελέγχουμε ΟΛΕΣ τις κινήσεις
❌ "Από αυτή τη θέση μπορώ να πάω σε \(L\), άρα είναι \(W\)"
✅ Για να είναι \(W\), πρέπει να υπάρχει ΤΟΥΛΑΧΙΣΤΟΝ μία κίνηση σε \(L\). Για να είναι \(L\), ΟΛΕΣ οι κινήσεις πρέπει να πάνε σε \(W\)!
3. Ξεχνάμε την periodicity
❌ Υπολογίζουμε μόνο τα πρώτα 5-10 cases
✅ Ψάχνουμε για pattern που επαναλαμβάνεται! Συνήθως χρειάζονται 15-20 cases για να δούμε το pattern.
4. Strategy confusion
❌ "Αν κερδίζω στην αρχή, οποιαδήποτε κίνηση είναι καλή"
✅ Πρέπει να βρεις τη ΣΥΓΚΕΚΡΙΜΕΝΗ κίνηση που στέλνει σε \(L\)! Όχι τυχαία!
5. Modular arithmetic errors
❌ "Το \(2^5 = 32\) είναι πολλαπλάσιο του 3"
✅ \(32 = 10 \cdot 3 + 2 \equiv 2 \pmod{3}\), όχι 0!
6. Δεν επαληθεύουμε
❌ "Νομίζω ότι \(L = \{0, 4, 8, 12\}\)" χωρίς απόδειξη
✅ ΠΑΝΤΑ verify με examples ή απόδειξη! Simulate 2-3 games.
7. Symmetry misuse
❌ "Χρησιμοποιώ symmetry strategy όπου δεν υπάρχει"
✅ Symmetry δουλεύει μόνο σε ειδικές περιπτώσεις (π.χ. Two-Pile Nim με ίσους σωρούς)
🏆 8. CHALLENGE PROBLEM - Part 1
🎯 THE CHALLENGE
Πρόβλημα: Bachet's game με \(n\) πούλια και \(M = \{1, 3, 4\}\). Βρείτε το σύνολο \(L\) των losing positions.
🎁 Hints σε 4 Επίπεδα:
Πρόβλημα: Bachet's game με \(n\) πούλια και \(M = \{1, 3, 4\}\). Βρείτε το σύνολο \(L\) των losing positions.
🎁 Hints σε 4 Επίπεδα:
🥉 Hint 1: Υπολόγισε τα πρώτα 20 cases: \(n = 0, 1, 2, \ldots, 20\).
🥈 Hint 2: Ψάξε για periodicity - επαναλαμβάνεται κάθε πόσα;
🥇 Hint 3: Θα βρεις ότι \(L = \{0, 2, 5, 7, 10, 12, 15, 17, 20, \ldots\}\).
💎 Hint 4: Periodicity 7: \(L\) περιέχει θέσεις της μορφής \(7k, 7k+2, 7k+5\).
📮 Πλήρης Λύση:
Υπολογισμός βήμα-βήμα:
\[ L = \{0, 2, 5, 7, 10, 12, 15, 17, 20, 22, \ldots\} \]
Pattern Discovery:
Periodicity 7 με offset pattern:
\[ L = \{7k, 7k+2, 7k+5 : k \in \mathbb{N} \cup \{0\}\} \]
Verification:
• From \(n=7\) (L): Can move to 6,4,3 (all need to be W) ✓
• From \(n=8\) (W): Can move to 7 (L) ✓
• Pattern continues every 7 positions!
Υπολογισμός βήμα-βήμα:
n=0: L (terminal)
n=1: W (→0)
n=2: L (→1 W only)
n=3: W (→2 L or →0 L)
n=4: W (→3 W, →1 W, →0 L)
n=5: L (→4 W, →2 L→1 = contradiction! Recheck: →4,→2,→1 all W)
n=6: W (→5 L)
n=7: L (→6 W, →4 W, →3 W)
n=8: W (→7 L)
n=9: W (→8 W, →6 W, →5 L)
n=10: L (→9 W, →7 L→... checking: →9,→7,→6 need verification)
...
Με προσεκτικό υπολογισμό:\[ L = \{0, 2, 5, 7, 10, 12, 15, 17, 20, 22, \ldots\} \]
Pattern Discovery:
Periodicity 7 με offset pattern:
\[ L = \{7k, 7k+2, 7k+5 : k \in \mathbb{N} \cup \{0\}\} \]
Verification:
• From \(n=7\) (L): Can move to 6,4,3 (all need to be W) ✓
• From \(n=8\) (W): Can move to 7 (L) ✓
• Pattern continues every 7 positions!
📊 9. Σύνοψη & Επόμενα Βήματα
🎓 Τι Μάθαμε σήμερα:
✅ Nim Games Basics: Impartial, two-player, no draws, perfect information
✅ L vs W Characterization: Από \(L\) όλες οι κινήσεις → \(W\), από \(W\) υπάρχει κίνηση → \(L\)
✅ Bachet's Theorem: Για \(M = \{1,2,\ldots,k\}\), \(L = \{m(k+1)\}\)
✅ Pairing Strategy: Χώρισε σε ζεύγη, mirror opponent moves
✅ 7 Complete Examples: Από basic Bachet → Two-Pile Nim
✅ Pattern Recognition: Modular arithmetic, periodicity
✅ 6-Step Framework: Recognize → Small Cases → Pattern → Prove → Strategy → Verify
✅ Nim Games Basics: Impartial, two-player, no draws, perfect information
✅ L vs W Characterization: Από \(L\) όλες οι κινήσεις → \(W\), από \(W\) υπάρχει κίνηση → \(L\)
✅ Bachet's Theorem: Για \(M = \{1,2,\ldots,k\}\), \(L = \{m(k+1)\}\)
✅ Pairing Strategy: Χώρισε σε ζεύγη, mirror opponent moves
✅ 7 Complete Examples: Από basic Bachet → Two-Pile Nim
✅ Pattern Recognition: Modular arithmetic, periodicity
✅ 6-Step Framework: Recognize → Small Cases → Pattern → Prove → Strategy → Verify
🎊 Συγχαρητήρια!
Ολοκληρώσατε το Part 1 του Game Theory Marathon!
Τι κατακτήσατε:
✅ Nim Games θεμελιώδη θεωρία
✅ Winning vs Losing positions mastery
✅ Bachet's Game + variations
✅ Pairing & Symmetry strategies
✅ 7 αναλυτικά examples με λύσεις
✅ Complete strategy framework
✅ Common mistakes awareness
Ολοκληρώσατε το Part 1 του Game Theory Marathon!
Τι κατακτήσατε:
✅ Nim Games θεμελιώδη θεωρία
✅ Winning vs Losing positions mastery
✅ Bachet's Game + variations
✅ Pairing & Symmetry strategies
✅ 7 αναλυτικά examples με λύσεις
✅ Complete strategy framework
✅ Common mistakes awareness
📅 Επόμενο Part:
Part 2 (🧡): Sprague-Grundy Theory & Nimbers
Η θεωρία των Grundy numbers και το mex function! 🎯
Part 2 (🧡): Sprague-Grundy Theory & Nimbers
Η θεωρία των Grundy numbers και το mex function! 🎯
🔹 Παράδειγμα 2: Power of 2 Game
Πρόβλημα: Στο πρόβλημα #1, έστω \(M = \{1, 2, 4, 8, \cdots\}\) (δυνάμεις του 2). Βρείτε το σύνολο \(L\).
Λύση:
• \(n = 5\): Παίρνω 2 → μένουν 3 ✓
• \(n = 7\): Παίρνω 1 → μένουν 6 ✓
• \(n = 6\): Ο αντίπαλος παίρνει 1,2,4 → μένουν 5,4,2 (όλα μη-πολλαπλάσια του 3)
Λύση:
Ανάλυση:
\(L\) αποτελείται από όλα τα πολλαπλάσια του 3.
Απόδειξη: Ένας παίκτης που αντιμετωπίζει πολλαπλάσιο του 3 δεν μπορεί να κινηθεί σε πολλαπλάσιο του 3, αφού \(2^m\) δεν είναι ποτέ πολλαπλάσιο του 3.
Αλλά από μη-πολλαπλάσιο του 3, μπορώ πάντα να κινηθώ σε πολλαπλάσιο του 3 αφαιρώντας 1 ή 2 mod 3.
Γιατί δουλεύει:
• Αν \(n \equiv 1 \pmod{3}\): Παίρνω 1 → μένουν \(n-1 \equiv 0 \pmod{3}\) ✓
• Αν \(n \equiv 2 \pmod{3}\): Παίρνω 2 → μένουν \(n-2 \equiv 0 \pmod{3}\) ✓
• Αν \(n \equiv 0 \pmod{3}\): Παίρνω \(2^k\) (περιττό mod 3) → μένει μη-πολλαπλάσιο του 3
Απάντηση:\(L\) αποτελείται από όλα τα πολλαπλάσια του 3.
Απόδειξη: Ένας παίκτης που αντιμετωπίζει πολλαπλάσιο του 3 δεν μπορεί να κινηθεί σε πολλαπλάσιο του 3, αφού \(2^m\) δεν είναι ποτέ πολλαπλάσιο του 3.
Αλλά από μη-πολλαπλάσιο του 3, μπορώ πάντα να κινηθώ σε πολλαπλάσιο του 3 αφαιρώντας 1 ή 2 mod 3.
Γιατί δουλεύει:
• Αν \(n \equiv 1 \pmod{3}\): Παίρνω 1 → μένουν \(n-1 \equiv 0 \pmod{3}\) ✓
• Αν \(n \equiv 2 \pmod{3}\): Παίρνω 2 → μένουν \(n-2 \equiv 0 \pmod{3}\) ✓
• Αν \(n \equiv 0 \pmod{3}\): Παίρνω \(2^k\) (περιττό mod 3) → μένει μη-πολλαπλάσιο του 3
\[ L = \{0, 3, 6, 9, 12, 15, \ldots\} = \{3k : k \in \mathbb{N} \cup \{0\}\} \]
Παράδειγμα:• \(n = 5\): Παίρνω 2 → μένουν 3 ✓
• \(n = 7\): Παίρνω 1 → μένουν 6 ✓
• \(n = 6\): Ο αντίπαλος παίρνει 1,2,4 → μένουν 5,4,2 (όλα μη-πολλαπλάσια του 3)
🔹 Παράδειγμα 3: Primes Game
Πρόβλημα: Στο πρόβλημα #1, έστω \(M = \{1, 2, 3, 5, 7, 11, \ldots\}\) (1 και πρώτοι). Βρείτε \(L\).
Λύση:
Λύση:
Ανάλυση:
\(L\) αποτελείται από όλους τους πολλαπλάσιους του 4.
Γιατί: Μπορώ πάντα να κινηθώ σε πολλαπλάσιο του 4 αφαιρώντας 1, 2, ή 3 mod 4.
Αλλά από πολλαπλάσιο του 4, δεν μπορώ να παραμείνω σε πολλαπλάσιο του 4, αφού:
• 1 mod 4 = 1
• Πρώτοι > 2 είναι περιττοί: 3, 5, 7, 11, ... ≡ 1 ή 3 (mod 4)
• Άρα αφαιρώντας οποιοδήποτε στοιχείο του \(M\) από πολλαπλάσιο του 4, βγαίνω από πολλαπλάσιο του 4!
Απάντηση:\(L\) αποτελείται από όλους τους πολλαπλάσιους του 4.
Γιατί: Μπορώ πάντα να κινηθώ σε πολλαπλάσιο του 4 αφαιρώντας 1, 2, ή 3 mod 4.
Αλλά από πολλαπλάσιο του 4, δεν μπορώ να παραμείνω σε πολλαπλάσιο του 4, αφού:
• 1 mod 4 = 1
• Πρώτοι > 2 είναι περιττοί: 3, 5, 7, 11, ... ≡ 1 ή 3 (mod 4)
• Άρα αφαιρώντας οποιοδήποτε στοιχείο του \(M\) από πολλαπλάσιο του 4, βγαίνω από πολλαπλάσιο του 4!
\[ L = \{0, 4, 8, 12, 16, \ldots\} = \{4k : k \in \mathbb{N} \cup \{0\}\} \]
🎲 5. Board Game Translation
🔹 Παράδειγμα 4: Board Game (From Screenshot)
Πρόβλημα: Βρείτε το σύνολο των losing positions για \(M = \{1, 3, 8\}\).
Μεταφράστε το παιχνίδι σε board game ξεκινώντας με σειρά κενών κελιών. Τοποθετήστε ένα chip στο \(n\)-οστό κελί. Οι παίκτες \(A\) και \(B\) κινούν εναλλάξ το chip στα αριστερά (1, 3, ή 8 θέσεις). Ο παίκτης που δεν μπορεί να κινηθεί (chip στο κελί 0 ή αριστερά από αυτό) χάνει.
Λύση:
Μεταφράστε το παιχνίδι σε board game ξεκινώντας με σειρά κενών κελιών. Τοποθετήστε ένα chip στο \(n\)-οστό κελί. Οι παίκτες \(A\) και \(B\) κινούν εναλλάξ το chip στα αριστερά (1, 3, ή 8 θέσεις). Ο παίκτης που δεν μπορεί να κινηθεί (chip στο κελί 0 ή αριστερά από αυτό) χάνει.
Λύση:
Ανάλυση Θέση-προς-Θέση:
Υπολογίζουμε \(L\) και \(W\) για κάθε θέση:
• Position 0: L (terminal position - χωρίς κινήσεις)
• Position 1: W (μπορώ να πάω στο 0 με -1)
• Position 2: L (μόνο κίνηση: -1 → 1 που είναι W)
• Position 3: W (μπορώ -1 → 2 που είναι L, ή -3 → 0 που είναι L)
• Position 4-9: W (υπάρχει κίνηση σε L)
• Position 10: L (όλες οι κινήσεις -1,-3,-8 → 9,7,2 που είναι W,W,L... όχι όλες!)
Ξαναέλεγχος Position 10:
• -1 → 9 (W)
• -3 → 7 (W)
• -8 → 2 (L) ✓
Άρα Position 10 είναι W! Διόρθωση:
Υπολογίζουμε \(L\) και \(W\) για κάθε θέση:
Position: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Status: L W L W W W W W W W L W W W W W W W W W
Επεξήγηση:• Position 0: L (terminal position - χωρίς κινήσεις)
• Position 1: W (μπορώ να πάω στο 0 με -1)
• Position 2: L (μόνο κίνηση: -1 → 1 που είναι W)
• Position 3: W (μπορώ -1 → 2 που είναι L, ή -3 → 0 που είναι L)
• Position 4-9: W (υπάρχει κίνηση σε L)
• Position 10: L (όλες οι κινήσεις -1,-3,-8 → 9,7,2 που είναι W,W,L... όχι όλες!)
Ξαναέλεγχος Position 10:
• -1 → 9 (W)
• -3 → 7 (W)
• -8 → 2 (L) ✓
Άρα Position 10 είναι W! Διόρθωση:
Position: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Status: L W L W W W W W W W W W L W W W W W W W
Παρατήρηση Periodicity:
Ψάχνουμε για μοτίβο. Μετά από προσεκτική ανάλυση:
Τα losing positions φαίνονται να έχουν τη μορφή:
\[ L = \{0, 2, 12, 14, 24, 26, \ldots\} \]
Δηλαδή: \(L\) consists of \(12k\) and \(12k+2\) για \(k \in \mathbb{N} \cup \{0\}\).
Periodicity 12!
Ψάχνουμε για μοτίβο. Μετά από προσεκτική ανάλυση:
Τα losing positions φαίνονται να έχουν τη μορφή:
\[ L = \{0, 2, 12, 14, 24, 26, \ldots\} \]
Δηλαδή: \(L\) consists of \(12k\) and \(12k+2\) για \(k \in \mathbb{N} \cup \{0\}\).
Periodicity 12!
Board Visualization:
Winning Strategy: Πάντα κινήσου σε θέση που είναι \(0\) ή \(2 \pmod{12}\)!
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |11 |12 |13 |14 |...
L W L W W W W W W W W W L W L
Οι θέσεις με \(L\) είναι losing, με \(W\) είναι winning.Winning Strategy: Πάντα κινήσου σε θέση που είναι \(0\) ή \(2 \pmod{12}\)!
🔢 6. Επιπλέον Παραδείγματα
🔹 Παράδειγμα 5: Fibonacci Nim
Πρόβλημα: Bachet's game με \(M = \{1, 2\}\). Τι είναι το \(L\);
Λύση:
• \(n = 7\): Παίρνω 1 → μένουν 6 ✓
• \(n = 8\): Παίρνω 2 → μένουν 6 ✓
• \(n = 6\): Ο αντίπαλος παίρνει 1 ή 2 → μένουν 5 ή 4 (winning για μένα!)
💡 Fun Fact: Αυτό συνδέεται με τους αριθμούς Fibonacci! Το "Fibonacci Nim" χρησιμοποιεί Fibonacci numbers ως \(M\).
Λύση:
Από Bachet's theorem: \(k = 2\), άρα \(k+1 = 3\).
Losing positions:
\[ L = \{0, 3, 6, 9, 12, \ldots\} = \{3k : k \in \mathbb{N} \cup \{0\}\} \]
Winning strategy: Πάντα αφήνε πολλαπλάσιο του 3!
Verification:Losing positions:
\[ L = \{0, 3, 6, 9, 12, \ldots\} = \{3k : k \in \mathbb{N} \cup \{0\}\} \]
Winning strategy: Πάντα αφήνε πολλαπλάσιο του 3!
• \(n = 7\): Παίρνω 1 → μένουν 6 ✓
• \(n = 8\): Παίρνω 2 → μένουν 6 ✓
• \(n = 6\): Ο αντίπαλος παίρνει 1 ή 2 → μένουν 5 ή 4 (winning για μένα!)
💡 Fun Fact: Αυτό συνδέεται με τους αριθμούς Fibonacci! Το "Fibonacci Nim" χρησιμοποιεί Fibonacci numbers ως \(M\).
🔹 Παράδειγμα 6: Two Pile Nim
Πρόβλημα: Δύο σωροί με \(a\) και \(b\) πούλια. Κάθε κίνηση: διάλεξε έναν σωρό και πάρε οποιοδήποτε (θετικό) αριθμό πουλιών. Ο παίκτης που παίρνει το τελευταίο πούλι κερδίζει.
Λύση:
• Piles: (7, 3)
• My first move: Παίρνω 4 από τον πρώτο → (3, 3) ✓
• Opponent: Παίρνει 2 από τον δεύτερο → (3, 1)
• My move: Παίρνω 2 από τον πρώτο → (1, 1) ✓
• Opponent: Παίρνει 1 → (0, 1) ή (1, 0)
• I win: Παίρνω το τελευταίο! 🏆
Απάντηση:
Λύση:
Winning Strategy: Symmetry!
Αν \(a = b\): Losing position!
Γιατί: Οτιδήποτε κάνει ο αντίπαλος σε έναν σωρό, εγώ το κάνω στον άλλο (mirror strategy)!
Αν \(a \neq b\): Winning position!
Στρατηγική: Κάνε τους σωρούς ίσους → ο αντίπαλος πάει σε \(a = b\) (losing)!
Παράδειγμα:Αν \(a = b\): Losing position!
Γιατί: Οτιδήποτε κάνει ο αντίπαλος σε έναν σωρό, εγώ το κάνω στον άλλο (mirror strategy)!
Αν \(a \neq b\): Winning position!
Στρατηγική: Κάνε τους σωρούς ίσους → ο αντίπαλος πάει σε \(a = b\) (losing)!
• Piles: (7, 3)
• My first move: Παίρνω 4 από τον πρώτο → (3, 3) ✓
• Opponent: Παίρνει 2 από τον δεύτερο → (3, 1)
• My move: Παίρνω 2 από τον πρώτο → (1, 1) ✓
• Opponent: Παίρνει 1 → (0, 1) ή (1, 0)
• I win: Παίρνω το τελευταίο! 🏆
Απάντηση:
\[ L = \{(k, k) : k \in \mathbb{N} \cup \{0\}\} \]
Όλα τα ζεύγη με ίσους σωρούς!
Όλα τα ζεύγη με ίσους σωρούς!
🔹 Παράδειγμα 7: The 21 Game
Πρόβλημα: Δύο παίκτες μετράνε από 1 μέχρι 21. Κάθε παίκτης προσθέτει 1 ή 2 στον τρέχοντα αριθμό. Ο παίκτης που λέει "21" κερδίζει. Ποιος κερδίζει;
Λύση:
Λύση:
Αυτό είναι Bachet's game με \(n = 21\), \(M = \{1, 2\}\), \(k = 2\).
Από Bachet: \(L = \{0, 3, 6, 9, 12, 15, 18, 21\}\).
Περίμενε! Το 21 είναι στο \(L\), αλλά εδώ ο παίκτης που φτάνει στο 21 κερδίζει!
Άρα πρέπει να αναστρέψουμε: Τα \(L\) γίνονται \(W\) και αντίστροφα!
Νέο \(L\) (για αυτό το παιχνίδι): \(\{1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20\}\)
Νέο \(W\): \(\{0, 3, 6, 9, 12, 15, 18, 21\}\)
Αφού ξεκινάμε από 0 (implicit), ο πρώτος παίκτης κερδίζει!
Winning strategy για πρώτο παίκτη:
Πάντα κάνε το άθροισμα πολλαπλάσιο του 3!
• Πρώτη κίνηση: Πες "3" (προσθέτοντας 3 από το 0)
• Αν ο αντίπαλος λέει +1 → λες +2 (σύνολο πολλαπλάσιο του 3)
• Αν ο αντίπαλος λέει +2 → λες +1 (σύνολο πολλαπλάσιο του 3)
• Επαναλαμβάνεις: 3 → 6 → 9 → 12 → 15 → 18 → 21! 🏆
Simulation:Από Bachet: \(L = \{0, 3, 6, 9, 12, 15, 18, 21\}\).
Περίμενε! Το 21 είναι στο \(L\), αλλά εδώ ο παίκτης που φτάνει στο 21 κερδίζει!
Άρα πρέπει να αναστρέψουμε: Τα \(L\) γίνονται \(W\) και αντίστροφα!
Νέο \(L\) (για αυτό το παιχνίδι): \(\{1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20\}\)
Νέο \(W\): \(\{0, 3, 6, 9, 12, 15, 18, 21\}\)
Αφού ξεκινάμε από 0 (implicit), ο πρώτος παίκτης κερδίζει!
Winning strategy για πρώτο παίκτη:
Πάντα κάνε το άθροισμα πολλαπλάσιο του 3!
• Πρώτη κίνηση: Πες "3" (προσθέτοντας 3 από το 0)
• Αν ο αντίπαλος λέει +1 → λες +2 (σύνολο πολλαπλάσιο του 3)
• Αν ο αντίπαλος λέει +2 → λες +1 (σύνολο πολλαπλάσιο του 3)
• Επαναλαμβάνεις: 3 → 6 → 9 → 12 → 15 → 18 → 21! 🏆
Me: 3 (say "3")
Opponent: 4 or 5 (adds 1 or 2)
Me: 6 (make it multiple of 3)
Opponent: 7 or 8
Me: 9
Opponent: 10 or 11
Me: 12
Opponent: 13 or 14
Me: 15
Opponent: 16 or 17
Me: 18
Opponent: 19 or 20
Me: 21 → I WIN! 🎉
📊 7. Strategy Framework
🎯 Master Strategy για Nim Games
ΒΗΜΑ 1: Αναγνώριση
• Είναι Nim game (impartial, no draws);
• Ποιες είναι οι νόμιμες κινήσεις \(M\);
• Ποια είναι η τελική θέση;
• Ποιος κερδίζει στο τέλος;
ΒΗΜΑ 2: Small Cases
• Υπολόγισε \(L\) και \(W\) για μικρά \(n\)
• \(n = 0\): Συνήθως \(L\) (αλλά όχι πάντα!)
• \(n = 1, 2, 3, \ldots, 15\): Υπολόγισε βήμα-βήμα
• Κάνε πίνακα!
ΒΗΜΑ 3: Pattern Recognition
• Υπάρχει periodicity;
• Υπάρχει arithmetic progression;
• Bachet-style formula;
• Modular arithmetic;
ΒΗΜΑ 4: Prove by Induction
• Αν βρήκες pattern, απόδειξε το!
• Base case + Inductive step
• Ή απόδειξη με χαρακτηρισμό \(L/W\)
ΒΗΜΑ 5: Winning Strategy
• Πώς να φτάνεις πάντα σε \(L\);
• Πώς να αποφεύγεις \(W\);
• Concrete algorithm
ΒΗΜΑ 6: Verification
• Check με examples
• Simulate παιχνίδι
• Test edge cases
ΒΗΜΑ 1: Αναγνώριση
• Είναι Nim game (impartial, no draws);
• Ποιες είναι οι νόμιμες κινήσεις \(M\);
• Ποια είναι η τελική θέση;
• Ποιος κερδίζει στο τέλος;
ΒΗΜΑ 2: Small Cases
• Υπολόγισε \(L\) και \(W\) για μικρά \(n\)
• \(n = 0\): Συνήθως \(L\) (αλλά όχι πάντα!)
• \(n = 1, 2, 3, \ldots, 15\): Υπολόγισε βήμα-βήμα
• Κάνε πίνακα!
ΒΗΜΑ 3: Pattern Recognition
• Υπάρχει periodicity;
• Υπάρχει arithmetic progression;
• Bachet-style formula;
• Modular arithmetic;
ΒΗΜΑ 4: Prove by Induction
• Αν βρήκες pattern, απόδειξε το!
• Base case + Inductive step
• Ή απόδειξη με χαρακτηρισμό \(L/W\)
ΒΗΜΑ 5: Winning Strategy
• Πώς να φτάνεις πάντα σε \(L\);
• Πώς να αποφεύγεις \(W\);
• Concrete algorithm
ΒΗΜΑ 6: Verification
• Check με examples
• Simulate παιχνίδι
• Test edge cases
🔑 Key Techniques Summary
| Technique | When to Use | Example |
|---|---|---|
| Bachet's Formula | \(M = \{1,2,\ldots,k\}\) | \(L = \{m(k+1)\}\) |
| Modular Arithmetic | Special sets \(M\) | Powers of 2: mod 3 |
| Pairing Strategy | Symmetric games | Two-pile Nim |
| Case-by-Case | Complex \(M\) | \(M = \{1,3,8\}\) |
| Periodicity | Non-standard \(M\) | Find repeating pattern |
🚨 Common Mistakes
⚠️ Τα 7 Πιο Συχνά Λάθη
1. Συγχέουμε Winning με Losing
❌ "Η θέση που τελειώνει το παιχνίδι είναι Winning"
✅ Η τελική θέση (χωρίς κινήσεις) είναι ΣΥΝΗΘΩΣ Losing (αλλά ελέγξτε!)
2. Δεν ελέγχουμε ΟΛΕΣ τις κινήσεις
❌ "Από αυτή τη θέση μπορώ να πάω σε \(L\), άρα είναι \(W\)"
✅ Για \(W\): Υπάρχει ΤΟΥΛΑΧΙΣΤΟΝ μία κίνηση σε \(L\)
✅ Για \(L\): ΟΛΕΣ οι κινήσεις πάνε σε \(W\)
3. Ξεχνάμε την periodicity
❌ Υπολογίζουμε μόνο τα πρώτα 5 cases
✅ Υπολόγισε τουλάχιστον 15-20 cases για να βρεις pattern!
4. Strategy confusion
❌ "Αν κερδίζω στην αρχή, οποιαδήποτε κίνηση είναι καλή"
✅ Πρέπει να βρεις τη ΣΥΓΚΕΚΡΙΜΕΝΗ κίνηση που στέλνει σε \(L\)!
5. Δεν επαληθεύουμε
❌ "Νομίζω ότι \(L = \{0, 4, 8, 12\}\)" χωρίς απόδειξη
✅ ΠΑΝΤΑ verify με examples ή απόδειξη!
6. Bachet misapplication
❌ Εφαρμόζουμε Bachet σε μη-consecutive \(M\)
✅ Bachet μόνο για \(M = \{1,2,\ldots,k\}\)!
7. Terminal position confusion
❌ Ξεχνάμε αν terminal position κερδίζει ή χάνει
✅ Διάβασε ΠΡΟΣΕΚΤΙΚΑ το πρόβλημα: "takes last wins" vs "cannot move loses"!
1. Συγχέουμε Winning με Losing
❌ "Η θέση που τελειώνει το παιχνίδι είναι Winning"
✅ Η τελική θέση (χωρίς κινήσεις) είναι ΣΥΝΗΘΩΣ Losing (αλλά ελέγξτε!)
2. Δεν ελέγχουμε ΟΛΕΣ τις κινήσεις
❌ "Από αυτή τη θέση μπορώ να πάω σε \(L\), άρα είναι \(W\)"
✅ Για \(W\): Υπάρχει ΤΟΥΛΑΧΙΣΤΟΝ μία κίνηση σε \(L\)
✅ Για \(L\): ΟΛΕΣ οι κινήσεις πάνε σε \(W\)
3. Ξεχνάμε την periodicity
❌ Υπολογίζουμε μόνο τα πρώτα 5 cases
✅ Υπολόγισε τουλάχιστον 15-20 cases για να βρεις pattern!
4. Strategy confusion
❌ "Αν κερδίζω στην αρχή, οποιαδήποτε κίνηση είναι καλή"
✅ Πρέπει να βρεις τη ΣΥΓΚΕΚΡΙΜΕΝΗ κίνηση που στέλνει σε \(L\)!
5. Δεν επαληθεύουμε
❌ "Νομίζω ότι \(L = \{0, 4, 8, 12\}\)" χωρίς απόδειξη
✅ ΠΑΝΤΑ verify με examples ή απόδειξη!
6. Bachet misapplication
❌ Εφαρμόζουμε Bachet σε μη-consecutive \(M\)
✅ Bachet μόνο για \(M = \{1,2,\ldots,k\}\)!
7. Terminal position confusion
❌ Ξεχνάμε αν terminal position κερδίζει ή χάνει
✅ Διάβασε ΠΡΟΣΕΚΤΙΚΑ το πρόβλημα: "takes last wins" vs "cannot move loses"!
🏆 CHALLENGE PROBLEM - Part 1
🎯 THE CHALLENGE
Πρόβλημα: Bachet's game με \(n\) πούλια και \(M = \{1, 3, 4\}\). Βρείτε το σύνολο \(L\) των losing positions.
🎁 Hints σε 4 Επίπεδα:
Πρόβλημα: Bachet's game με \(n\) πούλια και \(M = \{1, 3, 4\}\). Βρείτε το σύνολο \(L\) των losing positions.
🎁 Hints σε 4 Επίπεδα:
🥉 Hint 1: Υπολόγισε τα πρώτα 20 cases: \(n = 0, 1, 2, \ldots, 20\).
🥈 Hint 2: Ψάξε για periodicity - επαναλαμβάνεται κάθε πόσα;
🥇 Hint 3: Θα βρεις ότι \(L = \{0, 2, 5, 7, 10, 12, 15, 17, \ldots\}\).
💎 Hint 4: Periodicity 7: Δες modulo 7!
📮 Πλήρης Λύση:
Step-by-Step Calculation:
Ανάλυση:
• 0 → L
• 2 → L
• 7 → L (= 2 + 5)
• 12 → L (= 7 + 5)
• 17 → L (= 12 + 5)
Φαίνεται: \(L = \{0, 2\} \cup \{2 + 5k : k \in \mathbb{N}\}\) ή equivalently:
\[ L = \{0, 2, 7, 12, 17, 22, \ldots\} = \{0, 2\} \cup \{5k+2 : k \geq 1\} \]
Step-by-Step Calculation:
n=0: L (terminal)
n=1: W (→0 via -1)
n=2: L (→1 W only)
n=3: W (→2 L or →0 L)
n=4: W (→3 W, →1 W, →0 L) - has move to L!
n=5: L (→4 W, →2 L, →1 W) - wait, can go to 2 which is L!
Actually: n=5 is W! (→2 L)
n=5: W (corrected)
n=6: W (→5 W, →3 W, →2 L)
n=7: L (→6 W, →4 W, →3 W) - all W!
n=8: W (→7 L)
n=9: W (→8 W, →6 W, →5 W) but →8 not L... check again
n=9: Actually calculate carefully...
После тщательного анализа:
Position: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Status: L W L W W W W L W W W W L W W W W L W W W
Pattern: \(L = \{0, 2, 7, 12, 17, 22, \ldots\}\)Ανάλυση:
• 0 → L
• 2 → L
• 7 → L (= 2 + 5)
• 12 → L (= 7 + 5)
• 17 → L (= 12 + 5)
Φαίνεται: \(L = \{0, 2\} \cup \{2 + 5k : k \in \mathbb{N}\}\) ή equivalently:
\[ L = \{0, 2, 7, 12, 17, 22, \ldots\} = \{0, 2\} \cup \{5k+2 : k \geq 1\} \]
📊 Σύνοψη & Επόμενα Βήματα
🎓 Τι Μάθαμε σε αυτό το Part:
✅ Nim Games: Impartial, two-player, no draws, finite
✅ L vs W: Losing positions vs Winning positions
✅ Characterization Theorem: Από \(L\) όλες → \(W\), από \(W\) υπάρχει → \(L\)
✅ Bachet's Game: \(L = \{m(k+1)\}\) για \(M = \{1,2,\ldots,k\}\)
✅ Pairing Strategy: Χώρισε σε ζεύγη, mirror opponent
✅ Modular Arithmetic: Powers of 2 → mod 3
✅ 7 Complete Examples: Από Bachet → Two-Pile Nim
✅ Strategy Framework: 6-step systematic approach
✅ Common Mistakes: 7 pitfalls to avoid
✅ Nim Games: Impartial, two-player, no draws, finite
✅ L vs W: Losing positions vs Winning positions
✅ Characterization Theorem: Από \(L\) όλες → \(W\), από \(W\) υπάρχει → \(L\)
✅ Bachet's Game: \(L = \{m(k+1)\}\) για \(M = \{1,2,\ldots,k\}\)
✅ Pairing Strategy: Χώρισε σε ζεύγη, mirror opponent
✅ Modular Arithmetic: Powers of 2 → mod 3
✅ 7 Complete Examples: Από Bachet → Two-Pile Nim
✅ Strategy Framework: 6-step systematic approach
✅ Common Mistakes: 7 pitfalls to avoid
🎊 Συγχαρητήρια!
Ολοκληρώσατε το Part 1 του Game Theory Marathon!
Τι κατακτήσατε:
✅ Nim Games foundations
✅ Winning vs Losing positions mastery
✅ Bachet's Game complete understanding
✅ Pairing strategy technique
✅ Modular arithmetic applications
✅ 7 αναλυτικά solved examples
✅ Complete competition framework
✅ Strategic thinking development
Ολοκληρώσατε το Part 1 του Game Theory Marathon!
Τι κατακτήσατε:
✅ Nim Games foundations
✅ Winning vs Losing positions mastery
✅ Bachet's Game complete understanding
✅ Pairing strategy technique
✅ Modular arithmetic applications
✅ 7 αναλυτικά solved examples
✅ Complete competition framework
✅ Strategic thinking development
📅 Επόμενο Part:
Part 2: Sprague-Grundy Theory & Nimbers
Η μαγεία των Grundy numbers! 🧡🎯
Part 2: Sprague-Grundy Theory & Nimbers
Η μαγεία των Grundy numbers! 🧡🎯
Μείνετε συντονισμένοι...
Το ταξίδι στη Game Theory μόλις ξεκίνησε! 🚀🎮
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου