142 — Nim Game¶

Game theory trilogy-র দ্বিতীয় ধাপ — 141-এর W/L-চিন্তার উপর দাঁড়িয়ে এবার একটা জাদুর সূত্র: সব pile-এর XOR। Nim হলো সেই game যার পুরো রহস্য একটা XOR-এ বন্দি। মনে রাখো, এই level CP-leaning, interview-এর জন্য optional (repo-র plan অনুযায়ী) — তবে XOR-এর এই সৌন্দর্য না দেখলে মিস।

Source¶

Original source: Classic Nim game; LeetCode Nim Game (single-pile take-1-to-3 variant)
Platform: LeetCode — https://leetcode.com/problems/nim-game/; CP-Algorithms — https://cp-algorithms.com/game_theory/sprague-grundy-nim.html
Topic: Math-based programming fundamentals → Level 11: Hard Mixed CP Patterns
Difficulty: Medium
Pattern: XOR theorem (Nim-value of piles)
Basic idea inherited from: 141 (W/L labeling), 060 (XOR)

1. Problem in simple words¶

কয়েকটা স্তূপ (pile) পাথর — যেমন [3, 4, 5]। দুই player পালা করে চাল দেয়। প্রতি চালে যে কেউ যেকোনো একটা pile বেছে তা থেকে যত খুশি (অন্তত 1টা) পাথর সরায়। যে আর চাল দিতে পারে না (সব pile খালি, তার পালা) সে হারে (normal play)।

দুজনেই নিখুঁত খেলে। জিজ্ঞেস: প্রথম player জিতবে কি?

আশ্চর্যের ব্যাপার — উত্তরটা একটাই সংখ্যা দেখলেই বলা যায়: সব pile-এর XOR। আর LeetCode-এর সরল রূপটা single-pile: n পাথর, প্রতি চালে 1/2/3টা — সেখানে উত্তর n % 4-এ ধরা (141-এর সেই pattern!)।

এটা CP-leaning level। Interview-পথে থাকলে এড়িয়ে মূল DS topic-এ যেতে পারো; পরে ফিরে এলে XOR theorem-এর eleganceটা উপভোগ করবে।

2. What is the math idea?¶

মূল ধারণা Nim XOR theorem:

সব pile-এর XOR ≠ 0  ⟺  যার চাল সে জেতে (W position)
সব pile-এর XOR = 0  ⟺  যার চাল সে হারে (L position)

কেন XOR, কেন যোগফল নয়? কারণ XOR প্রতিটা bit-কে আলাদাভাবে দেখে — কোনো bit-position-এ যদি জোড়সংখ্যক pile-এ সেই bit জ্বলে থাকে, তারা পরস্পরকে "বাতিল" করে। XOR = 0 মানে প্রতিটা bit-position-এ ভারসাম্য — আর এই ভারসাম্যই হারা-অবস্থার চিহ্ন। যোগফল এই bit-ভারসাম্য ধরতে পারে না, তাই কাজ করে না।

3. Which basic idea does this inherit from?¶

দুটো শিকড়: W/L labeling (problem 141) আর XOR (problem 060)। 141 থেকে এসেছে "প্রতিটা position W না L" — এই কাঠামোটাই। কিন্তু Nim-এ state হলো (pile₁, pile₂, ...) — এত state যে পুরো table ভরা অসম্ভব। তখনই XOR theorem উদ্ধার করে: পুরো backward induction-এর ফলাফলটা একটা সূত্রে নেমে আসে।

আর XOR-এর স্বভাব (060): a ^ a = 0, a ^ 0 = a, এবং bitwise স্বাধীনতা — এগুলোই theorem-এর প্রমাণের ইট। তাই Nim হলো 141-এর W/L আর 060-এর XOR-এর সুন্দর মিলন।

4. Real-life analogy¶

ভাবো দুটো আয়না-খেলা। তোমার সামনে কয়েকটা মোমবাতির সারি (pile), আর তোমার প্রতিপক্ষ এক "আয়নাধারী" — সে তোমার প্রতিটা চালের আয়না-জবাব দিতে চায়, যাতে শেষে সারিটা আবার "ভারসাম্যে" (XOR = 0) ফিরে আসে।

শুরুতে যদি ভারসাম্য থাকে (XOR = 0), তুমি যা-ই চাল দাও তা ভারসাম্য ভাঙবে, আর প্রতিপক্ষ সবসময় আবার ভারসাম্যে ফিরিয়ে আনতে পারবে — তুমি ফাঁদে, শেষে চাল-হীন তুমিই (L)।
শুরুতে ভারসাম্য না থাকলে (XOR ≠ 0), তুমিই এক চালে ভারসাম্য বানিয়ে আয়নাধারী হয়ে যাও — এবার প্রতিপক্ষ ফাঁদে (W)।

