EisatoponAI: 👑 2026 Math Marathon: Game Theory #4 FINALE - IMO Problems & Competition Mastery

Game Theory Mastery — Part 4: IMO Problems & Competition Strategy

Στόχος του Part 4: Συνδυάζουμε όλες τις τεχνικές από τα Parts 1–3 για να λύσουμε προβλήματα διαγωνισμών και κλασικά training προβλήματα combinatorial game theory. Κάθε πρόβλημα συνοδεύεται από πλήρη απόδειξη, όχι sketch.

📚 Πηγές: Το Πρόβλημα 5 (IMO 2025) και το Πρόβλημα 7 (θεώρημα Nash) βασίζονται σε πλήρως επαληθευμένες, επίσημες πηγές. Τα Προβλήματα 2, 3, 4 και 6 είναι κλασικά training προβλήματα combinatorial game theory· οι αρχικές αναφορές σε συγκεκριμένα IMO Shortlist / Balkan MO προβλήματα δεν επιβεβαιώθηκαν κατά τον έλεγχο και αφαιρέθηκαν — σε τουλάχιστον δύο περιπτώσεις (SL 2001 C4, SL 2007 C5) οι πραγματικές πηγές αποδείχθηκε ότι αφορούν εντελώς διαφορετικά προβλήματα. Για πλήρη official solutions στα επιβεβαιωμένα προβλήματα, δείτε: Evan Chen — IMO Solution Notes και AoPS Community.

1. Competition Problem-Solving Framework

The 8-Step Framework

Read Carefully: Ποιοι είναι οι κανόνες ακριβώς; Ποιος κερδίζει; Normal ή Misère; Πεπερασμένο ή άπειρο παιχνίδι;
Small Cases: Δοκίμασε n = 1, 2, 3, 4, 5. Υπολόγισε L/W positions. Βρες pattern.
Identify Game Type: Impartial ή Partizan; Single game ή Sum; Υπάρχει συμμετρία;
Choose Technique:
- Συμμετρία → Mirror/Pairing strategy
- Impartial + Sum → Sprague-Grundy + XOR
- Partizan → Case analysis, strategy stealing
- Fixed moves → Parity argument
- Graph structure → Hackenbush-style analysis
Calculate / Prove: Εφάρμοσε την τεχνική. Δώσε explicit winning strategy.
Verify: Έλεγξε με παραδείγματα. Προσοχή στα edge cases.
Write Solution: Clear structure: state winner → describe strategy → prove correctness.
Double-Check: Ξαναδιάβασε το πρόβλημα. Επιβεβαίωσε τη μορφή της απάντησης.

2. IMO-Level Problem Collection

Problem 1: Bachet's Game (Classical / Training Problem)

Πρόβλημα: Υπάρχουν 100 πέτρες. Δύο παίκτες παίζουν εναλλάξ. Κάθε κίνηση: παίρνεις 1, 2, ή 3 πέτρες. Ο παίκτης που παίρνει την τελευταία πέτρα κερδίζει. Αν και οι δύο παίζουν βέλτιστα, ποιος κερδίζει;

Αναγνώριση: Αυτό είναι το κλασικό Bachet's game με σύνολο κινήσεων M = {1, 2, 3}. Από το Θεώρημα του Bachet (Part 1), οι θέσεις ήττας (P-positions) είναι τα πολλαπλάσια του (k+1) = 4.

L = P-positions = {0, 4, 8, 12, ...} = {4m : m ∈ ℕ₀}

Ανάλυση: Επειδή 100 = 4 × 25, το 100 ανήκει στο L. Άρα η αρχική θέση είναι P-position.

Απάντηση: Ο ΔΕΥΤΕΡΟΣ παίκτης κερδίζει.

Winning Strategy για τον Δεύτερο: Αν ο πρώτος παίρνει k πέτρες (όπου k ∈ {1,2,3}), ο δεύτερος παίρνει (4−k) πέτρες. Έτσι, μετά από κάθε ζευγάρι κινήσεων έχουν αφαιρεθεί ακριβώς 4 πέτρες. Επειδή 100 ≡ 0 (mod 4), ο δεύτερος παίρνει πάντα την τελευταία πέτρα.

