143 — Grundy Number Intro

Game theory trilogy-র শেষ ও সবচেয়ে শক্তিশালী ধাপ। 142-এ দেখলে Nim-এর রহস্য XOR; এবার Sprague-Grundy বলবে — যেকোনো impartial game আসলে ছদ্মবেশী Nim। প্রতিটা position-কে একটা সংখ্যা (Grundy number) দিয়ে, একাধিক game-কে XOR দিয়ে জোড়া যায়। মনে রাখো, এই level CP-leaning, interview-এর জন্য optional (repo-র plan অনুযায়ী)।

Source

• Original source: Sprague-Grundy theorem (impartial games)
• Platform: CP-Algorithms — https://cp-algorithms.com/game_theory/sprague-grundy-nim.html
• Topic: Math-based programming fundamentals → Level 11: Hard Mixed CP Patterns
• Difficulty: Hard
• Pattern: mex + XOR (Grundy value, sum of games)
• Basic idea inherited from: 142 (Nim Game)

1. Problem in simple words

142-এ Nim-এর রহস্য XOR-এ ধরা পড়েছিল। কিন্তু সব game তো Nim নয় — যেমন "এক স্তূপে n পাথর, প্রতি চালে 1 বা 2টা নেওয়া যায়"। এমন game-এ কে জেতে?

Sprague-Grundy theorem বলে: যেকোনো impartial game-এর প্রতিটা position-কে একটা সংখ্যা দেওয়া যায় — তার Grundy number — আর সেই সংখ্যাটা ঠিক Nim pile-এর মতো আচরণ করে। দুটো বড় কাজ:

• একটা position-এর Grundy 0 ⟺ সেটা L (হারা-অবস্থা)।
• একাধিক স্বাধীন game একসাথে চললে, মোট game জেতা যায় কি না — সব game-এর Grundy-র XOR দেখলেই বলা যায়।

এটা CP-leaning level। Interview-পথে থাকলে এড়িয়ে মূল DS topic-এ যেতে পারো; পরে ফিরে এলে sum-of-games-এর জাদু আরও স্পষ্ট লাগবে।

2. What is the math idea?

মূল ধারণা mex (minimum excludant) আর XOR of games:

g(position) = mex { g(next) : next = এই position থেকে এক চালে যাওয়া যায় }
mex(S) = S-এ নেই এমন ক্ষুদ্রতম অঋণাত্মক integer
         mex({0,1,3}) = 2,   mex({}) = 0,   mex({1,2}) = 0

g = 0 মানে position L; g > 0 মানে W। আর Sprague-Grundy-র মূল উপপাদ্য: একাধিক game যোগ করলে মোট Grundy = প্রতিটার Grundy-র XOR — এজন্যই Grundy-কে বলে "Nim-মুদ্রা": প্রতিটা game-কে সমতুল্য একটা Nim pile (যার আকার = তার Grundy) বানিয়ে XOR করো।

3. Which basic idea does this inherit from?

সরাসরি Nim (problem 142) থেকে। Nim-এ pile-এর আকারই ছিল তার "মান", আর XOR বলত কে জেতে। Grundy এটাকে সাধারণীকরণ করে: যেকোনো game-এর প্রতিটা position-এর একটা "Nim-সমতুল্য আকার" = তার Grundy number। তারপর Nim-এর সেই একই XOR rule খাটে।

আর 141-এর W/L labeling-ও আছে — Grundy আসলে W/L-এর উন্নত রূপ: W/L শুধু দুই মান (জিতি/হারি), Grundy দেয় পুরো সংখ্যা যা sum-of-games-এ XOR করা যায়। তাই trilogy: 141 (W/L) → 142 (Nim XOR) → 143 (Grundy = দুটোর মিলন ও সাধারণীকরণ)।

4. Real-life analogy

ভাবো তোমার সামনে কয়েকটা আলাদা আলাদা mini-game একসাথে চলছে (একটা দাবা-ধাঁচ, একটা পাথর-স্তূপ, একটা ধাঁধা) — প্রতি চালে তুমি যেকোনো একটা game-এ একটা চাল দাও। সব game-এ চাল ফুরোলে যে আটকায় সে হারে।

এত মিশ্র খেলা কীভাবে বিশ্লেষণ করবে? Grundy বলে: প্রতিটা mini-game-কে একটা "ওজন" (Grundy number) দাও — যেন প্রতিটা একটা Nim pile। তারপর সব ওজন XOR করো; ≠ 0 হলে তুমি জেতো। মানে যত আলাদা খেলাই হোক, প্রতিটাকে একটা সংখ্যায় অনুবাদ করে সব Nim-এ মিশিয়ে দেওয়া যায় — এটাই Grundy-র জাদু।