মূল কথা: যে ভারসাম্য (XOR = 0) বানাতে পারে, সে-ই জেতে।

5. Visual explanation¶

XOR কীভাবে bit-ভারসাম্য মাপে ([3, 4, 5]):

pile গুলো binary-তে সাজাও, প্রতিটা bit-column আলাদা গোনো:

        bit2  bit1  bit0
  3  =    0     1     1
  4  =    1     0     0
  5  =    1     0     1
  -----------------------
 XOR =    0     1     0     =  2   (≠ 0  ->  প্রথম player W)

column-এ 1-এর সংখ্যা জোড় হলে XOR-bit 0, বিজোড় হলে 1।
XOR = 2 ≠ 0  ->  ভারসাম্য নেই  ->  W

তুলনায় [1, 2, 3]:
  1 = 001,  2 = 010,  3 = 011
  XOR = 001 ^ 010 ^ 011 = 000 = 0  ->  ভারসাম্য  ->  L (প্রথম player ফাঁদে)

লক্ষ করো — যোগফল (3+4+5=12) কিছুই বলে না; শুধু column-by-column XOR-ই সত্য বলে।

6. Example input and output¶

piles          XOR              প্রথম player
-----------------------------------------------------
[3, 4, 5]      3^4^5 = 2 ≠ 0    জেতে (W)
[1, 2, 3]      1^2^3 = 0        হারে (L)
[0, 0, 0]      0                হারে (L) — চাল-ই নেই
[7]            7 ≠ 0            জেতে (W) — পুরোটা নিয়ে নাও
[5, 5]         5^5 = 0          হারে (L) — আয়না জোড়া

single-pile (LeetCode, take 1-3):
n = 4          n % 4 == 0       হারে (L)
n = 1, 2, 3    n % 4 != 0       জেতে (W)

দুটো edge case: সব pile 0 হলে XOR 0 → L (চাল নেই); আর দুটো সমান pile ([5,5]) XOR 0 → L (একটা আয়না-জোড়া)।

7. Brute force thinking¶

XOR theorem না জানলে, 141-এর মতো সরাসরি W/L recursion করা যায় — state এখন pile-গুলোর tuple:

from functools import lru_cache


def nim_brute(piles):
    piles = tuple(sorted(piles))
    @lru_cache(maxsize=None)
    def win(state):
        for i, p in enumerate(state):
            for take in range(1, p + 1):       # i-তম pile থেকে take সরাও
                ns = list(state)
                ns[i] -= take
                ns = tuple(sorted(ns))
                if not win(ns):                # opponent L-এ
                    return True
        return False                           # সব চাল W-তে -> L
    return win(piles)

এটা definition-এর হুবহু — ঠিক উত্তর দেয়, আর XOR theorem যাচাইয়ের মাপকাঠি হিসেবে দারুণ। কিন্তু state-সংখ্যা বিস্ফোরক।

8. Why brute force may be slow¶

State হলো প্রতিটা pile-এর মানের সব সম্ভাব্য combination। kটা pile, প্রতিটা সর্বোচ্চ M — মোট state প্রায় M^k:

3 pile, প্রতিটা ≤ 100  ->  ~100^3 = 10 লাখ state (memo লাগবেই)
pile বড় হলে (≤ 10^9)    ->  অসম্ভব — state গোনাই যায় না

XOR theorem -> O(k), পুরো recursion এক সূত্রে নেমে এল

মূল শিক্ষা: backward induction-এর পুরো গাছটা XOR theorem একটা O(k) হিসাবে গুটিয়ে দেয় — এটাই theorem-এর শক্তি।

9. Better thinking¶

মূল insight (theorem): শুধু সব pile-এর XOR বের করো; ≠ 0 হলে প্রথম player W, = 0 হলে L। ব্যস।

কেন? দুই দিক:

XOR = 0 হলে: যেকোনো চালে তুমি কোনো এক pile কমাও → সেই pile-এর bit বদলায় → XOR আর 0 থাকে না (ভারসাম্য ভাঙে)। প্রতিপক্ষ সবসময় আবার XOR = 0 করতে পারে। শেষ (সব 0, XOR = 0) আসে প্রতিপক্ষের চালের পরে — চাল-হীন তুমি (L)।
XOR ≠ 0 হলে: সবচেয়ে বড় জ্বলা bit-ওয়ালা pile-টা এমনভাবে কমাও যে নতুন XOR = 0 — এমন চাল সবসময় থাকে। তুমি ভারসাম্য বানিয়ে আয়নাধারী হলে (W)।