Πηγή: Κλασικό πρόβλημα, εμφανίζεται σε κάθε εισαγωγή σε combinatorial game theory. Βλ. Winning Ways for your Mathematical Plays (Berlekamp, Conway, Guy).

Problem 2: The Coin Game (Κλασικό Training Πρόβλημα)

Πρόβλημα: Υπάρχουν 2n νομίσματα σε γραμμή, με αξίες c₁, c₂, ..., c₂ₙ (γνωστές και στους δύο παίκτες). Δύο παίκτες παίζουν εναλλάξ. Κάθε κίνηση: παίρνεις ένα νόμισμα από οποιοδήποτε άκρο της γραμμής. Ο παίκτης με το μεγαλύτερο σύνολο κερδίζει. Δείξτε ότι ο πρώτος παίκτης μπορεί πάντα να εγγυηθεί τουλάχιστον ισοπαλία.

Ιδέα: Pairing strategy. Χωρίζουμε τα νομίσματα σε n ζευγάρια: (1,2), (3,4), ..., (2n−1, 2n).

Βασική Παρατήρηση: Ο πρώτος παίκτης μπορεί να ελέγξει ποιο ζευγάρι θα πάρει σε κάθε γύρο. Συγκεκριμένα:

Υπολογίζει S_odd = c₁ + c₃ + c₅ + ... + c₂ₙ₋₁ (άθροισμα περιττών θέσεων)
Υπολογίζει S_even = c₂ + c₄ + c₆ + ... + c₂ₙ (άθροισμα άρτιων θέσεων)

Strategy:

Αν S_odd ≥ S_even: Ο πρώτος παίκτης ξεκινάει παίρνοντας το c₁ (πρώτο νόμισμα, περιττή θέση). Στη συνέχεια, ό,τι και να κάνει ο αντίπαλος, ο πρώτος παίρνει το άλλο νόμισμα του ίδιου ζευγαριού. Έτσι εξασφαλίζει όλα τα νομίσματα σε περιττές θέσεις.
Αν S_even > S_odd: Αντίστοιχα, ξεκινάει με c₂ και εξασφαλίζει όλα τα άρτια.

Απόδειξη: Έστω S = S_odd + S_even το συνολικό άθροισμα. Τότε:

max(S_odd, S_even) ≥ (S_odd + S_even)/2 = S/2

Άρα ο πρώτος παίκτης εξασφαλίζει τουλάχιστον τα μισά από το συνολικό άθροισμα, δηλαδή τουλάχιστον ισοπαλία.

Πηγή: Κλασικό πρόβλημα greedy/pairing strategy που εμφανίζεται σε πολλές παραλλαγές σε βιβλία και σε διαγωνισμούς προπόνησης. Η αρχική αναφορά σε "Balkan MO 2002, Problem 4" δεν επιβεβαιώθηκε κατά τον έλεγχο πηγών και αφαιρέθηκε.

Problem 3: Wythoff's Game (Κλασικό Θεώρημα, 1907)

Πρόβλημα: Δύο σωροί με m και n πέτρες. Κάθε κίνηση: είτε αφαιρείς οποιονδήποτε αριθμό πετρών από έναν σωρό (standard Nim), είτε αφαιρείς τον ίδιο αριθμό πετρών και από τους δύο σωρούς. Ο παίκτης που παίρνει την τελευταία πέτρα κερδίζει. Χαρακτηρίστε όλες τις P-positions.

Αναγνώριση: Αυτό είναι το κλασικό Wythoff's Game. Είναι impartial game, άρα μπορούμε να χρησιμοποιήσουμε Sprague-Grundy theory. Όμως, λόγω του "remove same from both", το πρόβλημα έχει elegant closed-form λύση.

