Can You Make 24?

Riddler Express

Using each of the numbers $2$, $3$, $3$ and $4$ exactly once, together with parentheses and the operations $+$, $-$, $\times$, $\div$ and exponentiation (but no concatenation), make an expression equal to $24$. Extra credit: find another way.

The Riddler, FiveThirtyEight, July 10, 2020(original post)

Solution

With the friendlier sets one juggles sums and products, but $2, 3, 3, 4$ resist: no combination using only $+, -, \times, \div$ reaches $24$. The way through is exponentiation. Dividing $4$ by $2$ gives a clean base of $2$, and cubing it lands on $8$: $$\left(\tfrac{4}{2}\right)^{3}\times 3 = 2^{3}\times 3 = 8\times 3 = \boxed{24}.$$ A second route hides a fractional exponent: $4^{3/2} = (\sqrt4)^3 = 8$, so $$4^{\,3/2}\times 3 = 8 \times 3 = 24,$$ which uses the $2$ as the denominator of the exponent. Both belong to the same family of solutions: get a $2$ and a $3$ to build $2^3 = 8$, then multiply by the remaining $3$.

The computation

Encode the game: build every value reachable from the four numbers under the five operations, once without exponentiation and once with it. The target $24$ appears only when exponentiation is allowed.

from itertools import permutations
def reach(vals, powers):
    if len(vals) == 1: return {vals[0]}
    out = set(); n = len(vals)
    for i, j in permutations(range(n), 2):
        if i > j: continue
        rest = [vals[k] for k in range(n) if k != i and k != j]
        for a in reach([vals[i]], powers):
            for b in reach([vals[j]], powers):
                cands = [a + b, a - b, b - a, a * b]
                if b: cands.append(a / b)
                if a: cands.append(b / a)
                if powers:
                    for base, ex in ((a, b), (b, a)):
                        if base > 0 or (float(ex).is_integer() and base != 0):
                            try:
                                if abs(base) < 1e6 and -40 < ex < 40:
                                    cands.append(base ** ex)
                            except (ValueError, OverflowError, ZeroDivisionError):
                                pass
                for c in cands:
                    out |= reach(rest + [c], powers) if rest else {c}
    return out
nums = [2.0, 3.0, 3.0, 4.0]
print("24 without exponent:", any(abs(v - 24) < 1e-9 for v in reach(nums, False)))
print("24 with exponent:   ", any(abs(v - 24) < 1e-9 for v in reach(nums, True)))
print((4 / 2) ** 3 * 3, 4 ** 1.5 * 3)
# 24 without exponent: False
# 24 with exponent:    True
# 24.0 24.0

Riddler Classic

A toy has five rings of different sizes and a tapered column; each ring has a correct snug position (largest at the bottom). A placed ring slides to its correct position if it can reach it, otherwise it rests on the current top ring. How many unique stacks (using at least one ring) can be made? Extra credit: with $N$ rings?

The Riddler, FiveThirtyEight, July 10, 2020(original post)

Solution

Number the rings $1$ (smallest, snug at the top) to $5$ (largest, snug at the bottom). A dropped ring behaves simply: if it is smaller than the current top ring it slips down to its own snug slot, which lies above everything placed; if it is larger, it cannot pass and comes to rest in the slot just above the top ring, provided a slot is free there. Placing the smallest ring puts a ring at the very apex, after which nothing more fits.

Counting all reachable stacks splits into the $31$ “all-snug” stacks (each ring independently in or out, $2^5 - 1$) plus the stacks that carry one or more rings resting out of place atop a smaller one. Enumerating every placement order and collecting the distinct outcomes gives $$\boxed{65}$$ unique stacks for five rings. For the extra credit the same enumeration gives the sequence $$1,\ 3,\ 8,\ 22,\ 65,\ 209,\ \ldots \quad (N = 1, 2, 3, 4, 5, 6, \ldots),$$ so four rings give $22$ and six give $209$.

The computation

Encode the physical rule (smaller ring drops to its snug slot above; larger ring rests one slot above the top ring if room exists) and explore every placement order, collecting the set of distinct final stacks.

def count_stacks(N):
    seen, rings = set(), range(1, N + 1)
    def place(occ):                       # occ: dict slot -> ring; slot 1 = top
        if occ: seen.add(frozenset(occ.items()))
        top = min(occ) if occ else N + 1
        used = set(occ.values())
        for r in rings:
            if r in used: continue
            if not occ:
                place({r: r})             # snug slot equals ring size
            elif r < top:                 # smaller: slips to its own snug slot
                place({**occ, r: r})
            elif top > 1:                 # larger: rests one slot above the top ring
                place({**occ, top - 1: r})
    place({})
    return len(seen)
print([count_stacks(N) for N in range(1, 7)])   # [1, 3, 8, 22, 65, 209]