5. Visual explanation

mex দিয়ে Grundy ভরা (n পাথর, নেওয়া যায় 1 বা 2):

g[n] = mex { g[n-1], g[n-2] }   (যতগুলো বৈধ)

n :   0   1   2   3   4   5   6
g :   0   1   2   0   1   2   0     <- period 3!

কীভাবে:
  g[0] = mex {}          = 0   (চাল নেই)
  g[1] = mex {g[0]}      = mex {0}    = 1
  g[2] = mex {g[1],g[0]} = mex {1,0}  = 2
  g[3] = mex {g[2],g[1]} = mex {2,1}  = 0   <- L!
  g[4] = mex {g[3],g[2]} = mex {0,2}  = 1

g = 0 ঘরগুলো (n = 0, 3, 6, ...) = L position

sum of games (দুই স্তূপ a, b):
  মোট Grundy = g[a] XOR g[b]
  ≠ 0  ->  প্রথম player W

লক্ষ করো — mex মানে "set-এ যে সবচেয়ে ছোট অঋণাত্মক integer নেই"; min নয়, max নয়।

6. Example input and output

এক স্তূপ, নেওয়া যায় {1, 2}:
n      Grundy   W/L
-----------------------
0      0        L
3      0        L
1      1        W
2      2        W

sum of two heaps (Grundy XOR):
heaps        g_a ^ g_b           প্রথম player
-----------------------------------------------------
[3, 3]       g[3]^g[3]=0^0=0     হারে (L)
[1, 2]       g[1]^g[2]=1^2=3≠0   জেতে (W)
[3, 5]       g[3]^g[5]=0^2=2≠0   জেতে (W)

mex উদাহরণ:
mex({0,1,2}) = 3,  mex({0,2}) = 1,  mex({}) = 0

মূল edge case: mex({}) = 0 — কোনো চাল না থাকলে Grundy 0 (হারা-অবস্থা); আর দুটো সমান Grundy XOR করলে 0 (L)।

7. Brute force thinking

XOR rule না জেনেও sum-of-games-এর W/L সরাসরি recursion-এ বের করা যায় — state = সব heap একসাথে:

from functools import lru_cache


def two_heap_brute_win(a, b, moves=(1, 2)):
    @lru_cache(maxsize=None)
    def win(x, y):
        nexts = []
        for t in moves:
            if x >= t:
                nexts.append((x - t, y))
            if y >= t:
                nexts.append((x, y - t))
        for ns in nexts:
            if not win(*ns):                # opponent L-এ
                return True
        return False
    return win(a, b)

এটা definition-এর সরল রূপ — ঠিক উত্তর দেয়, আর Grundy-XOR rule যাচাইয়ের মাপকাঠি। কিন্তু heap বাড়লে state বিস্ফোরক।

8. Why brute force may be slow

Sum-of-games-এ state হলো সব game-এর মিলিত অবস্থা — সংখ্যাটা গুণফলে বাড়ে:

2 heap, প্রতিটা ≤ 1000  ->  ~10^6 state (memo লাগবে)
5 heap, প্রতিটা ≤ 1000  ->  ~10^15 state — অসম্ভব

Grundy: প্রতিটা game আলাদা O(M) তে precompute,
        তারপর XOR -> মোট O(সব game-এর আকার) — গুণফল ভেঙে যোগফল!

মূল শিক্ষা: combined game-এর exponential state-কে Grundy ভেঙে দেয় — প্রতিটা game আলাদা বিশ্লেষণ করে শুধু XOR; গুণফল-জটিলতা যোগফল-জটিলতায় নামে।

9. Better thinking

মূল insight (Sprague-Grundy): প্রতিটা game আলাদাভাবে তার Grundy number বের করো (mex দিয়ে, পেছন থেকে), তারপর সব game-এর Grundy XOR করো:

combined Grundy = g(game₁) XOR g(game₂) XOR ...
≠ 0  ->  প্রথম player W;   = 0  ->  L

একটা game-এর Grundy বের করা মানে 141-এর মতোই backward fill — শুধু W/L-এর জায়গায় mex। আর sum-of-games-এ Nim-এর XOR rule সরাসরি খাটে কারণ প্রতিটা Grundy number একটা Nim pile-এর সমতুল্য।

10. Thinking tweak

এক লাইনের "আহা": যেকোনো impartial game = ছদ্মবেশী Nim — প্রতিটা position-কে তার mex-দিয়ে-পাওয়া Grundy সংখ্যায় অনুবাদ করো, তারপর একাধিক game XOR করে Nim-এর মতো খেলো।