Θεώρημα (Wythoff, 1907): Οι P-positions του Wythoff's Game είναι τα ζευγάρια:

(⌊kφ⌋, ⌊kφ²⌋) για k = 0, 1, 2, ...

όπου φ = (1 + √5)/2 είναι ο χρυσός αριθμός. Ισοδύναμα: (⌊kφ⌋, ⌊kφ⌋ + k).

Απόδειξη (Sketch):

Beatty's Theorem: Οι ακολουθίες ⌊kφ⌋ και ⌊kφ²⌋ χωρίζουν τους φυσικούς αριθμούς (κάθε n εμφανίζεται ακριβώς μία φορά σε μία από τις δύο).
Terminal: (0,0) είναι P-position (αντιστοιχεί σε k=0).
Closure under moves: Από κάθε P-position, κάθε επιτρεπτή κίνηση οδηγεί σε N-position (λόγω των ιδιοτήτων του φ).
Reachability: Από κάθε N-position, υπάρχει κίνηση σε P-position.

Πρώτες P-positions:

k	⌊kφ⌋	⌊kφ²⌋
0	0	0
1	1	2
2	3	5
3	4	7
4	6	10
5	8	13

Πηγή: Wythoff, W. A. (1907), "A Modification of the Game of Nim", Annals of Mathematics. Επίσης Winning Ways, Chapter 4. (Η αρχική αναφορά σε "IMO Shortlist 1993, C7" δεν επιβεβαιώθηκε κατά τον έλεγχο πηγών και αφαιρέθηκε — το θεώρημα του Wythoff είναι ούτως ή άλλως κλασικό αποτέλεσμα του 1907, ανεξάρτητο διαγωνισμών.)

Problem 4: The Subtraction-Split Game (Training Πρόβλημα)

Πρόβλημα: Ένας σωρός με n πέτρες. Κάθε κίνηση: είτε αφαιρείς οποιονδήποτε θετικό αριθμό πετρών (1 έως n), είτε χωρίζεις τον σωρό σε δύο μη-κενούς σωρούς. Ο παίκτης που δεν μπορεί να κινηθεί χάνει. Υπολογίστε τα Grundy numbers g(n) για n ≤ 20 και βρείτε τη νικήτρια στρατηγική για (7, 11, 13).

Ορισμός Grundy: Για κάθε n, οι επιτρεπτές κινήσεις είναι:

Standard Nim: n → n−k για k = 1, ..., n (άρα φτάνουμε σε θέσεις με Grundy g(0), g(1), ..., g(n−1))
Split: n → (a, n−a) για a = 1, ..., n−1 (άρα Grundy = g(a) ⊕ g(n−a))

Άρα:

g(n) = mex({g(0), g(1), ..., g(n−1)} ∪ {g(a) ⊕ g(n−a) : 1 ≤ a < n})

Υπολογισμός (βήμα-βήμα):

g(0) = 0                                    (terminal)
g(1) = mex({0}) = 1
g(2) = mex({0, 1, g(1)⊕g(1)}) 
     = mex({0, 1, 0}) = 2
g(3) = mex({0, 1, 2, g(1)⊕g(2), g(2)⊕g(1)})
     = mex({0, 1, 2, 1⊕2, 2⊕1}) 
     = mex({0, 1, 2, 3}) = 4
g(4) = mex({0,1,2,4, g(1)⊕g(3), g(2)⊕g(2)})
     = mex({0,1,2,4, 1⊕4, 2⊕2})
     = mex({0,1,2,4, 5, 0}) = 3

Πλήρης πίνακας Grundy numbers (επαληθευμένος βήμα-βήμα από 0 έως 13):

n	0	1	2	3	4	5	6	7	8	9	10	11	12	13
g(n)	0	1	2	4	3	5	6	8	7	9	10	12	11	13
binary	0000	0001	0010	0100	0011	0101	0110	1000	0111	1001	1010	1100	1011	1101

