Can You Flip The Magic Coin?

Riddler Express

I claim my coin is magical: on most days it is fair, but once a year, on the summer solstice, it always lands the opposite side from the previous flip. You think there is a $1\%$ chance it really is magical and a $99\%$ chance it is an ordinary fair coin. You ask me to demonstrate by flipping it. How many successive alternating flips must I produce before you are $99\%$ sure the coin is magical (or at least rigged to alternate)?

The Riddler, FiveThirtyEight, June 19, 2020(original post)

Solution

This is Bayes’ rule. Let $M$ be the event that the coin is magical, with prior $\Pr(M) = 0.01$. A magical coin alternates with certainty, so $\Pr(A_n \mid M) = 1$, where $A_n$ is the event of $n$ flips all alternating. A fair coin alternates only if it happens to land in one of the two perfectly alternating patterns (starting heads or starting tails) out of $2^n$, so $\Pr(A_n \mid M^c) = 2/2^n = 2^{1-n}$.

The posterior is $$\Pr(M \mid A_n) = \frac{1\cdot 0.01}{1\cdot 0.01 + 2^{1-n}\cdot 0.99}.$$ Requiring this to reach $0.99$ rearranges to $2^{n-1} \ge \dfrac{0.99^2}{0.01^2} = 9801$, so $n - 1 \ge \log_2 9801 \approx 13.3$, giving $n - 1 \ge 14$ and $$n = \boxed{15}.$$ At fifteen alternating flips the posterior is about $0.994$, just over the line; fourteen would leave you only $0.988$ sure.

The computation

Evaluate the posterior for growing $n$ and report the first $n$ that reaches $99\%$ confidence.

from fractions import Fraction as F
prior = F(1, 100)
n = 1
while True:
    post = (1 * prior) / (1 * prior + F(2, 2**n) * (1 - prior))
    if post >= F(99, 100):
        print(n, float(post)); break          # 15, ~0.994
    n += 1

Riddler Classic

King Auric has a set of solid gold spheres, one of each diameter $1, 2, 3, \ldots$ centimetres. He divides them into three groups of equal weight, one for each of his three children, and finds his collection is the smallest that allows such a division. How many spheres does he have? Extra credit: how many would he need to split the gold evenly among two, four, five or six children?

The Riddler, FiveThirtyEight, June 19, 2020(original post)

Solution

A solid sphere’s weight is proportional to the cube of its diameter, so the spheres weigh $1^3, 2^3, \ldots, N^3$ and the task is to split $\{1^3, 2^3, \ldots, N^3\}$ into three groups of equal sum.

Two simple facts trim the search. First, the total weight is $1^3 + \cdots + N^3 = \bigl(\tfrac{N(N+1)}{2}\bigr)^2$, and for three equal groups this must be divisible by $3$, which forces $N \equiv 0$ or $2 \pmod 3$. Second, the heaviest sphere, weighing $N^3$, must fit inside its own group of weight (total)$/3$, so $$N^3 \le \frac{1}{3}\Bigl(\tfrac{N(N+1)}{2}\Bigr)^2 \;\Longrightarrow\; N^2 - 10N + 1 \ge 0 \;\Longrightarrow\; N \ge 10.$$ The candidates are therefore $11, 12, 14, 15, 17, 18, 20, 21, 23, \ldots$, and a direct partition search finds that none works until $$N = \boxed{23},$$ where the $23$ spheres split into three groups each weighing $76176/3 = 25392$. For other family sizes the same search gives the minimum collection:

The computation

Encode the partition directly: for each $N$ in turn, test whether $\{1^3, \ldots, N^3\}$ splits into $k$ groups of equal sum (assign each cube to a bin, pruning bins that would overflow the target). Report the first $N$ that works.

def splits(vals, k):
    total = sum(vals)
    if total % k: return False
    target = total // k
    vals = sorted(vals, reverse=True)
    if vals[0] > target: return False
    bins = [0] * k
    def place(i):
        if i == len(vals): return True
        seen = set()
        for b in range(k):
            if bins[b] in seen or bins[b] + vals[i] > target: continue
            seen.add(bins[b]); bins[b] += vals[i]
            if place(i + 1): return True
            bins[b] -= vals[i]
        return False
    return place(0)
def min_N(k):
    N = 1
    while not splits([n ** 3 for n in range(1, N + 1)], k): N += 1
    return N
for k in (2, 3, 4, 5, 6):
    print(k, min_N(k))        # 2->12, 3->23, 4->24, 5->24, 6->35