10. Thinking tweak¶

এক লাইনের "আহা": pile-এর যোগফল ভুলে যাও — সব pile-এর XOR-ই একমাত্র সত্য; XOR ≠ 0 মানে তুমি জেতার চাল বানাতে পারো।

ফাঁদ দুটো: (১) XOR-এর বদলে sum দেখা — sum কিছুই বলে না (concept-notes mistake #4); (২) misère variant (শেষ পাথর নিলে হার) আলাদা নিয়ম — গুলিয়ো না। আর LeetCode-এর single-pile take-1-to-3 রূপটা আসলে 141-এর সেই game — উত্তর n % 4-এ; এটাকে multi-pile XOR Nim-এর সাথে মিশিয়ো না (নিয়ম আলাদা)।

11. Step-by-step dry run¶

[1, 2, 3] (XOR = 0, তাই L) — দেখাই কেন প্রথম player হারে:

XOR হিসাব: 1 ^ 2 ^ 3 = 001 ^ 010 ^ 011 = 000 = 0 → প্রথম player L।
প্রথম player যা-ই করুক, ভারসাম্য ভাঙবে। ধরো সে pile 3 থেকে 2 নিল → [1, 2, 1], XOR = 001 ^ 010 ^ 001 = 010 = 2 ≠ 0।
আয়না-জবাব: দ্বিতীয় player XOR আবার 0 করে — pile 2 (মান 2) থেকে 2 নিয়ে [1, 0, 1], XOR = 001 ^ 000 ^ 001 = 0।
প্রথম player আবার ভাঙে → ধরো pile 0 থেকে 1 নিল → [0, 0, 1], XOR = 1।
দ্বিতীয় player শেষ pile-এর 1 নিয়ে [0, 0, 0] — সব খালি। এখন প্রথম player-এর পালা, চাল নেই → প্রথম player হারল (L)। ✓ theorem ঠিক।

12. Python solution¶

def nim_first_player_wins(piles):
    """multi-pile Nim: সব pile-এর XOR ≠ 0 হলে প্রথম player জেতে।"""
    x = 0
    for p in piles:
        x ^= p
    return x != 0


def leetcode_nim_can_win(n):
    """single-pile, প্রতি চালে 1/2/3: n % 4 != 0 হলে প্রথম player জেতে।"""
    return n % 4 != 0


from functools import lru_cache


def nim_brute(piles):
    """সরল W/L recursion — XOR theorem যাচাইয়ের জন্য।"""
    piles = tuple(sorted(piles))
    @lru_cache(maxsize=None)
    def win(state):
        for i, p in enumerate(state):
            for take in range(1, p + 1):
                ns = list(state)
                ns[i] -= take
                if not win(tuple(sorted(ns))):
                    return True
        return False
    return win(piles)


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert nim_first_player_wins([3, 4, 5]) is True       # 3^4^5 = 2 ≠ 0
assert nim_first_player_wins([1, 2, 3]) is False      # 1^2^3 = 0
assert nim_first_player_wins([0, 0, 0]) is False      # চাল নেই
assert nim_first_player_wins([7]) is True
assert nim_first_player_wins([5, 5]) is False         # আয়না জোড়া

# brute force-এর সাথে এলোমেলো ছোট case-এ মিল (theorem-এর প্রমাণ)
import random
for _ in range(400):
    k = random.randint(1, 3)
    piles = tuple(random.randint(0, 5) for _ in range(k))
    assert nim_first_player_wins(piles) == nim_brute(piles), piles

# single-pile LeetCode version
for n in range(20):
    assert leetcode_nim_can_win(n) == (n % 4 != 0), n

print(nim_first_player_wins([3, 4, 5]))   # True
print(nim_first_player_wins([1, 2, 3]))   # False
print(leetcode_nim_can_win(4))            # False
print("সব test pass!")

13. Line-by-line explanation¶

    x = 0
    for p in piles:
        x ^= p
    return x != 0

এটাই পুরো theorem। x শুরুতে 0; প্রতিটা pile XOR করে যোগ করি (x ^= p)। শেষে x ≠ 0 মানে ভারসাম্য নেই → প্রথম player জেতে। মাত্র O(k)।

def leetcode_nim_can_win(n):
    return n % 4 != 0

LeetCode-এর single-pile take-1-to-3 — এটা multi-pile XOR Nim নয়, বরং 141-এর সেই subtraction game; উত্তর n % 4-এ (4-এর গুণিতকে L)।

    @lru_cache(maxsize=None)
    def win(state):
        ...
        if not win(tuple(sorted(ns))):
            return True

brute version — প্রতিটা pile থেকে সম্ভাব্য সব take চেষ্টা করি; কোনোটা opponent-কে L-এ ফেললে আমি W। sorted করে lru_cache দিয়ে একই state বারবার গোনা এড়াই।

বাকি assert গুলো তিনভাবে যাচাই: (১) হাতে-গোনা ছোট case, (২) 400টা random pile-এ brute force-এর সাথে মিল, (৩) single-pile n % 4। সব মিললে সব test pass!।

14. Output walkthrough¶

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

True
False
False
সব test pass!

প্রথম লাইন [3,4,5] → XOR 2 ≠ 0 → True (W)। দ্বিতীয় [1,2,3] → XOR 0 → False (L)। তৃতীয় single-pile n=4 → False (4-এর গুণিতক, L)। তার আগের 400+টা assert চুপচাপ pass করেছে — theorem আর brute force সবসময় একমত। সবশেষে সব test pass!।

15. Time complexity¶

O(k) — kটা pile একবার XOR করা, ব্যস। pile-এর মান যত বড়ই হোক (10⁹), XOR constant-time প্রতি pile। single-pile version O(1) (শুধু n % 4)। brute force ছিল প্রায় O(M^k) — সূত্র সেটাকে O(k)-তে নামিয়েছে।

16. Space complexity¶

O(1) — শুধু একটা accumulator x। কোনো array বা recursion stack লাগে না (theorem version-এ)। brute version অবশ্য memo-র জন্য O(state) নেয়, কিন্তু আসল solution সেটা নয়।

17. Common mistakes¶

XOR-এর বদলে sum দেখা — যোগফল কিছুই বলে না; শুধু XOR সত্য (concept-notes mistake #4)।
Misère variant গুলিয়ে ফেলা — "শেষ পাথর নিলে হার" আলাদা নিয়ম (সেখানে সব pile ≤ 1-এর special case); এখানে normal play।
Single-pile আর multi-pile মিশিয়ে ফেলা — LeetCode take-1-to-3 single-pile = n % 4; multi-pile any-amount = XOR। নিয়ম ভিন্ন।
খালি pile (0) বাদ দেওয়া — 0-ও XOR-এ যায় (x ^ 0 = x), তাই আলাদা handle লাগে না; কিন্তু "pile আছে কিন্তু 0" আর "pile নেই" গুলিয়ো না।
জেতার চাল খুঁজতে গিয়ে ভুল bit — XOR ≠ 0-এ জেতার চাল = সর্বোচ্চ জ্বলা bit-ওয়ালা pile কমানো; অন্য pile কমালে সবসময় কাজ নাও করতে পারে।

18. Harder problems that inherit this idea¶

LeetCode — Nim Game (https://leetcode.com/problems/nim-game/) — single-pile take-1-to-3, n % 4।
CP-Algorithms — Sprague-Grundy & Nim (https://cp-algorithms.com/game_theory/sprague-grundy-nim.html) — Nim থেকে Grundy-তে সাধারণীকরণ।
LeetCode — Stone Game IV (https://leetcode.com/problems/stone-game-iv/) — game W/L DP, Nim-ঘরানার চিন্তা।

19. Pattern learned¶

Nim XOR theorem — multi-pile Nim-এ সব pile-এর XOR ≠ 0 ⟺ প্রথম player জেতে; কারণ XOR = 0 হলো bit-ভারসাম্য (হারা-অবস্থা)। sum নয়, XOR-ই সত্য — আর এটাই পরের Grundy number-এর ভিত্তি।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "Nim = pile-গুলোর XOR; ≠ 0 হলে প্রথম player জেতে (ভারসাম্য বানাতে পারে), = 0 হলে হারে। sum দেখো না, XOR দেখো। single-pile take-1-to-3 আলাদা: n % 4।"

পরের ধাপ → 143 — Grundy Number Intro (XOR theorem-এর সাধারণ রূপ: যেকোনো game-এর Nim-মান)। শিকড় → 141 — Game Theory Basics, 060 — XOR।

ফিরে দেখা: এই 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" বলা হয়েছে।