Παρατήρηση (Pattern): Για n = 2ᵏ − 1, έχουμε g(n) = 2ᵏ. Για n = 2ᵏ, έχουμε g(n) = 2ᵏ − 1. Για τα περισσότερα άλλα n, ισχύει g(n) = n ή g(n) = n ± 1. Το pattern δεν είναι τετριμμένο — αυτό κάνει το παιχνίδι ενδιαφέρον!

Εφαρμογή σε (7, 11, 13):

g(7) = 8, g(11) = 12, g(13) = 13

g_total = 8 ⊕ 12 ⊕ 13 = 1000₂ ⊕ 1100₂ ⊕ 1101₂ = 1001₂ = 9 ≠ 0

Άρα η αρχική θέση είναι N-position — ο πρώτος παίκτης κερδίζει.

Εύρεση Winning Move: Πρέπει να βρούμε κίνηση που κάνει το XOR = 0.

Σωρός 7: Θέλουμε g(7) → x τέτοιο ώστε 9 ⊕ 8 ⊕ x = 0, άρα x = 1. Πράγματι g(1) = 1. Winning move: 7 → 1 (standard Nim).
Σωρός 11: Θέλουμε x = 9 ⊕ 12 = 5. Πράγματι g(5) = 5. Winning move: 11 → 5 (standard Nim).
Σωρός 13: Θέλουμε x = 9 ⊕ 13 = 4. Πράγματι g(3) = 4. Winning move: 13 → 3 (standard Nim).

Υπάρχουν και split moves να ελεγχθούν: π.χ. split 13 → (3,10) δίνει συνδυασμένη τιμή g(3)⊕g(10) = 4⊕10 = 14. Για να είναι winning θα έπρεπε αυτό να ισούται με g(7)⊕g(11) = 8⊕12 = 4· αφού 14 ≠ 4, η κίνηση αυτή δεν είναι winning.

Πηγή: Training πρόβλημα που συνδυάζει subtraction game με "split" κίνηση — κλασική τεχνική σε βιβλία combinatorial game theory. Η αρχική αναφορά σε "IMO Shortlist 2001, C4" ήταν λανθασμένη (το πραγματικό SL 2001 C4 αφορά "historic sets", ένα εντελώς άσχετο θέμα number theory) και αφαιρέθηκε. Βλ. Lessons in Play (Albert, Nowakowski, Wolfe) για τη γενική τεχνική split-games.

Problem 5: The IMO 2025 Game (Alice & Bazza — IMO 2025/5)

Πρόβλημα: Οι Alice και Bazza παίζουν ένα παιχνίδι με παράμετρο λ > 0. Στην n-οστή κίνηση (ξεκινώντας από n=1):

Αν n περιττός: Η Alice επιλέγει xₙ ≥ 0 με x₁ + x₂ + ... + xₙ ≤ λ·n
Αν n άρτιος: Ο Bazza επιλέγει xₙ ≥ 0 με x₁² + x₂² + ... + xₙ² ≤ n

Αν ένας παίκτης δεν μπορεί να επιλέξει, χάνει. Αν το παιχνίδι συνεχίζεται για πάντα, κανείς δεν κερδίζει. Βρείτε όλες τις τιμές του λ για τις οποίες η Alice έχει winning strategy και όλες τις τιμές για τις οποίες ο Bazza έχει winning strategy.

Πηγή: IMO 2025, Problem 5. Proposed by Massimiliano Foschi & Leonardo Franchi (Italy) — επιβεβαιωμένο. Official solutions: Evan Chen — IMO 2025 Solution Notes, §2.2.

Απάντηση: Alice κερδίζει για λ > 1/√2. Bazza κερδίζει για λ < 1/√2. Για λ = 1/√2, κανείς δεν μπορεί να εγγυηθεί νίκη.

Ιδέα: Υπάρχει ανταγωνισμός μεταξύ ℓ₁-norm (Alice) και ℓ₂-norm (Bazza). Η βασική ανισότητα είναι: για t ≥ 0,

t + √(2 − t²) ≥ √2