ফাঁদ: mex ভুল করা — mex মানে set-এ নেই এমন ক্ষুদ্রতম অঋণাত্মক integer; min নয়, max নয় (concept-notes mistake #5)। mex({1,2,3}) = 0 (0 নেই!), mex({0,1,2}) = 3। আর Grundy = 0 ⟺ L — এই একটা সমীকরণ মনে রাখলেই W/L আর Grundy এক সুতোয় বাঁধা।

11. Step-by-step dry run

n পাথর, নেওয়া যায় {1, 2} — Grundy table ভরি, তারপর sum-of-games চেক:

1. g[0] = mex {} = 0 — চাল নেই, L।
2. g[1] = mex {g[0]} = mex {0} = 1 — W।
3. g[2] = mex {g[1], g[0]} = mex {1, 0} = 2 — W।
4. g[3] = mex {g[2], g[1]} = mex {2, 1} = 0 — L! (0, 1, 2 কেউ নেই বাদ দিয়ে... আসলে 0 set-এ নেই, তাই mex = 0)।
5. g[4] = mex {g[3], g[2]} = mex {0, 2} = 1 — W। Pattern: g[n] = n % 3।
6. sum-of-games [1, 2]: combined Grundy = g[1] ^ g[2] = 1 ^ 2 = 3 ≠ 0 → প্রথম player W। (brute force-ও True বলে — মিলে গেল।)

12. Python solution

def mex(s):
    """s-এ নেই এমন ক্ষুদ্রতম অঋণাত্মক integer।"""
    m = 0
    while m in s:
        m += 1
    return m


def grundy_subtraction(N, moves=(1, 2)):
    """এক স্তূপ: 0..N প্রতিটার Grundy number (নেওয়া যায় moves থেকে)।"""
    g = [0] * (N + 1)
    for n in range(1, N + 1):
        g[n] = mex({g[n - m] for m in moves if n >= m})
    return g


def sum_of_games_wins(heaps, moves=(1, 2)):
    """একাধিক স্বাধীন স্তূপ — combined Grundy = XOR; ≠ 0 হলে W।"""
    g = grundy_subtraction(max(heaps) if heaps else 0, moves)
    x = 0
    for h in heaps:
        x ^= g[h]
    return x != 0


from functools import lru_cache


def two_heap_brute_win(a, b, moves=(1, 2)):
    """দুই স্তূপ W/L সরাসরি — Grundy-XOR যাচাইয়ের জন্য।"""
    @lru_cache(maxsize=None)
    def win(x, y):
        for t in moves:
            if x >= t and not win(x - t, y):
                return True
            if y >= t and not win(x, y - t):
                return True
        return False
    return win(a, b)


# --- ছোট test গুলো (সব pass করা উচিত) ---
g = grundy_subtraction(9)
for n in range(10):
    assert g[n] == n % 3, n                 # {1,2}-game: Grundy period 3
assert mex({0, 1, 2}) == 3
assert mex({0, 2}) == 1
assert mex(set()) == 0
assert mex({1, 2, 3}) == 0                  # 0 নেই -> mex 0

# Grundy = 0 ⟺ L: একক স্তূপে brute W/L-এর সাথে মিল
for n in range(10):
    single_W = two_heap_brute_win(n, 0)     # দ্বিতীয় heap খালি = একক game
    assert single_W == (g[n] != 0), n       # g লম্বা 0..9

# sum-of-games XOR rule brute force-এর সাথে মিল
import random
gg = grundy_subtraction(10)
for _ in range(300):
    a, b = random.randint(0, 8), random.randint(0, 8)
    pred = (gg[a] ^ gg[b]) != 0
    assert pred == two_heap_brute_win(a, b), (a, b)

print(g)                                     # [0,1,2,0,1,2,0,1,2,0]
print(sum_of_games_wins([1, 2]))             # True (1^2=3≠0)
print(sum_of_games_wins([3, 3]))             # False (0^0=0)
print("সব test pass!")

13. Line-by-line explanation

def mex(s):
    m = 0
    while m in s:
        m += 1
    return m

0 থেকে গুনি, set-এ যতক্ষণ আছে এগোই; প্রথম যেটা নেই সেটাই mex। mex({0,1,3}) → 0 আছে, 1 আছে, 2 নেই → 2।

        g[n] = mex({g[n - m] for m in moves if n >= m})

position n থেকে এক চালে যেসব position-এ যাওয়া যায় (n-1, n-2), তাদের Grundy-র set বানিয়ে mex নিই — এটাই Grundy-র সংজ্ঞা।

    x = 0
    for h in heaps:
        x ^= g[h]
    return x != 0

Sum-of-games: প্রতিটা heap-এর Grundy XOR করি (প্রতিটা যেন একটা Nim pile)। ≠ 0 হলে প্রথম player W — Nim-এর সেই একই rule।

বাকি two_heap_brute_win definition-এর সরল recursion (যাচাইয়ের জন্য), আর assert গুলো চারভাবে মিলিয়ে দেখে: (১) Grundy period, (২) mex-এর মান, (৩) Grundy=0 ⟺ L, (৪) sum-of-games XOR rule vs brute। সব মিললে সব test pass!।

14. Output walkthrough

চালালে ছাপবে:

[0, 1, 2, 0, 1, 2, 0, 1, 2, 0]
True
False
সব test pass!

প্রথম লাইন {1,2}-game-এর Grundy (period 3, 0/3/6/9-এ 0 = L)। দ্বিতীয় [1,2] → 1^2=3≠0 → True (W)। তৃতীয় [3,3] → 0^0=0 → False (L)। তার আগের সব assert চুপচাপ pass — Grundy theory আর brute force একমত। সবশেষে সব test pass!।

15. Time complexity

এক game-এর Grundy precompute: O(N · |moves|) — প্রতিটা position-এ moves দেখে mex (mex নিজে ছোট set-এ প্রায় constant)। Sum-of-games-এ মোট: প্রতিটা game precompute + heap-সংখ্যা বার XOR — গুণফল-state-এর exponential থেকে নেমে প্রতিটা game-এর আকারের যোগফল।

16. Space complexity

O(N) — এক game-এর Grundy array। Sum-of-games-এ সব game-এর সবচেয়ে বড়টার আকার (একই moves হলে একটাই array শেয়ার করা যায়)। brute version memo-র জন্য O(state) নেয়, কিন্তু আসল solution তা নয়।

17. Common mistakes

1. mex ভুল করা — mex = set-এ নেই এমন ক্ষুদ্রতম অঋণাত্মক integer; min/max নয় (concept-notes mistake #5)। mex({1,2}) = 0।
2. Grundy = 0-কে W ভাবা — g = 0 মানে L (হারা); উল্টে ভাবলে সব W/L উল্টে যায়।
3. Sum-of-games-এ XOR ভুলে যোগ করা — combined Grundy = XOR, sum নয় (Nim-এর মতোই)।
4. next-states ভুল গোনা — Grundy-তে শুধু এক চালে যাওয়া position-এর Grundy নিতে হয়, তাদের next নয়।
5. এক game-এর Grundy আরেকটায় ভুলে ব্যবহার — moves/নিয়ম আলাদা হলে Grundy table আলাদা; শেয়ার করার আগে নিশ্চিত হও নিয়ম এক।

18. Harder problems that inherit this idea

• CP-Algorithms — Sprague-Grundy & Nim (https://cp-algorithms.com/game_theory/sprague-grundy-nim.html) — তত্ত্ব, প্রমাণ, আরও প্রয়োগ।
• LeetCode — Stone Game IV (https://leetcode.com/problems/stone-game-iv/) — W/L DP, Grundy-ঘরানার চিন্তা।
• Codeforces — game theory + grundy tag (https://codeforces.com/problemset?tags=games) — sum-of-games-এর নানা রূপ।

19. Pattern learned

Grundy number (mex + XOR) — প্রতিটা impartial game position-এর Grundy = mex of next-states' Grundy; g = 0 ⟺ L। একাধিক স্বাধীন game-এর combined Grundy = তাদের XOR — যেকোনো game-কে Nim-এ অনুবাদ করার সর্বজনীন মুদ্রা।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "যেকোনো impartial game = ছদ্মবেশী Nim। Grundy(position) = mex of next-states; g=0 মানে হারা। একাধিক game একসাথে চললে সব Grundy XOR করো — Nim-এর মতো ≠ 0 হলে জিতি। mex = set-এ নেই এমন ক্ষুদ্রতম অঋণাত্মক সংখ্যা।"

পরের ধাপ → 144 — Expected Value Problems (game theory শেষ, এবার probability-র জাদু)। শিকড় → 142 — Nim Game।

ফিরে দেখা: এই level-এর map → ../README.md · চিন্তার ছাঁচ → ../concept-notes.md · template → ../../../templates/math-problem-note-template.md।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি করা হয়নি — বরং "CP-style pattern" / "common interview pattern" বলা হয়েছে।