Skip to main content

Getting Stuck: The Nim Variant That Played Me

 

Getting Stuck: The Nim Variant That Played Me

I like to believe that I’ve learned to recognize traps in mathematical problems. Especially in games. If something looks too neat, too regular, too easy, I get suspicious. But this time, the trap wasn’t in the setup — it was in my own head.

The Game That Looked Harmless

Here’s the problem:

  • One pile of n stones.

  • Two players alternate.

  • On your turn, you may remove 1, 3, or 4 stones.

  • Whoever takes the last stone wins.

That’s it. Barebones, no hidden twists. Just arithmetic.

I’ve seen countless problems like this. My instinct: there’s always a neat modular pattern in the losing positions. Like in ordinary Nim (remove 1 or 2 stones), where the losing positions are just multiples of 3. I was convinced I’d crack this in fifteen minutes.

Spoiler: it took me an entire evening, and I ended up learning more about myself than the stones.

My First Pass: Confidence at Full Blast

I began the way every combinatorial game analyst does: mark small cases.

  • 0 → losing (no move).

  • 1 → winning (take 1).

  • 2 → losing (forced to leave 1, which is winning).

  • 3 → winning (take all 3).

  • 4 → winning (take all 4).

  • 5 → winning (take 3 → leave 2, which is losing).

So far, clean. I rubbed my hands: maybe all evens are losing?

The Betrayal of 6

Next case:

6.

  • Take 1 → leave 5 (winning). Bad.

  • Take 3 → leave 3 (winning). Bad.

  • Take 4 → leave 2 (losing). Bingo! That’s good.

So 6 is winning. My “all evens are losing” hypothesis immediately collapsed.

I tried to rescue it: maybe it’s “every even number except 6”? That felt like stretching duct tape over a broken bridge.

The Catastrophe of 7

Then came 7.

  • Take 1 → leave 6 (winning).

  • Take 3 → leave 4 (winning).

  • Take 4 → leave 3 (winning).

Every single move loses. Which means 7 is a losing position.

This was irritating. I thought: maybe the losing numbers are every other odd one? 2, 7… maybe 12, 17… I scribbled down guesses.

Descent Into Pattern-Chasing

At this point, I was chasing phantom structures.

  • Maybe the losing positions were all n mod 5 = 2? Nope: 2 works, 7 doesn’t.

  • Maybe they were spaced by 5, then 2, then 4, in some cycle? Didn’t match.

  • Maybe it was mod 7? Again, inconsistent.

I started writing little tables, convinced I was “just one more case” away from spotting it.

By n = 15, I had a mess: losing at 0, 2, 7, 9, 13, 15. My notebook looked like the diary of a conspiracy theorist — circles, arrows, false modular “rules,” everything except string and pushpins.

False Hope From Symmetry

I tried a different tack. Maybe the game has a “mirror strategy”: whatever my opponent does, I reply with something that pairs with it. That kind of symmetry trick works in some take-away games.

I attempted to define “pairs” of moves: if they take 1, I take 4; if they take 3, I take 2. Except — wait, I can’t even take 2. The move set doesn’t allow it.

I abandoned that idea quickly, but not before wasting half an hour drawing mirrored trees of moves.

Giving Up on Intuition

By this point, my head was fried. I had oscillated between “I see the pattern!” and “the universe is chaos” at least five times. The truth is, there’s only so long you can manually track moves before your brain starts hallucinating regularities.

So I finally caved and wrote a Python script.

def classify(n):
    dp = [False] * (n + 1)  # False = L, True = W
    for i in range(1, n + 1):
        dp[i] = any(i - m >= 0 and not dp[i - m] for m in (1, 3, 4))
    return dp

dp = classify(25)
for i, state in enumerate(dp):
    print(i, "W" if state else "L")

And the output:

0 L
1 W
2 L
3 W
4 W
5 W
6 W
7 L
8 W
9 L
10 W
11 W
12 W
13 L
14 W
15 L
16 W
17 W
18 W
19 L
20 W
21 L
22 W
23 W
24 W
25 L

I just stared at it. The losing positions weren’t multiples of anything. They weren’t following a neat congruence. They were… scattered.

The Humbling

I had assumed the game would bow to my pattern-hunting ego. Instead, it laughed at me. The losing positions were at 0, 2, 7, 9, 13, 15, 19, 21, 25… — not regular, but not random either. They were dictated by deeper structure.

The “structure” is called the Sprague–Grundy theorem, which says every impartial game can be reduced to Nim via Grundy numbers. If I had remembered that from the start, I could have approached the game systematically. Instead, I flailed in the dark.

When I finally computed Grundy numbers for each pile size, everything clicked: losing positions are exactly those with Grundy number 0. Of course. But by then, I was too exhausted to celebrate.

Reflection

This episode of Getting Stuck wasn’t just about a pile of stones. It was about how easily we can fool ourselves with patterns that aren’t there.

I went in expecting elegance. I got chaos.
I wanted a five-minute solution. I got a three-hour ego check.
I thought I was playing the game. Turns out, the game was playing me.

And that’s exactly why I love doing this.


Labels:

Comments

Post a Comment

Popular posts from this blog

Sharp Extremal Bounds for Angular Occupancy (Behind the Curtains)

you can find the full paper here First Attempts, and the Limits of Energy When I first began thinking about angular occupancy, I wasn’t looking for a brand-new problem. I was chasing a theme that has long fascinated me in discrete geometry: how do we measure the geometric richness of a finite set of points? This fascination is not unique to me. Erdős, way back in 1946, posed the distinct distances problem : given n points in the plane, how many distinct distances can they determine? That question alone gave birth to entire decades of work in combinatorial geometry. Later, Fishburn and Füredi asked about distinct angles , while Pach and Sharir studied repeated angles . Each time, the same underlying itch was being scratched: when you place points in the plane, what kinds of diversity can they generate? Why angles, why bins? It was natural to think of angles — after all, distances and directions had already been well studied. But if you go straight for “distinct angles,” you run in...
Post a Comment
Read more

The Art of Goodbye

  The Art of Goodbye: How Relationships End and Why It Matters The friendship had been slowly dissolving for months. What used to be weekly coffee dates became monthly check-ins, then sporadic text messages, then silence. No fight precipitated the ending, no dramatic confrontation or betrayal. It simply... faded. One day you realized you hadn't spoken to someone who was once central to your life, and you weren't sure when the relationship had officially ended or even if it had. This ambiguous loss left you with a peculiar grief – mourning someone still alive, still accessible, but no longer present in your world. This experience is incredibly common yet rarely discussed. While we have cultural scripts for how relationships begin – meet-cutes, first dates, friendship origin stories – we have few models for how they end. We talk extensively about building connections but rarely about gracefully releasing them. This gap in our social understanding leaves many people unprepared ...
1 comment
Read more

Getting Stuck: When Dijkstra Meets Negative Edges

  Getting Stuck: When Dijkstra Meets Negative Edges One of the joys (and pains) of computer science is when you take a tool you know, confidently apply it, and then watch everything break down in surprising ways. This happened to me recently when I decided to revisit shortest path algorithms — specifically, Dijkstra’s algorithm — only to get stuck in a swamp of negative edges. Setting the Scene The problem was classic: Given a directed, weighted graph and a source vertex, find the shortest path to all other vertices. This is the kind of problem that every CS student learns early, usually with Dijkstra’s algorithm. I already knew Dijkstra like an old friend: Keep a priority queue of distances. Always expand the node with the current smallest distance. Relax its edges. Simple, elegant, efficient ( O((V + E) log V) with a binary heap). So when I started coding a graph utility for my project — a tool to analyze transportation networks — I confidently plugged in D...
Post a Comment
Read more