με ισότητα όταν t = 1. Αυτό υποδεικνύει το κρίσιμο κατώφλι λ = 1/√2.

Μέρος Α: Bazza κερδίζει για λ ≤ 1/√2

Στρατηγική Bazza: Όταν η Alice παίζει x₂ₖ₋₁, ο Bazza παίζει x₂ₖ = √(2 − x₂ₖ₋₁²), τη μέγιστη επιτρεπτή τιμή.

Τότε x₂ₖ₋₁² + x₂ₖ² = 2, άρα μετά από k γύρους: x₁² + x₂² + ... + x₂ₖ² = 2k.

Από Cauchy-Schwarz: x₁ + x₂ + ... + x₂ₖ ≤ √(2k · 2k) = 2k. Άρα η σειρά Alice δεν ξεπερνάει το όριό της.

Από την ανισότητα t + √(2−t²) ≥ √2, έχουμε:
x₁ + x₂ + ... + x₂ₖ ≥ k√2.

Η Alice πρέπει να ικανοποιεί: x₁ + ... + x₂ₖ₊₁ ≤ λ(2k+1).
Άρα x₂ₖ₊₁ ≤ λ(2k+1) − k√2.

Για λ < 1/√2, το δεξί μέλος γίνεται αρνητικό για μεγάλα k, άρα η Alice δεν μπορεί να κινηθεί.

Μέρος Β: Alice κερδίζει για λ > 1/√2

Στρατηγική Alice (A-Spike-K): Η Alice παίζει 0 στις κινήσεις 1, 3, ..., 2K−3. Στην κίνηση 2K−1 παίζει το μέγιστο δυνατό.

Επειδή ο Bazza είναι περιορισμένος από ℓ₂, από QM-AM: x₂ + x₄ + ... + x₂ₖ ≤ √2 · k.
Άρα το budget της Alice: x₂ₖ₊₁ ≤ λ(2k+1) − √2 · k > 0 για όλα τα k (αφού λ > 1/√2).

Επιλέγουμε K αρκετά μεγάλο ώστε λ(2K−1) > K√2. Τότε στην κίνηση 2K−1, η Alice παίζει x₂ₖ₋₁ = λ(2K−1) − S₂ₖ₋₂ > √2. Αυτό αναγκάζει τον Bazza να έχει x₂ₖ² ≤ 2K − (2K−2 + x₂ₖ₋₁²) < 0, άδυνατο. Ο Bazza χάνει.

Μέρος Γ: λ = 1/√2
Και οι δύο παίκτες μπορούν να εξασφαλίσουν ότι το παιχνίδι συνεχίζεται επ' άπειρον (draw). Κανείς δεν μπορεί να εγγυηθεί νίκη.

Problem 6: The Chocolate Bar Game (Misère 2-Pile Nim σε μεταμφίεση)

Πρόβλημα: Ένας πίνακας από σοκολάτα m × n. Κάθε κίνηση: διαλέγεις ένα ορθογώνιο και το κόβεις οριζόντια ή κατακόρυφα σε δύο μικρότερα ορθογώνια, παίρνοντας το ένα κομμάτι και αφήνοντας το άλλο. Ο παίκτης που αφήνει 1×1 χάνει (Misère). Ποιος κερδίζει;

Αναγνώριση: Κάθε κίνηση (οριζόντια ή κάθετη κοπή) αλλάζει μία μόνο από τις δύο διαστάσεις (m ή n) σε οποιαδήποτε μικρότερη θετική τιμή — ένα ίσιο κόψιμο δεν μπορεί ποτέ να αλλάξει και τις δύο διαστάσεις ταυτόχρονα.

⚠️ Αυτό ΔΕΝ είναι Wythoff's Game. Το Wythoff επιτρέπει επιπλέον κίνηση (αφαίρεση του ίδιου αριθμού και από τις δύο "στοίβες" ταυτόχρονα) — κάτι αδύνατο με ένα ίσιο κόψιμο σοκολάτας. Στην πραγματικότητα, το παιχνίδι είναι Misère 2-Pile Nim: θέτοντας a = m−1, b = n−1 (a,b ≥ 0), κάθε κίνηση μειώνει το a ή το b σε οποιαδήποτε μικρότερη μη-αρνητική τιμή, και το να φτάσεις σε (a,b)=(0,0) [δηλαδή αρχικό (m,n)=(1,1)] είναι η χαμένη κίνηση.

Θεωρία Misère 2-Pile Nim: Στο κανονικό (normal-play) 2-pile Nim, οι P-positions είναι τα ζευγάρια με ίσες στοίβες (a=b — mirror strategy). Στο misère παίζεις ακριβώς όπως στο κανονικό παιχνίδι, εκτός όταν πλησιάζεις στην περιοχή όπου και οι δύο στοίβες είναι ≤ 1 — εκεί ο κανόνας αντιστρέφεται (βλ. Misère Nim, Part 2/3).

Πλήρης Χαρακτηρισμός (σε αρχικές συντεταγμένες m, n ≥ 1):

Αν max(m,n) ≥ 3: P-position ⟺ m = n (όπως το κανονικό 2-pile Nim)
Εξαίρεση (2,2): Είναι N-position (ο μετακινούμενος κερδίζει) — σπάει τον κανόνα "m=n"!
Εξαιρέσεις (1,2) και (2,1): P-positions (ο μετακινούμενος χάνει)

Απόδειξη των εξαιρέσεων:

• Από (1,2): η μόνη δυνατή κίνηση είναι να μειωθεί το n από 2 σε 1, αφήνοντας (1,1) — που είναι ακριβώς η χαμένη κίνηση! Άρα (1,2) είναι Losing για τον μετακινούμενο.

• Από (2,2): ο μετακινούμενος κόβει σε (1,2), στέλνοντας τον αντίπαλο σε P-position. Ο αντίπαλος αναγκάζεται τελικά να είναι αυτός που αφήνει το (1,1). Άρα (2,2) είναι Winning για τον μετακινούμενο.

Απάντηση: Ο πρώτος παίκτης κερδίζει ⟺ m ≠ n, εκτός από τις εξαιρέσεις: αν (m,n) = (2,2), κερδίζει ο πρώτος (παρόλο που m=n)· αν (m,n) ∈ {(1,2),(2,1)}, κερδίζει ο δεύτερος (παρόλο που m≠n). Για όλα τα υπόλοιπα ζεύγη με max(m,n) ≥ 3, ισχύει η απλή αρχή: κερδίζει ο πρώτος ⟺ m ≠ n.

Πηγή: Το παιχνίδι είναι ισοδύναμο με Misère 2-Pile Nim, κλασικό αποτέλεσμα combinatorial game theory (Bouton, 1901· Winning Ways, Chapter 1). Η αρχική αναφορά σε "IMO Shortlist 2007, C5" ήταν λανθασμένη (το πραγματικό SL 2007 C5 αφορά έγχρωμες λωρίδες στο επίπεδο, εντελώς άσχετο θέμα) — αφαιρέθηκε, όπως και ο εσφαλμένος χαρακτηρισμός "Wythoff's Game σε Misère form" που είχε αρχικά δοθεί.

Problem 7: Strategy Stealing — The Hex Theorem (John Nash, 1952)

Πρόβλημα: Στο παιχνίδι Hex σε n × n board, οι δύο παίκτες (Blue/Red) τοποθετούν εναλλάξ πούλια σε κενά hexagons. Ο Blue κερδίζει αν σχηματίζει συνεχή γραμμή από αριστερά προς δεξιά, ο Red από πάνω προς τα κάτω. Δείξτε ότι ο πρώτος παίκτης έχει winning strategy.

Θεώρημα (Nash): Στο Hex, ο πρώτος παίκτης πάντα κερδίζει (με βέλτιστο παιχνίδι και από τους δύο).

Απόδειξη (Strategy Stealing):

Υποθέτουμε ότι ο δεύτερος παίκτης έχει winning strategy.
Ο πρώτος παίκτης κάνει μια τυχαία πρώτη κίνηση (π.χ. στο κέντρο) και μετά υποκρίνεται ότι είναι δεύτερος, ακολουθώντας τη winning strategy του δεύτερου.
Αν η strategy του λέει να παίξει στο ίδιο τετράγωνο που ήδη κατέχει (λόγω της τυχαίας πρώτης κίνησης), κάνει μια άλλη τυχαία κίνηση και συνεχίζει.
Έχοντας ένα "έξτρα" πούλι στο board, ο πρώτος παίκτης είναι σε ισχυρότερη θέση από τον δεύτερο. Άρα η υποτιθέμενη winning strategy του δεύτερου οδηγεί τον πρώτο σε νίκη — άτοπο.

Σημαντική Παρατήρηση: Το strategy stealing δεν δίνει constructive strategy. Δεν ξέρουμε ποια είναι η winning strategy του πρώτου — μόνο ότι υπάρχει. Αυτό είναι χαρακτηριστικό του strategy stealing argument.

Πηγή: John Nash (1952). Βλ. Hex Strategy (Browne) και Winning Ways, Chapter 22. Το Hex είναι κλασικό παράδειγμα strategy stealing σε partizan games.

3. Master Reference Guide

Complete Technique Reference

Technique	When to Use	Key Formula / Idea	Source
Bachet's Theorem	Subtraction game M = {1,...,k}	P = {(k+1)m}	Part 1
Sprague-Grundy	Impartial games	g(S) = mex{g(T) : S→T}	Part 2
XOR Theorem	Disjunctive sum	g(G₁+G₂+...) = g(G₁) ⊕ g(G₂) ⊕ ...	Part 2
Wythoff's Formula	Wythoff's Game (remove + same)	P = (⌊kφ⌋, ⌊kφ²⌋)	Wythoff, 1907
Pairing Strategy	Symmetric positions, coin games	Mirror / Control pairs	Part 3
Strategy Stealing	Prove first player doesn't lose	Contradiction via extra move	Part 3
Parity Argument	Fixed total moves	Odd/Even analysis	Part 3
Misère Nim	Nim with last move loses	Play normal until all piles ≤1, then leave opponent an odd count	Part 2

Problem-Type Decision Tree

START: Read problem carefully │ ├─ Has obvious symmetry? │ └─ YES → Try Pairing / Mirror Strategy │ ├─ Is it impartial? (same moves for both players) │ ├─ YES → Single game or sum of games? │ │ ├─ Single → Calculate Grundy numbers │ │ └─ Sum → XOR of Grundy numbers │ │ │ └─ NO → Partizan game │ ├─ Can prove first player doesn't lose? │ │ └─ YES → Strategy Stealing │ └─ NO → Case analysis / explicit strategy │ ├─ Fixed number of moves? │ └─ YES → Parity argument │ ├─ Graph / geometric structure? │ └─ YES → Hackenbush / Hex / pairing on structure │ ├─ Restricted moves (not standard Nim)? │ └─ YES → Modified Grundy / Case analysis │ └─ Last move loses (Misère)? └─ YES → Misère analysis (careful with all-1s case)

4. Competition Strategy & Tips

Time Management

Problem Type	Estimated Time	Key Action
Bachet-type (subtraction)	10–15 min	Immediate pattern recognition
Standard Nim / Grundy	15–25 min	Careful XOR calculation
Wythoff / Beatty	20–30 min	Verify pattern with small cases
Strategy Stealing	15–20 min	Clear contradiction structure
Novel / Partizan	40–60 min	Multiple small cases, look for invariants

Common Traps

