Wanna Play?

By /

I offer to play a card game with you using a normal deck of 52 cards.  the rules of the game are that we will turn over two cards at a time.  if the cards are both black, they go into my pile.  if they are both red, they go into your pile.  if there is one red and one black, they go into the discard pile.

We repeat the two card flipping until we’ve gone through all 52 cards.  whoever has more cards in their pile at the end wins.  i win if there is a tie.  if you win, i pay you a dollar.  how much would you pay to play this game?

Solution 

I wouldn’t give you a penny for that game. Here’s why.

Let’s say all the color pairs are matched. That means 13 red pairs, 13 black pairs, you win.

Now let’s say there is 12 red pairs in the deck, we pick them all from the top of the deck. With the 28 remaining card, there will always be exactly 12 black pairs and two mixed pairs. Why? Two red cards in the stack, they can’t be in a pair, otherwise you would get a total of 13 pairs, and I would too since all the black cards would be together. So the two red cards are matched with one black card each, leaving 24 black cards together, I get the same number of pairs as you do and you win.

Same math with 11 red pairs. That means four red cards in mixed pairs, hence 22 black cards left together, or 11 pairs.

No matter how mixed up the cards are, it’s a tie, and you win. Hence, I wouldn’t give you a penny.

2026 Update: Game Theory — Combinatorial Games and Nim Strategy

Interview game puzzles (Nim, Wythoff’s, coin removal games) test whether you can find the mathematical invariant that determines winning strategy. For most combinatorial games, the key is Sprague-Grundy theory.

def nim_winner(piles: list) -> str:
    """
    Nim game: players alternate taking any number from one pile.
    Last player to take wins. Loser is who can't move.
    P-position (previous player wins, current loses): XOR of all piles = 0.
    N-position (next player wins): XOR != 0.
    """
    xor_sum = 0
    for pile in piles:
        xor_sum ^= pile
    return "Second player wins" if xor_sum == 0 else "First player wins"

def nim_optimal_move(piles: list) -> tuple:
    """Find optimal Nim move: which pile to reduce and by how much."""
    xor_sum = 0
    for p in piles:
        xor_sum ^= p

    if xor_sum == 0:
        return None  # Losing position, no winning move

    # Find a pile where pile[i] XOR xor_sum < pile[i]
    for i, pile in enumerate(piles):
        new_pile = pile ^ xor_sum
        if new_pile  str:
    """
    General single-pile game: take 1 or 2 from pile.
    Losing positions: multiples of 3 (0, 3, 6, 9, ...)
    Pattern: Grundy value = n % 3
    """
    return "Lose" if game_state % 3 == 0 else "Win"

# Test Nim
print(nim_winner([1, 2, 3]))         # Second player wins (XOR=0)
print(nim_winner([1, 3, 5, 7]))      # Second player wins (XOR=0)
print(nim_winner([1, 2, 4]))         # First player wins
print(nim_optimal_move([1, 2, 4]))   # (2, 3) — remove 3 from pile 2 (leaves 1)

# Common interview variants:
print("nSimple pile game (take 1 or 2):")
for n in range(10):
    print(f"  n={n}: {play_game(n)}")

# Wythoff's game: take from one pile OR equal from both
def wythoff_losing(n: int) -> list:
    """Wythoff losing positions (cold positions) up to n."""
    phi = (1 + 5**0.5) / 2
    positions = []
    k = 0
    while True:
        a = int(k * phi)
        b = int(k * phi * phi)
        if a > n:
            break
        positions.append((a, b))
        k += 1
    return positions

print("nWythoff cold positions:", wythoff_losing(15))

Interview insight: Game theory problems test invariant thinking. For Nim: XOR of pile sizes. For single-pile take-k games: losing positions are multiples of (k+1). For “staircase” games and Chomp: Sprague-Grundy numbers via dynamic programming. The skill is recognizing which invariant to compute — the same mathematical structure underlies many different game presentations.

Scroll to Top