by Sami Casanova
Art by Jesse Gelles
Problem: New Year’s Town/​Holi Town

This game is a variant of Nim, and for each game, the first player can guarantee themselves a win—the goal of the puzzle is to find all possible winning moves for the starting player.

In the images below, the winning first moves for each game are colored in (using a different color for each game).

In the final image, all winning first moves for all games are shown superimposed together.

If you read the letters assigned to each bubble from left to right, top to bottom, they spell ANSWER RELIEF PITCHER.

(A relief pitcher of champagne must certainly be what Blanche is getting to remedy the champagne situation!)

Blanche is the name of the wife of mathematical logician Raymond Smullyan, if you were wondering about the names.

The following is a sample program written in Python to prove this logic puzzle’s solution.

# Python 3 code to solve Bubbly, MIT Mystery Hunt 2019, Setec Astronomy

# Game states are represented as balanced strings of parentheses, with nesting to show nested bubbles.
# A letter label follows each open paren in the initial game states, but during runtime these labels are
# separated from the parens, so the representation of a game state is purely parens.

# Return a list of balanced paren strings by splitting the argument into balanced substrings
def parensplit(s):
    l = []
    start = 0
    level = 0
    for i, c in enumerate(s):
        if c == '(':
            level += 1
            level -= 1
        if level == 0:
            l.append(s[start:i + 1])
            start = i + 1
    return l

# Return canonical form of game state s (subgames in sorted order)
def canonicalize(s):
    if len(s) == 0:
        return ''
    l = parensplit(s)
    if len(l) == 1:
        return '(' + canonicalize(s[1:-1]) + ')'
    return ''.join(sorted(l))

# Table of games with known nimbers (transposition table, sorta)
nimtab = dict()

# Return resulting game state for game state s if you pop the bubble whose open paren is in position p
def popbubble(s, p):
    ss = ''
    level = 0
    minlevel = 0
    for i in range(p - 1, -1, -1):
        if s[i] == '(':
            level -= 1
            if level < minlevel:
                minlevel = level
                ss = '(' + ss
            level += 1
            ss = ')' + ss
    level = 0
    minlevel = 0
    for i in range(p + 1, len(s)):
        if s[i] == ')':
            level -= 1
            if level < minlevel:
                minlevel = level
                ss += ')'
            level += 1
            ss += '('
    return ss

#Compute nimber for game state s
def nimber(s):
    if s == '':
        return 0
    s = canonicalize(s)
    if s in nimtab:
        return nimtab[s]
    l = parensplit(s)
    if len(l) > 1:
        # more than one independent subgame: return nim-sum (xor) of subgame nimbers
        n = 0
        for ss in l:
            n ^= nimber(ss)
        # find and make all moves and use mex rule to find nimber of this game
        numset = set()
        for i, c in enumerate(s):
            if c == '(':
                numset.add(nimber(popbubble(s, i)))
        n = 0
        while n in numset:
            n += 1
    nimtab[s] = n
    return n

# Return string of all winning move labels for game state s (with labels)
def winningmoves(s):
    parens = ''
    labels = ''
    # split out labels from paren sequence so game state is only balanced parens
    for c in s:
        if c == '(' or c == ')':
            parens += c
            labels += c
    pcount = 0
    winners = ''
    for i, c in enumerate(parens):
        if c == '(':
            # look at all moves
            if nimber(popbubble(parens, i)) == 0:
                # game is won if nimber is zero after making move
                winners += labels[pcount]
            pcount += 1
    return winners

# Nested paren notation for games.
games = [

for g in games:
    print('{}: winning moves: {}'.format(g, winningmoves(g)))

Running the above program produces the following output:

(C(H(S(V(E(L)))(U(I))(T)))(R(A))(G)))(N): winning moves: EI
(I(T(C(A(L))))(F(N(U))(S)))(H(V(P(R))))(E(G)): winning moves: CSH
(F(H(E(C(I(T(S))(G))(V))(A(Y(M))(N)))(R))(L(U))(P)): winning moves: ER
(I(Y(U(T(H)))(N(F))))(M(R(C(L))(K)))(A(S(P(E)))(V))(B(G)): winning moves: TFRA
(F(L(E(D(T(U)))(A(R))(B))(S(I(V(H))(C))(Y))(G(M)))(N(K(P))(Z))): winning moves: EIP
(A(B(E(Z(M(K))(V))(Y))(L(M))(H))(T(F(G)))(U(X))(D))(C(R(P))(I))(S(W)): winning moves: EL
(T(S(D(K(X))))(Y(J(M))(A)))(R(G(U(L(Z(C))))))(F(Q(B(V(I)))))(P(H(W)))(N(E)): winning moves: RWN