.jpg)
🎮 2026 MATH MARATHON - GAME THEORY #3
Game Theory Mastery
Part 3: Advanced Strategies & Complex Games - Η Τέχνη της Συμμετρίας
🔗 Η Διαδρομή μας:
Part 1: Nim Games, L/W positions, Bachet's Game 💚
Part 2: Sprague-Grundy Theory, Nimbers, XOR 🧡
Part 3 (σήμερα): Advanced Strategies - The Art of Winning! 💙
Τι θα μάθετε σήμερα:
✅ Symmetry Strategy (η πιο elegant!)
✅ Pairing Technique (advanced)
✅ Partizan Games (διαφορετικοί κανόνες!)
✅ Graph Games & Green Hackenbush
✅ Strategy Stealing Argument
✅ Misère Game Strategies
✅ 7 complex examples
✅ Competition mastery
Part 1: Nim Games, L/W positions, Bachet's Game 💚
Part 2: Sprague-Grundy Theory, Nimbers, XOR 🧡
Part 3 (σήμερα): Advanced Strategies - The Art of Winning! 💙
Τι θα μάθετε σήμερα:
✅ Symmetry Strategy (η πιο elegant!)
✅ Pairing Technique (advanced)
✅ Partizan Games (διαφορετικοί κανόνες!)
✅ Graph Games & Green Hackenbush
✅ Strategy Stealing Argument
✅ Misère Game Strategies
✅ 7 complex examples
✅ Competition mastery
🎨 Η Φιλοσοφία του Part 3:
Στα Parts 1-2 μάθαμε τα θεμέλια. Τώρα μαθαίνουμε την τέχνη - πώς να σκεφτόμαστε στρατηγικά, πώς να βλέπουμε patterns, πώς να κερδίζουμε χωρίς υπολογισμούς! Αυτό είναι το Part που σας κάνει masters! 🎯
Στα Parts 1-2 μάθαμε τα θεμέλια. Τώρα μαθαίνουμε την τέχνη - πώς να σκεφτόμαστε στρατηγικά, πώς να βλέπουμε patterns, πώς να κερδίζουμε χωρίς υπολογισμούς! Αυτό είναι το Part που σας κάνει masters! 🎯
🎯 1. Symmetry Strategy - The Elegant Weapon
📌 Τι είναι η Symmetry Strategy;
Η Symmetry Strategy είναι μια τεχνική όπου καθρεφτίζεις τις κινήσεις του αντιπάλου σου χρησιμοποιώντας κάποιο είδος συμμετρίας.
Βασική Ιδέα:
Αν το game board έχει συμμετρία (rotational, reflective, translational), μπορείς να παίξεις έτσι ώστε πάντα να διατηρείς τη συμμετρία μετά τη σειρά σου!
Γιατί δουλεύει;
Αν διατηρείς συμμετρία, ο αντίπαλος θα μείνει πρώτος χωρίς νόμιμη κίνηση!
Η Symmetry Strategy είναι μια τεχνική όπου καθρεφτίζεις τις κινήσεις του αντιπάλου σου χρησιμοποιώντας κάποιο είδος συμμετρίας.
Βασική Ιδέα:
Αν το game board έχει συμμετρία (rotational, reflective, translational), μπορείς να παίξεις έτσι ώστε πάντα να διατηρείς τη συμμετρία μετά τη σειρά σου!
Γιατί δουλεύει;
Αν διατηρείς συμμετρία, ο αντίπαλος θα μείνει πρώτος χωρίς νόμιμη κίνηση!
🎲 Types of Symmetry
1. Reflective Symmetry (Mirror):
• Το board έχει άξονα συμμετρίας
• Κάθε κίνηση του αντιπάλου, την καθρεφτίζεις
2. Rotational Symmetry:
• Το board είναι συμμετρικό ως προς περιστροφή
• Παίζεις τη "rotated" εκδοχή της κίνησης του αντιπάλου
3. Translational Symmetry:
• Το board έχει επαναλαμβανόμενο pattern
• Παίζεις την "shifted" εκδοχή
4. Parity Symmetry:
• Pair up positions
• Mirror between pairs
1. Reflective Symmetry (Mirror):
• Το board έχει άξονα συμμετρίας
• Κάθε κίνηση του αντιπάλου, την καθρεφτίζεις
2. Rotational Symmetry:
• Το board είναι συμμετρικό ως προς περιστροφή
• Παίζεις τη "rotated" εκδοχή της κίνησης του αντιπάλου
3. Translational Symmetry:
• Το board έχει επαναλαμβανόμενο pattern
• Παίζεις την "shifted" εκδοχή
4. Parity Symmetry:
• Pair up positions
• Mirror between pairs
🔹 Παράδειγμα 1: Chocolate Bar Game
Πρόβλημα: Ένα σοκολατάκι \(m \times n\). Κάθε κίνηση: διάλεξε ένα κομμάτι και σπάσε το σε δύο μικρότερα (horizontal ή vertical). Ο παίκτης που δεν μπορεί να κινηθεί χάνει. Ποιος κερδίζει;
Λύση:
Λύση:
Ανάλυση:
Το τελικό αποτέλεσμα είναι πάντα \(mn\) κομμάτια \(1 \times 1\).
Άρα ο συνολικός αριθμός κινήσεων είναι πάντα \(mn - 1\) (fixed, ανεξάρτητα από τη σειρά των κινήσεων!).
Parity Argument:
• Αν \(mn - 1\) είναι περιττός → πρώτος παίκτης κάνει την τελευταία κίνηση → κερδίζει
• Αν \(mn - 1\) είναι άρτιος → δεύτερος παίκτης κερδίζει
Το τελικό αποτέλεσμα είναι πάντα \(mn\) κομμάτια \(1 \times 1\).
Άρα ο συνολικός αριθμός κινήσεων είναι πάντα \(mn - 1\) (fixed, ανεξάρτητα από τη σειρά των κινήσεων!).
Parity Argument:
• Αν \(mn - 1\) είναι περιττός → πρώτος παίκτης κάνει την τελευταία κίνηση → κερδίζει
• Αν \(mn - 1\) είναι άρτιος → δεύτερος παίκτης κερδίζει
Συμπέρασμα:
• Αν \(mn\) είναι άρτιος → \(mn-1\) περιττός → First player wins
• Αν \(mn\) είναι περιττός → \(mn-1\) άρτιος → Second player wins
Παράδειγμα:
• \(3 \times 4\): \(mn = 12\) (άρτιος) → \(11\) κινήσεις (περιττές) → First wins
• \(3 \times 3\): \(mn = 9\) (περιττός) → \(8\) κινήσεις (άρτιες) → Second wins
• Αν \(mn\) είναι άρτιος → \(mn-1\) περιττός → First player wins
• Αν \(mn\) είναι περιττός → \(mn-1\) άρτιος → Second player wins
Παράδειγμα:
• \(3 \times 4\): \(mn = 12\) (άρτιος) → \(11\) κινήσεις (περιττές) → First wins
• \(3 \times 3\): \(mn = 9\) (περιττός) → \(8\) κινήσεις (άρτιες) → Second wins
🔹 Παράδειγμα 2: Tic-Tac-Toe Symmetry
Πρόβλημα: Tic-Tac-Toe: First player (X) έχει winning strategy;
Strategy Stealing Argument:
• Αν ο πρώτος παίζει off-center, παίξε στο συμμετρικό σημείο ως προς το κέντρο
• Guarantees τουλάχιστον draw!
Strategy Stealing Argument:
Claim: Ο δεύτερος παίκτης δεν έχει winning strategy.
Απόδειξη (by contradiction):
Υποθέτουμε ότι ο δεύτερος παίκτης έχει winning strategy \(S\).
Τότε ο πρώτος παίκτης μπορεί να:
1. Παίξει στο κέντρο (ή οποιαδήποτε θέση)
2. Μετά, "κλέψει" τη στρατηγική \(S\) του δεύτερου και να παίζει σαν να είναι δεύτερος!
3. Αν η στρατηγική \(S\) του πει να παίξει σε θέση που είναι κατειλημμένη, παίζει οπουδήποτε αλλού
Έτσι ο πρώτος παίκτης θα κερδίσει (contradiction!)
Άρα ο δεύτερος δεν έχει winning strategy → At best, draw!
Center Symmetry Strategy για δεύτερο:Απόδειξη (by contradiction):
Υποθέτουμε ότι ο δεύτερος παίκτης έχει winning strategy \(S\).
Τότε ο πρώτος παίκτης μπορεί να:
1. Παίξει στο κέντρο (ή οποιαδήποτε θέση)
2. Μετά, "κλέψει" τη στρατηγική \(S\) του δεύτερου και να παίζει σαν να είναι δεύτερος!
3. Αν η στρατηγική \(S\) του πει να παίξει σε θέση που είναι κατειλημμένη, παίζει οπουδήποτε αλλού
Έτσι ο πρώτος παίκτης θα κερδίσει (contradiction!)
Άρα ο δεύτερος δεν έχει winning strategy → At best, draw!
• Αν ο πρώτος παίζει off-center, παίξε στο συμμετρικό σημείο ως προς το κέντρο
• Guarantees τουλάχιστον draw!
🎮 2. Pairing Strategy - Advanced
🔹 Παράδειγμα 3: Chomp Game
Πρόβλημα: Ένα \(m \times n\) grid από σοκολάτες. Bottom-left είναι "poisoned". Κάθε κίνηση: διάλεξε μια σοκολάτα και φάε αυτή + όλες πάνω-δεξιά από αυτή. Ο παίκτης που φάει τη poisoned χάνει. Ποιος κερδίζει;
Λύση:
Λύση:
Strategy Stealing:
Claim: Ο πρώτος παίκτης κερδίζει!
Απόδειξη:
Υποθέτουμε ότι ο δεύτερος έχει winning strategy.
Τότε ο πρώτος παίκτης:
1. Παίζει top-right corner (μικρότερη κίνηση)
2. Μετά "κλέβει" τη winning strategy του δεύτερου
3. Αν χρειαστεί να παίξει το top-right που ήδη έφαγε, παίζει άλλο top-right
Contradiction! Άρα ο πρώτος κερδίζει.
Σημείωση: Η ακριβής winning strategy για \(m \times n\) είναι unknown για γενικό \(m,n\)! Αυτό είναι open problem!
Claim: Ο πρώτος παίκτης κερδίζει!
Απόδειξη:
Υποθέτουμε ότι ο δεύτερος έχει winning strategy.
Τότε ο πρώτος παίκτης:
1. Παίζει top-right corner (μικρότερη κίνηση)
2. Μετά "κλέβει" τη winning strategy του δεύτερου
3. Αν χρειαστεί να παίξει το top-right που ήδη έφαγε, παίζει άλλο top-right
Contradiction! Άρα ο πρώτος κερδίζει.
Σημείωση: Η ακριβής winning strategy για \(m \times n\) είναι unknown για γενικό \(m,n\)! Αυτό είναι open problem!
🔹 Παράδειγμα 4: Two-Row Pairing
Πρόβλημα: Nim με δύο rows από αντικείμενα: top row \(n\) αντικείμενα, bottom row \(n\) αντικείμενα. Κανόνας ειδικός: μπορείς να πάρεις από οποιοδήποτε row. Ποιος κερδίζει;
Λύση:
Λύση:
Pairing Strategy για δεύτερο παίκτη:
Οτιδήποτε κάνει ο πρώτος σε ένα row, ο δεύτερος το κάνει στο άλλο row!
Proof that it works:
• Αρχικά: (n, n) - συμμετρικό
• Μετά από κίνηση πρώτου: (n-k, n) - ασύμμετρο
• Μετά από mirror: (n-k, n-k) - συμμετρικό πάλι!
Τελικά: (0, 0) → δεύτερος παίκτης κερδίζει!
💡 Σημείωση: Αυτό είναι απλώς το ίδιο Two-Pile Nim που είδαμε στο Part 1, με \(a=b=n\) — η mirror στρατηγική είναι ίδια.
Οτιδήποτε κάνει ο πρώτος σε ένα row, ο δεύτερος το κάνει στο άλλο row!
Proof that it works:
• Αρχικά: (n, n) - συμμετρικό
• Μετά από κίνηση πρώτου: (n-k, n) - ασύμμετρο
• Μετά από mirror: (n-k, n-k) - συμμετρικό πάλι!
Τελικά: (0, 0) → δεύτερος παίκτης κερδίζει!
💡 Σημείωση: Αυτό είναι απλώς το ίδιο Two-Pile Nim που είδαμε στο Part 1, με \(a=b=n\) — η mirror στρατηγική είναι ίδια.
🌟 3. Partizan Games
📌 Τι είναι Partizan Games;
Μέχρι τώρα μιλήσαμε για impartial games (same moves για όλους).
Partizan games: Οι δύο παίκτες έχουν διαφορετικούς κανόνες/κινήσεις!
Παραδείγματα:
• Chess (άσπρα vs μαύρα)
• Checkers
• Go
• Domineering (vertical vs horizontal)
• Hackenbush (blue vs red edges)
Μέχρι τώρα μιλήσαμε για impartial games (same moves για όλους).
Partizan games: Οι δύο παίκτες έχουν διαφορετικούς κανόνες/κινήσεις!
Παραδείγματα:
• Chess (άσπρα vs μαύρα)
• Checkers
• Go
• Domineering (vertical vs horizontal)
• Hackenbush (blue vs red edges)
🎮 Domineering Game
Rules:
• Board: \(m \times n\) grid
• Vertical player: Places \(1 \times 2\) domino vertically
• Horizontal player: Places \(2 \times 1\) domino horizontally
• First player unable to move loses
Ερώτηση: Ποιος κερδίζει σε \(n \times n\) board;
Rules:
• Board: \(m \times n\) grid
• Vertical player: Places \(1 \times 2\) domino vertically
• Horizontal player: Places \(2 \times 1\) domino horizontally
• First player unable to move loses
Ερώτηση: Ποιος κερδίζει σε \(n \times n\) board;
🔹 Παράδειγμα 5: Domineering on Square Board
Πρόβλημα: Domineering σε \(n \times n\) board. Vertical παίζει πρώτος. Ποιος κερδίζει;
Λύση:
Λύση:
Μια συγκεκριμένη, επαληθευμένη περίπτωση: \(n=2\)
Έστω ο Vertical παίζει πρώτος στο \(2 \times 2\) board. Οποιαδήποτε από τις δύο νόμιμες κινήσεις του (κάθετο domino στην αριστερή ή στη δεξιά στήλη) αφήνει μια στήλη με 2 κελιά στοιβαγμένα κάθετα — άρα ο Horizontal δεν έχει καμία νόμιμη κίνηση (χρειάζεται 2 κελιά στην ίδια γραμμή, δεν υπάρχουν)!
Συμπέρασμα για \(n=2\): Κερδίζει ο πρώτος παίκτης (Vertical)!
⚠️ Προσοχή σε λάθος συλλογισμό: Μια απλή στρατηγική «χώρισε σε \(2\times2\) blocks, ο Horizontal συμπληρώνει το υπόλοιπο του block» δεν δουλεύει: αν ο Vertical πάρει τη μία στήλη ενός block, τα 2 κελιά που μένουν είναι στην ίδια στήλη (όχι στην ίδια γραμμή) — ο Horizontal δεν μπορεί να τα χρησιμοποιήσει καθόλου εκεί!
Έστω ο Vertical παίζει πρώτος στο \(2 \times 2\) board. Οποιαδήποτε από τις δύο νόμιμες κινήσεις του (κάθετο domino στην αριστερή ή στη δεξιά στήλη) αφήνει μια στήλη με 2 κελιά στοιβαγμένα κάθετα — άρα ο Horizontal δεν έχει καμία νόμιμη κίνηση (χρειάζεται 2 κελιά στην ίδια γραμμή, δεν υπάρχουν)!
Συμπέρασμα για \(n=2\): Κερδίζει ο πρώτος παίκτης (Vertical)!
⚠️ Προσοχή σε λάθος συλλογισμό: Μια απλή στρατηγική «χώρισε σε \(2\times2\) blocks, ο Horizontal συμπληρώνει το υπόλοιπο του block» δεν δουλεύει: αν ο Vertical πάρει τη μία στήλη ενός block, τα 2 κελιά που μένουν είναι στην ίδια στήλη (όχι στην ίδια γραμμή) — ο Horizontal δεν μπορεί να τα χρησιμοποιήσει καθόλου εκεί!
Η γενική περίπτωση \(n \times n\):
Το ποιος κερδίζει στο γενικό \(n \times n\) Domineering board είναι στην πραγματικότητα ένα δύσκολο πρόβλημα της combinatorial game theory — δεν λύνεται με ένα απλό pairing argument σαν αυτό που περιγράφηκε. Οι Berlekamp, Conway και Guy (στο κλασικό "Winning Ways") το αναλύουν με πιο εξελιγμένες τεχνικές (θεωρία CGT values), και τα αποτελέσματα για μικρά boards προκύπτουν μέσω εξαντλητικής (computer-assisted) ανάλυσης. Δεν υπάρχει απλός στοιχειώδης κανόνας τύπου «άρτιο \(n\) → κερδίζει πάντα ο τάδε» — χρειάζεται περίπτωση-προς-περίπτωση μελέτη.
Το ποιος κερδίζει στο γενικό \(n \times n\) Domineering board είναι στην πραγματικότητα ένα δύσκολο πρόβλημα της combinatorial game theory — δεν λύνεται με ένα απλό pairing argument σαν αυτό που περιγράφηκε. Οι Berlekamp, Conway και Guy (στο κλασικό "Winning Ways") το αναλύουν με πιο εξελιγμένες τεχνικές (θεωρία CGT values), και τα αποτελέσματα για μικρά boards προκύπτουν μέσω εξαντλητικής (computer-assisted) ανάλυσης. Δεν υπάρχει απλός στοιχειώδης κανόνας τύπου «άρτιο \(n\) → κερδίζει πάντα ο τάδε» — χρειάζεται περίπτωση-προς-περίπτωση μελέτη.
🌳 4. Green Hackenbush - Graph Games
📌 Green Hackenbush
Setup:
• Έχουμε γράφο με edges που συνδέονται σε "ground" node
• Κάθε κίνηση: Remove ένα edge
• Όλα τα edges που αποσυνδέονται από το ground εξαφανίζονται
• Last player to move wins
Γιατί "Green";
Όλα τα edges είναι "neutral" - και οι δύο παίκτες μπορούν να τα αφαιρέσουν (impartial).
Blue-Red Hackenbush: Partizan version όπου μπορείς να αφαιρέσεις μόνο το χρώμα σου!
Setup:
• Έχουμε γράφο με edges που συνδέονται σε "ground" node
• Κάθε κίνηση: Remove ένα edge
• Όλα τα edges που αποσυνδέονται από το ground εξαφανίζονται
• Last player to move wins
Γιατί "Green";
Όλα τα edges είναι "neutral" - και οι δύο παίκτες μπορούν να τα αφαιρέσουν (impartial).
Blue-Red Hackenbush: Partizan version όπου μπορείς να αφαιρέσεις μόνο το χρώμα σου!
🔹 Παράδειγμα 6: Bamboo Stalk Hackenbush
Πρόβλημα: Green Hackenbush με \(k\) "bamboo stalks" (simple paths) μηκών \(a_1, a_2, \ldots, a_k\) από το ground. Ποιος κερδίζει;
Λύση:
Stalks: (3, 5, 6)
\(g = 3 \oplus 5 \oplus 6 = 011 \oplus 101 \oplus 110 = 000 = 0\)
Losing position για τον παίκτη που παίζει!
Λύση:
Grundy Analysis:
Κάθε bamboo stalk μήκους \(n\) έχει Grundy number \(g(n) = n\)!
Γιατί;
• Αφαιρώντας το edge \(i\) από κάτω, μένει stalk μήκους \(i-1\)
• Άρα μπορούμε να φτάσουμε σε states: \(0, 1, 2, \ldots, n-1\)
• \(g(n) = \text{mex}(\{0,1,\ldots,n-1\}) = n\)
Multi-stalk:
\[ g = a_1 \oplus a_2 \oplus \cdots \oplus a_k \]
Δηλαδή: Ακριβώς όπως Nim!
Παράδειγμα:Κάθε bamboo stalk μήκους \(n\) έχει Grundy number \(g(n) = n\)!
Γιατί;
• Αφαιρώντας το edge \(i\) από κάτω, μένει stalk μήκους \(i-1\)
• Άρα μπορούμε να φτάσουμε σε states: \(0, 1, 2, \ldots, n-1\)
• \(g(n) = \text{mex}(\{0,1,\ldots,n-1\}) = n\)
Multi-stalk:
\[ g = a_1 \oplus a_2 \oplus \cdots \oplus a_k \]
Δηλαδή: Ακριβώς όπως Nim!
Stalks: (3, 5, 6)
\(g = 3 \oplus 5 \oplus 6 = 011 \oplus 101 \oplus 110 = 000 = 0\)
Losing position για τον παίκτη που παίζει!
🔹 Παράδειγμα 7: Complex Hackenbush Graph
Πρόβλημα: Green Hackenbush με graph που έχει branches (διακλαδώσεις). Πώς υπολογίζουμε Grundy number;
Γενική Μέθοδος (Colon Principle):
Γενική Μέθοδος (Colon Principle):
Σωστός Αναδρομικός Υπολογισμός:
1. Leaf (χωρίς παιδιά): το edge που οδηγεί σε ένα leaf είναι σαν μονό bamboo stalk μήκους 1, άρα η τιμή του κλάδου που καταλήγει εκεί είναι \(1\).
2. Εσωτερικός κόμβος \(v\) με παιδιά \(c_1, c_2, \ldots, c_k\): η τιμή του κλάδου (edge γονέα→\(v\) + ό,τι κρέμεται από κάτω) είναι: \[ value(v) = 1 + \big[value(c_1) \oplus value(c_2) \oplus \cdots \oplus value(c_k)\big] \] Το +1 είναι κρίσιμο — αντιστοιχεί ακριβώς στο edge που συνδέει τον γονέα με το \(v\)! Παραλείποντάς το, καταλήγεις σε λάθος αποτέλεσμα.
3. Ρίζα (ο κόμβος που συνδέεται απευθείας με το Ground): \[ g(\text{graph}) = value(\text{root}) \]
Bottom-up calculation!
Example Graph:1. Leaf (χωρίς παιδιά): το edge που οδηγεί σε ένα leaf είναι σαν μονό bamboo stalk μήκους 1, άρα η τιμή του κλάδου που καταλήγει εκεί είναι \(1\).
2. Εσωτερικός κόμβος \(v\) με παιδιά \(c_1, c_2, \ldots, c_k\): η τιμή του κλάδου (edge γονέα→\(v\) + ό,τι κρέμεται από κάτω) είναι: \[ value(v) = 1 + \big[value(c_1) \oplus value(c_2) \oplus \cdots \oplus value(c_k)\big] \] Το +1 είναι κρίσιμο — αντιστοιχεί ακριβώς στο edge που συνδέει τον γονέα με το \(v\)! Παραλείποντάς το, καταλήγεις σε λάθος αποτέλεσμα.
3. Ρίζα (ο κόμβος που συνδέεται απευθείας με το Ground): \[ g(\text{graph}) = value(\text{root}) \]
Bottom-up calculation!
Ground
|
[1]
/ \
[2] [3]
/ \ |
[L] [L] [L]
(κάθε γράμμα/αριθμός = ξεχωριστός κόμβος, κάθε γραμμή = 1 edge)
Calculation:
• Leaves: value = 1 (κάθε leaf-edge είναι stalk μήκους 1)
• Node [2]: value = \(1 + (1 \oplus 1) = 1 + 0 = 1\)
• Node [3]: value = \(1 + 1 = 2\)
• Node [1] (root): value = \(1 + (1 \oplus 2) = 1 + 3 = 4\)
Άρα το graph έχει \(g = 4 \neq 0\) → Winning position!
Νόμιμη winning κίνηση: κόψε αμέσως το edge Ground→[1] — μηδενίζει ολόκληρο το γράφημα (νέο \(g=0\)).
• Leaves: value = 1 (κάθε leaf-edge είναι stalk μήκους 1)
• Node [2]: value = \(1 + (1 \oplus 1) = 1 + 0 = 1\)
• Node [3]: value = \(1 + 1 = 2\)
• Node [1] (root): value = \(1 + (1 \oplus 2) = 1 + 3 = 4\)
Άρα το graph έχει \(g = 4 \neq 0\) → Winning position!
Νόμιμη winning κίνηση: κόψε αμέσως το edge Ground→[1] — μηδενίζει ολόκληρο το γράφημα (νέο \(g=0\)).
🎯 5. Misère Game Strategies
🔄 General Misère Strategy
Misère Convention: Last to move loses (αντί για wins)
Key Insight:
Για πολλά games, η misère strategy είναι:
• Παίζε κανονικά (κάνε nim-sum = 0) μέχρι να φτάσεις σε "all heaps size ≤1" state
• Τότε ο παίκτης που είναι να παίξει κερδίζει αν βλέπει άρτιο αριθμό τέτοιων heaps, και θέλει να αφήσει περιττό στον αντίπαλο
Misère Nim (θεώρημα Bouton):
• Όσο υπάρχει pile μεγέθους ≥ 2: Παίξε για nim-sum = 0 (όπως στο κανονικό Nim)
• Μόλις όλα τα piles γίνουν ≤ 1: Άφησε στον αντίπαλο περιττό αριθμό piles μεγέθους 1
Misère Convention: Last to move loses (αντί για wins)
Key Insight:
Για πολλά games, η misère strategy είναι:
• Παίζε κανονικά (κάνε nim-sum = 0) μέχρι να φτάσεις σε "all heaps size ≤1" state
• Τότε ο παίκτης που είναι να παίξει κερδίζει αν βλέπει άρτιο αριθμό τέτοιων heaps, και θέλει να αφήσει περιττό στον αντίπαλο
Misère Nim (θεώρημα Bouton):
• Όσο υπάρχει pile μεγέθους ≥ 2: Παίξε για nim-sum = 0 (όπως στο κανονικό Nim)
• Μόλις όλα τα piles γίνουν ≤ 1: Άφησε στον αντίπαλο περιττό αριθμό piles μεγέθους 1
📊 6. Competition Strategy Framework
🏆 Master Framework - Advanced Games
ΒΗΜΑ 1: Αναγνώριση Game Type
• Impartial vs Partizan;
• Normal vs Misère;
• Has symmetry;
• Graph structure;
ΒΗΜΑ 2: Check for Symmetry
• Reflective;
• Rotational;
• Pairing;
→ Αν υπάρχει, use symmetry strategy!
ΒΗΜΑ 3: Strategy Stealing
• Can you steal second player's strategy;
• Proves first player doesn't lose;
ΒΗΜΑ 4: Grundy (if impartial)
• Calculate \(g(n)\);
• Use XOR for sums;
ΒΗΜΑ 5: Case Analysis (if partizan)
• Small boards: exhaustive search
• Look for patterns
ΒΗΜΑ 6: Verify & Adapt
• Test strategy
• Adjust if needed
ΒΗΜΑ 1: Αναγνώριση Game Type
• Impartial vs Partizan;
• Normal vs Misère;
• Has symmetry;
• Graph structure;
ΒΗΜΑ 2: Check for Symmetry
• Reflective;
• Rotational;
• Pairing;
→ Αν υπάρχει, use symmetry strategy!
ΒΗΜΑ 3: Strategy Stealing
• Can you steal second player's strategy;
• Proves first player doesn't lose;
ΒΗΜΑ 4: Grundy (if impartial)
• Calculate \(g(n)\);
• Use XOR for sums;
ΒΗΜΑ 5: Case Analysis (if partizan)
• Small boards: exhaustive search
• Look for patterns
ΒΗΜΑ 6: Verify & Adapt
• Test strategy
• Adjust if needed
📋 Quick Strategy Selection
| Game Feature | Best Strategy | Example |
|---|---|---|
| Has symmetry | Mirror/Symmetry | Two-row Nim |
| Impartial + sum | Grundy + XOR | Multi-pile Nim |
| Fixed total moves | Parity argument | Chocolate bar |
| Graph structure | Grundy recursion (+1 ανά edge!) | Hackenbush |
| Unknown winner | Strategy stealing | Chomp |
| Partizan + small | Exhaustive + pattern | Small Domineering |
🚨 Common Mistakes - Advanced
⚠️ Τα 7 Advanced Mistakes
1. Missing Symmetry
❌ Δεν βλέπουμε την προφανή συμμετρία
✅ ΠΑΝΤΑ check για symmetry πρώτα!
2. Strategy Stealing Wrong
❌ "Strategy stealing proves first player wins"
✅ Strategy stealing proves first player δεν χάνει (σε παιχνίδι χωρίς ισοπαλίες, αυτό σημαίνει ότι κερδίζει)
3. Partizan = Impartial
❌ Εφαρμόζουμε Grundy σε partizan games
✅ Grundy μόνο για impartial!
4. Misère = Normal
❌ Ξεχνάμε να αλλάξουμε strategy για misère
✅ Misère έχει special endgame rules (άφησε περιττό αριθμό piles μεγέθους 1)!
5. Complexity Underestimation
❌ "Chomp/Domineering είναι εύκολα, απλά υπολόγισε"
✅ Πολλά τέτοια games είναι εξαιρετικά δύσκολα ή PSPACE-complete!
6. Hackenbush Tree Errors
❌ Υπολογίζουμε \(value(v)\) χωρίς το \(+1\) για το edge γονέα→\(v\)
✅ ΠΑΝΤΑ \(value(v) = 1 + \text{XOR παιδιών}\), bottom-up!
7. Parity Confusion
❌ Συγχέουμε "odd moves total" με "odd heaps"
✅ Διαφορετικά concepts!
1. Missing Symmetry
❌ Δεν βλέπουμε την προφανή συμμετρία
✅ ΠΑΝΤΑ check για symmetry πρώτα!
2. Strategy Stealing Wrong
❌ "Strategy stealing proves first player wins"
✅ Strategy stealing proves first player δεν χάνει (σε παιχνίδι χωρίς ισοπαλίες, αυτό σημαίνει ότι κερδίζει)
3. Partizan = Impartial
❌ Εφαρμόζουμε Grundy σε partizan games
✅ Grundy μόνο για impartial!
4. Misère = Normal
❌ Ξεχνάμε να αλλάξουμε strategy για misère
✅ Misère έχει special endgame rules (άφησε περιττό αριθμό piles μεγέθους 1)!
5. Complexity Underestimation
❌ "Chomp/Domineering είναι εύκολα, απλά υπολόγισε"
✅ Πολλά τέτοια games είναι εξαιρετικά δύσκολα ή PSPACE-complete!
6. Hackenbush Tree Errors
❌ Υπολογίζουμε \(value(v)\) χωρίς το \(+1\) για το edge γονέα→\(v\)
✅ ΠΑΝΤΑ \(value(v) = 1 + \text{XOR παιδιών}\), bottom-up!
7. Parity Confusion
❌ Συγχέουμε "odd moves total" με "odd heaps"
✅ Διαφορετικά concepts!
🏆 CHALLENGE PROBLEM - Part 3
🎯 THE ULTIMATE CHALLENGE
Πρόβλημα: Green Hackenbush με το εξής graph:
Ποιος κερδίζει και ποια είναι η βέλτιστη πρώτη κίνηση;
🎁 Hints σε 4 Επίπεδα:
Πρόβλημα: Green Hackenbush με το εξής graph:
Ground
/ | \
(5 edges)(2 edges) (1 edge)
| | |
leaf leaf P
/ \
(3 edges) (2 edges)
| |
leaf leaf
(Τρεις ανεξάρτητοι κλάδοι από το Ground: ένα απλό stalk 5 edges, ένα απλό stalk 2 edges, και ένας κλάδος που μετά από 1 edge φτάνει σε κόμβο \(P\) ο οποίος διακλαδίζεται σε δύο stalks μήκους 3 και 2)Ποιος κερδίζει και ποια είναι η βέλτιστη πρώτη κίνηση;
🎁 Hints σε 4 Επίπεδα:
🥉 Hint 1: Ένα απλό (χωρίς διακλάδωση) stalk μήκους \(L\) edges έχει τιμή \(L\).
🥈 Hint 2: Στο σημείο διακλάδωσης \(P\), συνδύασε τις τιμές των δύο υπο-κλάδων με XOR — και μην ξεχάσεις το \(+1\) για το edge Ground→\(P\)!
🥇 Hint 3: Οι τρεις κλάδοι από το Ground είναι ανεξάρτητοι — το συνολικό \(g\) είναι το XOR τους.
💎 Hint 4: Βρες ποιος κλάδος επιτρέπει νόμιμη κίνηση προς \(g=0\) (σαν σε multi-pile Nim).
📮 Πλήρης Λύση:
Step 1: Τιμές των τριών ανεξάρτητων κλάδων
• Κλάδος A (απλό stalk 5 edges): \(value(A) = 5\)
• Κλάδος B (απλό stalk 2 edges): \(value(B) = 2\)
• Κλάδος Γ (μέσω κόμβου \(P\)): πρώτα συνδύασε τα δύο sub-stalks του \(P\) (μήκους 3 και 2) με XOR: \(3 \oplus 2 = 011 \oplus 010 = 001 = 1\). Μετά πρόσθεσε 1 για το edge Ground→\(P\): \(value(\Gamma) = 1 + 1 = 2\)
Step 2: Συνολικό Grundy
\[ g = value(A) \oplus value(B) \oplus value(\Gamma) = 5 \oplus 2 \oplus 2 = 101_2 \oplus 010_2 \oplus 010_2 = 101_2 = 5 \]
Άρα \(g = 5 \neq 0\) → Winning position!
Step 3: Εύρεση Winning Move
Δοκιμάζουμε \(a_i' = g \oplus a_i\) για κάθε ανεξάρτητο κλάδο:
• Κλάδος A (5): \(5 \oplus 5 = 0 < 5\) ✓ νόμιμο! (κόψε το edge Ground→A, μηδενίζοντας τον κλάδο)
• Κλάδος B (2): \(5 \oplus 2 = 7 > 2\) ✗ μη νόμιμο
• Κλάδος Γ (2): \(5 \oplus 2 = 7 > 2\) ✗ μη νόμιμο
Μοναδική winning κίνηση: Κόψε το edge στη βάση του κλάδου των 5 (Ground→A). Αυτό μηδενίζει τον κλάδο A, αφήνοντας \(g = 0 \oplus 2 \oplus 2 = 0\). ✓
Step 1: Τιμές των τριών ανεξάρτητων κλάδων
• Κλάδος A (απλό stalk 5 edges): \(value(A) = 5\)
• Κλάδος B (απλό stalk 2 edges): \(value(B) = 2\)
• Κλάδος Γ (μέσω κόμβου \(P\)): πρώτα συνδύασε τα δύο sub-stalks του \(P\) (μήκους 3 και 2) με XOR: \(3 \oplus 2 = 011 \oplus 010 = 001 = 1\). Μετά πρόσθεσε 1 για το edge Ground→\(P\): \(value(\Gamma) = 1 + 1 = 2\)
Step 2: Συνολικό Grundy
\[ g = value(A) \oplus value(B) \oplus value(\Gamma) = 5 \oplus 2 \oplus 2 = 101_2 \oplus 010_2 \oplus 010_2 = 101_2 = 5 \]
Άρα \(g = 5 \neq 0\) → Winning position!
Step 3: Εύρεση Winning Move
Δοκιμάζουμε \(a_i' = g \oplus a_i\) για κάθε ανεξάρτητο κλάδο:
• Κλάδος A (5): \(5 \oplus 5 = 0 < 5\) ✓ νόμιμο! (κόψε το edge Ground→A, μηδενίζοντας τον κλάδο)
• Κλάδος B (2): \(5 \oplus 2 = 7 > 2\) ✗ μη νόμιμο
• Κλάδος Γ (2): \(5 \oplus 2 = 7 > 2\) ✗ μη νόμιμο
Μοναδική winning κίνηση: Κόψε το edge στη βάση του κλάδου των 5 (Ground→A). Αυτό μηδενίζει τον κλάδο A, αφήνοντας \(g = 0 \oplus 2 \oplus 2 = 0\). ✓
📊 Σύνοψη & Finale Teaser
🎓 Τι Μάθαμε σε αυτό το Part:
✅ Symmetry Strategy: Mirror, rotation, pairing
✅ Strategy Stealing: Proof technique
✅ Parity Arguments: Fixed-move games
✅ Partizan Games: Domineering, different rules
✅ Green Hackenbush: Graph Grundy calculation (με το κρίσιμο +1 ανά edge!)
✅ Misère Strategies: Endgame modifications
✅ 7 Complex Examples: Από Chocolate → Complex Graphs
✅ Master Framework: 6-step advanced approach
✅ Symmetry Strategy: Mirror, rotation, pairing
✅ Strategy Stealing: Proof technique
✅ Parity Arguments: Fixed-move games
✅ Partizan Games: Domineering, different rules
✅ Green Hackenbush: Graph Grundy calculation (με το κρίσιμο +1 ανά edge!)
✅ Misère Strategies: Endgame modifications
✅ 7 Complex Examples: Από Chocolate → Complex Graphs
✅ Master Framework: 6-step advanced approach
🎊 Συγχαρητήρια!
Ολοκληρώσατε το Part 3 του Game Theory Marathon!
Τι κατακτήσατε:
✅ Symmetry strategy mastery
✅ Strategy stealing technique
✅ Partizan game understanding
✅ Green Hackenbush complete theory
✅ Parity arguments
✅ Misère game modifications
✅ 7 αναλυτικά complex examples
✅ Advanced competition skills
Ολοκληρώσατε το Part 3 του Game Theory Marathon!
Τι κατακτήσατε:
✅ Symmetry strategy mastery
✅ Strategy stealing technique
✅ Partizan game understanding
✅ Green Hackenbush complete theory
✅ Parity arguments
✅ Misère game modifications
✅ 7 αναλυτικά complex examples
✅ Advanced competition skills
📅 Επόμενο Part - GRAND FINALE:
Part 4: IMO Problems & Competition Mastery
The ultimate collection! 💜👑
Part 4: IMO Problems & Competition Mastery
The ultimate collection! 💜👑
🔗 Αν σου διέφυγε: Part 2 - Sprague-Grundy Theory & Nimbers
Ετοιμαστείτε για το FINALE...
Η κορυφή σας περιμένει! 🏔️🎮👑
Έρχεται το πολλαπλό βιβλίο ΝΕΟ — βρες όλες τις επιλογές εδώ
PDF & Ψηφιακά Μαθησιακά Αντικείμενα — χωρίς εγγραφή • Portify
📚 437 βιβλία🎬 22.000+ Ψηφιακά Μαθησιακά Αντικείμενα
Δες τα βιβλία →
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου