🧡 2026 Math Marathon: Game Theory #2 - Sprague-Grundy Theorem & Nimbers | XOR Strategy Mastery

🎮 2026 MATH MARATHON - GAME THEORY #2

Game Theory Mastery

Part 2: Sprague-Grundy Theory & Nimbers - Η Μαγεία των Grundy Numbers

🔗 Σύνδεση με Part 1:
Part 1: Nim Games, Winning/Losing positions, Bachet's Game
Part 2 (σήμερα): Sprague-Grundy Theory - The Ultimate Tool!

Τι θα μάθετε σήμερα:
✅ Grundy Numbers (nimbers) - Τι είναι;
✅ Mex Function (minimum excludant)
✅ Sprague-Grundy Theorem (THE theorem!)
✅ Game Sums & XOR strategy
✅ Impartial games complete theory
✅ 7 advanced examples
✅ Competition mastery techniques

🤔 Η Μεγάλη Ερώτηση:
Στο Part 1 υπολογίζαμε \(L\) και \(W\) case-by-case. Αλλά τι γίνεται όταν έχουμε **πολλαπλά παιχνίδια ταυτόχρονα**; Πώς συνδυάζουμε strategies; Η απάντηση: Sprague-Grundy Theory - το πιο powerful εργαλείο στη Game Theory! 🎯

🎯 1. Grundy Numbers - The Magic Concept

📌 Ορισμός: Grundy Number (Nimber)

Για κάθε θέση \(P\) ενός impartial game, ορίζουμε τον Grundy number \(g(P)\) αναδρομικά:

\[ g(P) = \text{mex}\{g(P') : P' \text{ είναι θέση που μπορούμε να φτάσουμε από } P\} \]

όπου mex (minimum excludant) είναι ο μικρότερος μη-αρνητικός ακέραιος που **δεν** ανήκει στο σύνολο.

Με απλά λόγια:
Ο Grundy number μιας θέσης είναι ο μικρότερος φυσικός αριθμός που δεν εμφανίζεται στους Grundy numbers των θέσεων που μπορούμε να πάμε!

🔢 Mex Function - Minimum Excludant

Ορισμός:
\[ \text{mex}(S) = \min\{n \in \mathbb{N} \cup \{0\} : n \notin S\} \]

Παραδείγματα:
• \(\text{mex}(\{1, 2, 3\}) = 0\)
• \(\text{mex}(\{0, 2, 3\}) = 1\)
• \(\text{mex}(\{0, 1, 3, 4\}) = 2\)
• \(\text{mex}(\{0, 1, 2, 3\}) = 4\)
• \(\text{mex}(\emptyset) = 0\)
• \(\text{mex}(\{2, 5, 7\}) = 0\)

🎲 Η Σύνδεση με L και W

Θεώρημα (Βασικό):
Μια θέση \(P\) είναι:

• Losing position (L) αν και μόνο αν \(g(P) = 0\)

• Winning position (W) αν και μόνο αν \(g(P) > 0\)

Γιατί αυτό είναι τόσο powerful;
Αντί να ελέγχουμε "υπάρχει κίνηση σε L;", απλά **υπολογίζουμε έναν αριθμό**!

📚 2. Υπολογισμός Grundy Numbers

🔹 Παράδειγμα 1: Bachet's Game Grundy Numbers Πρόβλημα: Υπολογίστε τους Grundy numbers για Bachet's game με \(M = \{1, 2, 3\}\).

Λύση:

Base case:
Position 0 (terminal): Δεν υπάρχουν κινήσεις → successors = \(\emptyset\)
\[ g(0) = \text{mex}(\emptyset) = 0 \]

Position 1:
Μπορώ να πάω μόνο στο 0 (με -1)
\[ g(1) = \text{mex}(\{g(0)\}) = \text{mex}(\{0\}) = 1 \]

Position 2:
Μπορώ να πάω στο 1 (με -1) ή 0 (με -2)
\[ g(2) = \text{mex}(\{g(1), g(0)\}) = \text{mex}(\{1, 0\}) = 2 \]

Position 3:
Μπορώ να πάω στο 2, 1, ή 0 (με -1, -2, -3)
\[ g(3) = \text{mex}(\{g(2), g(1), g(0)\}) = \text{mex}(\{2, 1, 0\}) = 3 \]

Position 4:
Μπορώ να πάω στο 3, 2, ή 1 (με -1, -2, -3)
\[ g(4) = \text{mex}(\{g(3), g(2), g(1)\}) = \text{mex}(\{3, 2, 1\}) = 0 \]

Αυτό είναι L! (όπως ξέραμε από Part 1: \(4 = 1 \cdot (3+1)\))

Complete Table:

Position n	Successors	g(successors)	g(n)	L/W
0	∅	∅	0	L
1	{0}	{0}	1	W
2	{1,0}	{1,0}	2	W
3	{2,1,0}	{2,1,0}	3	W
4	{3,2,1}	{3,2,1}	0	L
5	{4,3,2}	{0,3,2}	1	W
6	{5,4,3}	{1,0,3}	2	W
7	{6,5,4}	{2,1,0}	3	W
8	{7,6,5}	{3,2,1}	0	L

Παρατήρηση:
\[ g(n) = n \bmod 4 \]

Άρα \(g(n) = 0 \Leftrightarrow n \equiv 0 \pmod{4} \Leftrightarrow n\) είναι πολλαπλάσιο του \(4 = k+1\)! ✓

🔹 Παράδειγμα 2: Power of 2 Game Grundy Πρόβλημα: \(M = \{1, 2, 4, 8, \ldots\}\). Υπολογίστε \(g(n)\).

Λύση:

n	Successors	g(successors)	g(n)	L/W
0	∅	∅	0	L
1	{0}	{0}	1	W
2	{1,0}	{1,0}	2	W
3	{2,1}	{2,1}	0	L
4	{3,2,0}	{0,2,0}	1	W
5	{4,3,1}	{1,0,1}	2	W
6	{5,4,2}	{2,1,2}	0	L

Pattern: \(g(n) = n \bmod 3\)

Άρα \(g(n) = 0 \Leftrightarrow n\) πολλαπλάσιο του 3! ✓

🏆 3. The Sprague-Grundy Theorem

👑 Sprague-Grundy Theorem (1935-1939)

Το πιο σημαντικό θεώρημα στη combinatorial game theory!

Θεώρημα:
Κάθε impartial game είναι ισοδύναμο με ένα Nim pile!

Συγκεκριμένα, ένα παιχνίδι με Grundy number \(g\) είναι ισοδύναμο με:

Ένα Nim pile με \(g\) αντικείμενα

Τι σημαίνει "ισοδύναμο";
Έχουν την ίδια winning/losing στρατηγική!

🎲 Game Sums & XOR

Πρόβλημα: Παίζουμε \(k\) παιχνίδια ταυτόχρονα. Κάθε κίνηση, διαλέγουμε ΕΝΑ παιχνίδι και κάνουμε κίνηση σε αυτό. Ο παίκτης που δεν μπορεί να κινηθεί χάνει.

Grundy Number του Combined Game:

\[ g(G_1 + G_2 + \cdots + G_k) = g(G_1) \oplus g(G_2) \oplus \cdots \oplus g(G_k) \]

όπου \(\oplus\) είναι το XOR (exclusive OR)!

XOR Reminder:
• \(0 \oplus 0 = 0\)
• \(0 \oplus 1 = 1\)
• \(1 \oplus 0 = 1\)
• \(1 \oplus 1 = 0\)

Για αριθμούς: XOR bit-by-bit
• \(3 \oplus 5 = 011_2 \oplus 101_2 = 110_2 = 6\)
• \(2 \oplus 3 \oplus 1 = 010_2 \oplus 011_2 \oplus 001_2 = 000_2 = 0\)

🎮 4. Classic Nim Game

🔹 Παράδειγμα 3: Multi-Pile Nim Πρόβλημα: Nim με \(k\) piles: \((a_1, a_2, \ldots, a_k)\). Κάθε κίνηση: διάλεξε ένα pile και πάρε οποιοδήποτε (θετικό) αριθμό. Ποιος κερδίζει;

Λύση:

Grundy Number ενός Single Pile:

Ένα pile με \(n\) αντικείμενα:
• Μπορούμε να πάμε σε \(0, 1, 2, \ldots, n-1\)
• Άρα \(g(n) = \text{mex}(\{0, 1, \ldots, n-1\}) = n\)

Δηλαδή: Το Grundy number ενός pile είναι ο αριθμός αντικειμένων!

Combined Game:

Για piles \((a_1, a_2, \ldots, a_k)\):
\[ g = a_1 \oplus a_2 \oplus \cdots \oplus a_k \]

Winning Strategy:
• Αν \(g = 0\): Losing position
• Αν \(g \neq 0\): Winning position - κινήσου ώστε το XOR να γίνει 0!

Παράδειγμα:
Piles: (3, 5, 7)

XOR calculation:

  3 = 011₂
  5 = 101₂
  7 = 111₂
  ⊕ = 001₂ = 1
            

Άρα \(g = 1 \neq 0\) → Winning position!

Winning move: Κάνε το XOR = 0

Αν πάρω από το pile 7:
• Θέλω: \(3 \oplus 5 \oplus x = 0\)
• Άρα: \(x = 3 \oplus 5 = 011_2 \oplus 101_2 = 110_2 = 6\)

Move: Pile 7 → 6
New state: (3, 5, 6)
Check: \(3 \oplus 5 \oplus 6 = 011 \oplus 101 \oplus 110 = 000 = 0\) ✓

🔹 Παράδειγμα 4: Nim Sum Properties Ιδιότητες του XOR (Nim Sum):

1. Commutative: \(a \oplus b = b \oplus a\)

2. Associative: \((a \oplus b) \oplus c = a \oplus (b \oplus c)\)

3. Identity: \(a \oplus 0 = a\)

4. Self-inverse: \(a \oplus a = 0\)

5. Cancellation: Αν \(a \oplus b = c\), τότε \(a = b \oplus c\)

Χρήσιμο: Για να βρούμε ποιο pile να αλλάξουμε:
Αν \(g = a_1 \oplus a_2 \oplus \cdots \oplus a_k \neq 0\), θέλουμε \(a_i' \oplus (g \oplus a_i) = 0\)
Άρα: \(a_i' = g \oplus a_i\)

📊 5. Advanced Examples

🔹 Παράδειγμα 5: Misère Nim Πρόβλημα: Nim αλλά ο παίκτης που παίρνει το τελευταίο αντικείμενο χάνει! (Misère version)

Λύση:

Στρατηγική:

1. Αν όλα τα piles έχουν μέγεθος ≤ 1:
• Κερδίζεις αν υπάρχει περιττός αριθμός piles με 1 αντικείμενο

2. Αλλιώς (υπάρχει pile ≥ 2):
• Παίζεις σαν κανονικό Nim (κάνε XOR = 0)
• Μέχρι να φτάσεις σε κατάσταση με piles ≤ 1

Παράδειγμα:
• (3, 5, 7): XOR = 1 → κάνε (3, 5, 6), continue normal Nim
• (1, 1, 1): 3 piles → losing (θα πάρεις το τελευταίο!)
• (1, 1): 2 piles → winning (πάρε 1, αφήνοντας (0, 1))

🔹 Παράδειγμα 6: Staircase Nim Πρόβλημα: Υπάρχουν \(n\) σκαλοπάτια με \(a_i\) νομίσματα στο \(i\)-οστό. Κάθε κίνηση: διάλεξε ένα σκαλοπάτι \(i > 0\) και μετακίνησε οποιοδήποτε αριθμό νομισμάτων στο σκαλοπάτι \(i-1\). Ο παίκτης που δεν μπορεί να κινηθεί χάνει.

Λύση:

Grundy Analysis:

Το Grundy number είναι:
\[ g = a_1 \oplus a_3 \oplus a_5 \oplus \cdots \]

Δηλαδή: XOR των περιττών θέσεων μόνο!

Γιατί; Τα άρτια σκαλοπάτια είναι "transit" - δεν επηρεάζουν το outcome!

Παράδειγμα:
Stairs: (2, 3, 1, 4, 5) (positions 0,1,2,3,4)
Grundy: \(g = a_1 \oplus a_3 = 3 \oplus 4 = 011_2 \oplus 100_2 = 111_2 = 7\)
Winning position!

🔹 Παράδειγμα 7: Green Hackenbush (Intro) Πρόβλημα: Γράφος με edges. Κάθε κίνηση: αφαίρεσε ένα edge (και όλα τα edges που αποσυνδέονται από το ground). Ποιος κερδίζει;

Simple Case - Bamboo Stalks:

Αν έχουμε \(k\) ξεχωριστά "stalks" (paths) με μήκη \(a_1, a_2, \ldots, a_k\):

Κάθε stalk είναι ισοδύναμο με Nim pile!
\[ g = a_1 \oplus a_2 \oplus \cdots \oplus a_k \]

Winning strategy: Όπως στο Nim!

🎯 6. Competition Strategy

🏆 Master Strategy για Grundy/Nim Problems

ΒΗΜΑ 1: Αναγνώριση
• Ένα παιχνίδι ή πολλά;
• Impartial (same rules για όλους);
• Finite (τελειώνει);

ΒΗΜΑ 2: Single Game Grundy
• Υπολόγισε \(g(n)\) για μικρά \(n\)
• Βρες pattern
• Συχνά: \(g(n) = n \bmod k\)

ΒΗΜΑ 3: Multiple Games
• XOR τα Grundy numbers!
• \(g_{total} = g_1 \oplus g_2 \oplus \cdots \oplus g_k\)

ΒΗΜΑ 4: Winning Move
• Αν \(g = 0\): Losing (οποιαδήποτε κίνηση οδηγεί σε \(g \neq 0\))
• Αν \(g \neq 0\): Winning - βρες κίνηση που κάνει \(g = 0\)!

ΒΗΜΑ 5: Verify
• Check με examples
• Simulate game

📋 Quick Reference Table

Game Type	Grundy Formula	Notes
Single Nim Pile (n)	\(g(n) = n\)	Direct
Bachet \(M=\{1,\ldots,k\}\)	\(g(n) = n \bmod (k+1)\)	Periodic
Multi-Pile Nim	\(g = a_1 \oplus a_2 \oplus \cdots\)	XOR sum
Game Sum	\(g(G_1+G_2) = g(G_1) \oplus g(G_2)\)	XOR
Misère Nim	Special rules	All ≤1: count piles

🚨 Common Mistakes

⚠️ Τα 6 Πιο Συχνά Λάθη

1. XOR vs Addition
❌ \(g = a_1 + a_2 + a_3\)
✅ \(g = a_1 \oplus a_2 \oplus a_3\)

2. Mex confusion
❌ mex(\{0,1,3\}) = 3
✅ mex(\{0,1,3\}) = 2 (μικρότερος που λείπει!)

3. Ξεχνάμε τη βάση
❌ Δεν υπολογίζουμε \(g(0)\)
✅ Πάντα ξεκινάμε από terminal positions!

4. Misère confusion
❌ Misère = κανονικό Nim
✅ Misère έχει ειδικούς κανόνες για piles ≤ 1

5. Binary XOR errors
❌ \(3 \oplus 5 = 8\)
✅ \(3 \oplus 5 = 6\) (011 ⊕ 101 = 110)

6. Δεν επαληθεύουμε
❌ "Νομίζω \(g(n) = n \bmod 3\)" χωρίς check
✅ ΠΑΝΤΑ verify με calculation!

🏆 CHALLENGE PROBLEM - Part 2

🎯 THE CHALLENGE

Πρόβλημα: Nim με 4 piles: (7, 11, 13, 15). Ποιος κερδίζει και ποια είναι η βέλτιστη πρώτη κίνηση;

🎁 Hints σε 4 Επίπεδα:

🥉 Hint 1: Υπολόγισε \(g = 7 \oplus 11 \oplus 13 \oplus 15\) σε binary.

🥈 Hint 2: Αν \(g \neq 0\), είναι winning position.

🥇 Hint 3: Για να βρεις ποιο pile να αλλάξεις, δοκίμασε \(a_i' = g \oplus a_i\) για κάθε \(i\).

💎 Hint 4: Check αν \(a_i' < a_i\) (νόμιμη κίνηση!).

📮 Πλήρης Λύση:

Step 1: Calculate XOR

 7 = 0111₂
11 = 1011₂
13 = 1101₂
15 = 1111₂
 ⊕ = 0100₂ = 4
            

Άρα \(g = 4 \neq 0\) → Winning position!

Step 2: Find Winning Move

Δοκιμάζουμε κάθε pile:
• Pile 7: \(a_1' = 4 \oplus 7 = 0100 \oplus 0111 = 0011 = 3\) ✓ (3 < 7, νόμιμο!)
• Pile 11: \(a_2' = 4 \oplus 11 = 0100 \oplus 1011 = 1111 = 15\) ✗ (15 > 11)
• Pile 13: \(a_3' = 4 \oplus 13 = 0100 \oplus 1101 = 1001 = 9\) ✓ (9 < 13, νόμιμο!)
• Pile 15: \(a_4' = 4 \oplus 15 = 0100 \oplus 1111 = 1011 = 11\) ✓ (11 < 15, νόμιμο!)

Winning Moves (3 options):
1. Pile 7 → 3: New state (3, 11, 13, 15)
2. Pile 13 → 9: New state (7, 11, 9, 15)
3. Pile 15 → 11: New state (7, 11, 13, 11)

Verification (option 1):
\(3 \oplus 11 \oplus 13 \oplus 15 = 0011 \oplus 1011 \oplus 1101 \oplus 1111 = 0000 = 0\) ✓

📊 Σύνοψη & Επόμενα Βήματα

🎓 Τι Μάθαμε σε αυτό το Part:

✅ Grundy Numbers: \(g(P) = \text{mex}\{g(P')\}\)
✅ Mex Function: Minimum excludant
✅ L vs W: \(g = 0 \Leftrightarrow L\), \(g > 0 \Leftrightarrow W\)
✅ Sprague-Grundy Theorem: Every impartial game ≈ Nim pile
✅ Game Sums: \(g(G_1 + G_2) = g(G_1) \oplus g(G_2)\)
✅ XOR Strategy: Nim sum for multi-pile
✅ 7 Advanced Examples: Από Bachet Grundy → Green Hackenbush
✅ Competition Framework: 5-step systematic approach

🎊 Συγχαρητήρια!

Ολοκληρώσατε το Part 2 του Game Theory Marathon!

Τι κατακτήσατε:
✅ Grundy numbers mastery
✅ Mex function understanding
✅ Sprague-Grundy theorem
✅ XOR strategy for Nim
✅ Game sums technique
✅ Misère & Staircase variations
✅ 7 αναλυτικά examples
✅ Competition-ready skills

📅 Επόμενο Part:
Part 3: Advanced Strategies & Partizan Games
Symmetry, Pairing, Complex Games! 💙

Μείνετε συντονισμένοι...
Το ταξίδι προς την κορυφή συνεχίζεται! 🚀🎮