Chapter 185
The Case Of The Smudged Secret Message
Riddler Express
Five improvisers perform a scene. They each pick a character at the start; halfway through the scene they each switch to a different character, so the five characters are unchanged but no actor plays the same one in both halves. Two of the five characters are villains and three are heroes. Assuming each valid reallocation is equally likely, what is the probability that at least one actor plays a villain in both halves?
The Riddler, FiveThirtyEight, June 8, 2018(original post)
Solution
The reallocation is a derangement of the five actors: a permutation of with for every . The number of derangements of five elements is Label the two villain-actors . Define the events A villain is played twice in a row exactly when at least one of occurs.
Counting by symmetry. Fix the villain . Over all derangements, maps to one of the four other actors, and by symmetry each of those four images is equally likely. So exactly derangements have . By the same argument .
Intersection. fixes the swap . The remaining three hero-actors must derange themselves, giving . So .
Inclusion-exclusion. Therefore
The symmetry step is worth pausing on. Among derangements, the image ranges over the four allowed values . Relabelling those four targets is a symmetry of the derangement-count (a derangement remains a derangement under any permutation of the codomain that fixes ’s image set), so the four counts are equal at each.
The computation
Encode the problem: enumerate all derangements of (let index the villains and the heroes), and count those that send or .
from itertools import permutations
from fractions import Fraction
actors = (0, 1, 2, 3, 4)
villains = {0, 1}
derangements = [p for p in permutations(actors) if all(p[i] != i for i in actors)]
print("D_5 =", len(derangements))
# A villain repeat: some actor i in {0,1} satisfies p[i] in {0, 1}, i.e. a villain plays villain.
# But p[i] != i (derangement), so the only way villain i plays villain in 2nd half is
# p[i] = the other villain.
repeats = sum(1 for p in derangements if p[0] == 1 or p[1] == 0)
print("repeat villains =", repeats, "/", len(derangements))
print("probability =", Fraction(repeats, len(derangements)))The script prints and , confirming the boxed answer.
Riddler Classic
Two equations have been intercepted. In each, different letters stand for different digits. In the first, every digit appears, and four letters have been smudged (shown as dashes). In the second, exactly one of the letters is wrong. Recover both equations.
The first equation, with the smudges relabelled , is The second equation is with exactly one letter in error.
The Riddler, FiveThirtyEight, June 8, 2018(original post)
Solution (Equation 1)
The sum of two -digit numbers is at most and is the -digit , so the leading digit is .
The units column is (modulo and a possible carry). The hundreds-thousands column on the left has , which must equal (modulo ) and contribute the leading carry into position (the column of the answer). Working through these constraints by digit-by-digit elimination, or, faster, by brute search over the digit assignments respecting the letter constraints, the unique solution is Substituting, All ten digits – appear, as required.
Solution (Equation 2)
By the same leading-digit argument, . The units column and the hundred-millions column (mod ) give the small system , for some carry . With , , works ( and ). Continuing the column-by-column logic (or by computer search over the assignments with one letter freed up to vary), the unique solution is Substituting into the intended (correct) equation, position of the first number reads (digit ), not :
The computation
Encode each puzzle as a constraint-satisfaction problem and brute-force the digit assignments. For equation , the constraint is that the letter substitution gives an arithmetically valid sum, with all ten digits appearing and the dashes distinct from the named letters. For equation , search over which of the ten letters is wrong, freeing that letter from the all-different constraint at that position and checking the sum.
Enumerate digit assignments to the letters for equation ; check the arithmetic.
For equation , enumerate digit assignments to ; for each, also try replacing each of the ten letter-positions in the first number with a different letter and check the arithmetic.
from itertools import permutations
def letters_to_int(s, m):
n = 0
for ch in s:
n = 10 * n + m[ch]
return n
# Equation 1: brute search over 10! / (10 - len(letters))! assignments
LET1 = "EXMRKABCDH"
A1, B1, S1 = "EXMREEK", "EHKREKK", "AKBHCXDE"
sols1 = []
for perm in permutations(range(10)):
m = dict(zip(LET1, perm))
if m['E'] == 0 or m['A'] == 0:
continue
if (letters_to_int(A1, m) + letters_to_int(B1, m)
== letters_to_int(S1, m)):
sols1.append(m)
break # unique
m1 = sols1[0]
print("equation 1:", letters_to_int(A1, m1), "+",
letters_to_int(B1, m1), "=", letters_to_int(S1, m1))
# Equation 2: confirm the corrected letter pattern with K -> Y gives a valid sum
LET2 = "YTBEDMHRP" # 9 letters after K -> Y collapse
A2_FIXED, B2, S2 = "YTBBEDMYD", "YHDBTYYDD", "EDYTERTPTY"
sols2 = []
for perm in permutations(range(10), len(LET2)):
m = dict(zip(LET2, perm))
if any(m[ch] == 0 for ch in (A2_FIXED[0], B2[0], S2[0])):
continue
if (letters_to_int(A2_FIXED, m) + letters_to_int(B2, m)
== letters_to_int(S2, m)):
sols2.append(m)
break # unique
m2 = sols2[0]
print("equation 2:", letters_to_int(A2_FIXED, m2), "+",
letters_to_int(B2, m2), "=", letters_to_int(S2, m2),
"(corrected; original K at position 8 should be Y)")For equation the search returns the unique solution . For equation the corrected letter pattern admits the unique assignment ; the original in position of the first number should have been .