Don't assume impartial without checking. Πολλά προβλήματα φαίνονται impartial αλλά είναι partizan.
Don't forget Misère modifications. Το Misère Nim έχει ειδική περίπτωση όταν όλοι οι σωροί έχουν ≤1 πέτρα.
Verify XOR calculations. Ένα λάθος bit = λάθος απάντηση. Κάνε τον υπολογισμό δύο φορές.
Check edge cases. n = 0, n = 1, άδειος σωρός, μοναδική κίνηση.
Μην υποθέτεις ότι δύο παιχνίδια είναι "ίδια" επειδή μοιάζουν. Το chocolate-bar παιχνίδι του Προβλήματος 6 φαίνεται σαν Wythoff αλλά ΔΕΝ είναι — έλεγξε πάντα ΑΚΡΙΒΩΣ ποιες κινήσεις επιτρέπονται.
Strategy Stealing ≠ Constructive. Αποδεικνύει ύπαρξη, όχι concrete strategy.

Proof Writing Checklist

State clearly who wins (First or Second player).
Describe the winning strategy explicitly.
Prove that the strategy is always legal (feasible moves).
Prove that following the strategy leads to victory.
Handle all cases (don't miss edge cases).
Conclude with the final answer in the required format.

5. Ultimate Challenge: The Split-Nim Grand Finale

Problem: Split-Nim on Three Piles

Πρόβλημα: Τρεις σωροί με (7, 11, 13) πέτρες. Κάθε κίνηση: διάλεξε ΕΝΑΝ σωρό και είτε αφαίρεσε οποιονδήποτε αριθμό πετρών (standard Nim), είτε χώρισέ τον σε δύο μη-κενούς σωρούς. Ο παίκτης που δεν μπορεί να κινηθεί χάνει. Ποιος κερδίζει και ποια είναι η βέλτιστη πρώτη κίνηση;

Βήμα 1: Υπολογίζουμε τα Grundy numbers g(n) για το split-Nim (βλ. Problem 4 παραπάνω, πλήρως επαληθευμένος πίνακας).

Βήμα 2: Υπολογίζουμε το συνολικό Grundy:

g(7) = 8, g(11) = 12, g(13) = 13
g_total = 8 ⊕ 12 ⊕ 13 = 1000₂ ⊕ 1100₂ ⊕ 1101₂ = 1001₂ = 9 ≠ 0

Άρα: N-position — ο ΠΡΩΤΟΣ παίκτης κερδίζει.

Βήμα 3 — Εύρεση Winning Move: Πρέπει g_total → 0.

Pile	Current g	Target g	Required move
7	8	8 ⊕ 9 = 1	7 → 1 (remove 6)
11	12	12 ⊕ 9 = 5	11 → 5 (remove 6)
13	13	13 ⊕ 9 = 4	13 → 3 (remove 10)

Όλες οι παραπάνω είναι valid standard Nim moves! Ο πρώτος παίκτης έχει 3 winning moves.

Βέλτιστη πρώτη κίνηση: Μείωσε τον σωρό 7 σε 1 (αφαίρεσε 6 πέτρες) — ή ισοδύναμα, μείωσε τον 11 σε 5, ή τον 13 σε 3. Μετά την κίνηση, το XOR είναι 0 και ο δεύτερος παίκτης βρίσκεται σε P-position.

Series Complete

Game Theory Marathon — 4 Parts

Part 1: Nim Games, L/W Positions, Bachet's Game

Part 2: Sprague-Grundy Theory, Nimbers, XOR

Part 3: Advanced Strategies, Partizan Games, Symmetry

Part 4: IMO Problems & Competition Mastery

Με 7 fully-solved προβλήματα, complete technique reference, και verified mathematical rigor.

🔗 Αν σου διέφυγε: Part 3 - Advanced Strategies & Complex Games

Πλήρης λίστα πηγών:

Evan Chen, IMO 2025 Solution Notes — web.evanchen.cc
Berlekamp, Conway, Guy — Winning Ways for your Mathematical Plays (4 vols)
Albert, Nowakowski, Wolfe — Lessons in Play: An Introduction to Combinatorial Game Theory
AoPS Community — artofproblemsolving.com/community/c13_olympiads
IMO Shortlist Archives — imo-official.org