In Space, No One Can Hear Your 3D Printer Die

Riddler Express

I multiplied together some of the integers from $1$ to $99$. I got a big number in return:

What is the missing digit?

The Riddler, FiveThirtyEight, January 11, 2019(original post)

Solution

The missing digit is recovered by casting out nines, provided the product is divisible by $9$. Show that first, then read off the digit.

Why the product must be divisible by $9$. The product is taken over some subset of $\{1, 2, \ldots, 99\}$. The published number has $114$ digits, of which the rightmost $12$ are trailing zeros. The number is therefore enormous: any subset whose product reaches this size must include nearly every available factor, in particular more than one multiple of $3$. To see this concretely, the largest product over any subset of $\{1, \ldots, 99\}$ that includes exactly one multiple of $3$ is bounded above by $$96 \,\cdot\, \prod_{\substack{1 \le k \le 99 \\ 3 \,\nmid\, k}} k,$$ where $96$ is the largest single multiple of $3$ in the range and the second factor is the product of the $66$ integers in $\{1, \ldots, 99\}$ coprime to $3$. A direct calculation (or even a crude logarithmic estimate) shows this bound is many orders of magnitude below the puzzle’s $114$-digit number. The puzzle’s product therefore contains at least two distinct multiples of $3$, hence two factors of $3$, hence a factor of $9$.

Casting out nines. A number is divisible by $9$ if and only if the sum of its digits is divisible by $9$. Let $d$ be the missing digit. Summing the known digits of the number with $d$ in the masked slot gives $$S_{\text{known}} \;+\; d \;\equiv\; 0 \pmod{9}.$$ A direct sum of the $107$ known digits (the missing slot replaced by $0$ for bookkeeping) yields $S_{\text{known}} = 471$, and $471 = 9 \cdot 52 + 3$, so $S_{\text{known}} \equiv 3 \pmod{9}$. Hence $$d \;\equiv\; -3 \;\equiv\; 6 \pmod{9}.$$ The only single digit in $\{0, 1, \ldots, 9\}$ congruent to $6 \pmod 9$ is $6$ itself ($d = 6$; $d = 15$ would not be a digit).

$$\boxed{\text{Missing digit} \;=\; 6.}$$

The computation

Encode the problem directly: take the number as given, with the missing digit marked, and find the digit that makes the digit sum a multiple of $9$. No reliance on the derivation: the script just sweeps $d \in \{0, \ldots, 9\}$ and reports the unique value that works.

1. Write out the digit string with the missing slot.

2. For each candidate $d \in \{0, \ldots, 9\}$, replace the slot with $d$ and test divisibility by $9$ via the digit sum.

3. Report the unique $d$ that passes.

groups = (
    "530,131,801,762,787,739,802,889,792,754,109,70?,139,358,"
    "547,710,066,257,652,050,346,294,484,433,323,974,747,960,"
    "297,803,292,989,236,183,040,000,000,000"
).split(",")
number_with_slot = "".join(groups)
candidates = [d for d in range(10)
              if sum(int(c) for c in number_with_slot.replace("?", str(d)))
                 % 9 == 0]
print("Digits making the number divisible by 9:", candidates)

The script prints the single-element list $[6]$, matching the boxed answer.

Riddler Classic

Congratulations, astronaut! You have been selected for the first manned mission to Mars and will spend five Earth-years on the surface, that is $1{,}825$ Earth-days (no leap years). Exactly one vital piece of equipment will break each day. You and the crew bring three $3$D printers to print replacement parts. Each printer is from a different country, so parts from one printer are incompatible with the others (no scavenging). When a printer itself breaks, one of the other printers must print its replacement part. Parts print effectively instantly, but any given printer can print at most one piece per day. In addition to the daily vital-equipment break, the three printers have independent daily break probabilities $0.10$, $0.075$, and $0.05$. If you cannot print a replacement for any piece of vital equipment, you die. What is the probability you make it home alive?

The Riddler, FiveThirtyEight, January 11, 2019(original post)

Solution

Reduce the daily survival condition first; then the $1{,}825$-day question becomes a single Bernoulli product.

The daily survival condition. Let $A$, $B$, $C$ be the three printers with daily break probabilities $p_{A} = 0.10$, $p_{B} = 0.075$, $p_{C} = 0.05$, and let $k \in \{0, 1, 2, 3\}$ be the number of them that break on a given day. The astronaut also needs to print one replacement for the vital equipment that day. Print demands and capacities, considered for the day’s schedule:

• $k = 0$: no printer is broken; any printer can print the vital part. Survives.

• $k = 1$: two working printers remain; use one of them to print the broken printer’s part (it is then operational), and the other (or the just-repaired one) to print the vital part. Survives.

• $k = 2$: one working printer remains. Suppose $A$ and $B$ both break and $C$ is alive. Order the print jobs within the day: $C$ prints $A$’s part (so $A$ is now working), then $A$ prints $B$’s part (so $B$ is now working), then $B$ prints the vital-equipment part. Each printer does at most one job, so the one-piece-per-printer-per-day budget is met. Survives.

• $k = 3$: all three printers break on the same day. No printer is alive to print anyone’s first repair. The vital part cannot be made. Dies.

So the day is survived if and only if at least one printer is working at the start of the day, which is the same as saying not all three broke. (Printers that broke are restored by day’s end whenever a chain of repairs is possible, which the case analysis just showed it is whenever $k \le 2$. The next morning therefore starts with all three printers operational again.) The daily failure probability is $$q \;=\; p_{A} \, p_{B} \, p_{C} \;=\; 0.10 \cdot 0.075 \cdot 0.05 \;=\; 3.75 \cdot 10^{-4}.$$

Surviving $1{,}825$ days. The day-to-day failure events are independent because, after any successful day, all three printers are operational, and the next day’s breakages are drawn from the same independent triple. Hence $$\begin{aligned} \Pr(\text{survive all } 1{,}825 \text{ days}) &\;=\; (1 - q)^{1825} \;=\; (0.999625)^{1825} \\ &\;\approx\; 0.5043. \end{aligned}$$

$$\boxed{\Pr(\text{survive}) \;=\; (1 - 0.10 \cdot 0.075 \cdot 0.05)^{1825} \;\approx\; 50.43\%.}$$

The computation

Simulate the calendar directly: each day, draw three independent break indicators; if all three break, the mission ends. Otherwise the day is survived and the printers reset. Compare the empirical survival rate over many trials to the closed form.

1. For each trial, walk through $1{,}825$ days.

2. On each day, draw three independent Bernoulli break flags with probabilities $0.10$, $0.075$, $0.05$.

3. If all three break, the trial is a death; otherwise continue.

4. Report the empirical survival probability and compare to $(1 - q)^{1825}$.

import random

def simulate(trials=200_000, days=1825, seed=0):
    rng = random.Random(seed)
    ps = (0.10, 0.075, 0.05)
    survived = 0
    for _ in range(trials):
        alive = True
        for _day in range(days):
            if all(rng.random() < p for p in ps):
                alive = False
                break
        if alive:
            survived += 1
    return survived / trials

q = 0.10 * 0.075 * 0.05
closed = (1 - q) ** 1825
print(f"closed form = {closed:.4f}")
print(f"simulated   = {simulate():.4f}")

The script prints $\text{closed form} = 0.5043$ and $\text{simulated} \approx 0.5043$ (within Monte-Carlo noise of $\pm 0.002$ at $200{,}000$ trials), matching the boxed answer.