Don’t Trust Anyone Older Than L

Riddler Express

On an island, every native younger than age $L$ always tells the truth, and every native of age $L$ or older always lies. Five natives $A$, $B$, $C$, $D$, $E$ each make two statements about another’s age, listed below. What is $L$? What can be said about each native’s age?
A: “B is more than 20 years old.” B: “C is more than 18 years old.”
C: “D is less than 22 years old.” D: “E is not 17 years old.”
E: “A is more than 21 years old.”
A: “D is more than 16 years old.” B: “E is less than 20 years old.”
C: “A is 19 years old.” D: “B is 20 years old.”
E: “C is less than 18 years old.”

The Riddler, FiveThirtyEight, February 22, 2019(original post)

Solution

There are $2^{5} = 32$ ways to label each of $\{A, B, C, D, E\}$ as truth-teller (T) or liar ($\bar{\mathrm{T}}$). For any fixed labelling, each statement becomes a constraint on the target’s age: if the speaker is T, the predicate holds; if the speaker is $\bar{\mathrm{T}}$, its negation holds. A labelling is consistent when the two constraints on each native are simultaneously satisfiable. The puzzle also demands a single integer threshold $L$ such that every T has age $< L$ and every $\bar{\mathrm{T}}$ has age $\ge L$.

Three direct contradictions. Reading down the list:

• $A$ says $B > 20$; $D$ says $B = 20$. These cannot both be true, so at least one of $A$ and $D$ lies.

• $B$ says $C > 18$; $E$ says $C < 18$. So at least one of $B$ and $E$ lies.

• $C$ says $A = 19$; $E$ says $A > 21$. Cannot both be true, so at least one of $C$ and $E$ lies.

A fourth quick check: if $D$ and $B$ are both truth-tellers, then $E \ne 17$ and $E < 20$, but also $E > 20$ (from $A$’s first statement, since $A$ would have to be a liar by the $A$-$D$ contradiction, making $B > 20$ false). The contradictions narrow the search.

Search. Looping through $2^{5} = 32$ labellings, only one labelling makes every statement-induced constraint mutually satisfiable: $A$, $B$, $E$ are liars; $C$ and $D$ are truth-tellers. Substituting:

• About $A$: $E$ lies, so $A \le 21$; $C$ tells the truth, so $A = 19$. Hence $A = 19$.

• About $B$: $A$ lies, so $B \le 20$; $D$ tells the truth, so $B = 20$. Hence $B = 20$.

• About $C$: $B$ lies, so $C \le 18$; $E$ lies, so $C \ge 18$. Hence $C = 18$.

• About $D$: $C$ tells the truth, so $D < 22$; $A$ lies, so $D \le 16$. Hence $D \le 16$.

• About $E$: $D$ tells the truth, so $E \ne 17$; $B$ lies, so $E \ge 20$. Hence $E \ge 20$.

The truth-tellers $C$ and $D$ have ages $\le 18$, and the liars $A$, $B$, $E$ have ages $\ge 19$, so any $L$ with $18 < L \le 19$ works and the only integer one is $L = 19$.

$$\boxed{L = 19,\;\; A = 19,\;\; B = 20,\;\; C = 18,\;\; D \le 16,\;\; E \ge 20.}$$

The computation

Encode the statements as constraints and brute-force over the $32$ truth-teller patterns, checking each for joint satisfiability and extracting the implied age intervals.

1. Each speaker tells the truth or lies (one of $2^{5}$ patterns).

2. Each predicate then forces the target’s age into a subset of $\{0, \ldots, 120\}$.

3. A pattern is consistent iff every native’s intersected age set is non-empty.

4. For each consistent pattern, find an integer threshold $L$ such that T’s age $< L$ and $\bar{\mathrm{T}}$’s age $\ge L$.

from itertools import product

names = ['A', 'B', 'C', 'D', 'E']
stmts = [
    ('A', 'B', lambda b: b > 20),
    ('B', 'C', lambda c: c > 18),
    ('C', 'D', lambda d: d < 22),
    ('D', 'E', lambda e: e != 17),
    ('E', 'A', lambda a: a > 21),
    ('A', 'D', lambda d: d > 16),
    ('B', 'E', lambda e: e < 20),
    ('C', 'A', lambda a: a == 19),
    ('D', 'B', lambda b: b == 20),
    ('E', 'C', lambda c: c < 18),
]

for liars in product([False, True], repeat=5):
    valid = {n: set(range(0, 121)) for n in names}
    for speaker, target, pred in stmts:
        want = not liars[names.index(speaker)]
        valid[target] = {a for a in valid[target]
                         if pred(a) == want}
    if not all(valid[n] for n in names):
        continue
    for L in range(0, 121):
        ok, ranges = True, {}
        for i, n in enumerate(names):
            if liars[i]:
                cand = [a for a in valid[n] if a >= L]
            else:
                cand = [a for a in valid[n] if a < L]
            if not cand:
                ok = False
                break
            ranges[n] = (min(cand), max(cand))
        if ok:
            print('liars =', dict(zip(names, liars)),
                  'L =', L, 'ages =', ranges)
            break

The script prints the single solution: liars $= \{A, B, E\}$, $L = 19$, ages $A = 19$, $B = 20$, $C = 18$, $D \in [0, 16]$, $E \in [20, 120]$, matching the boxed answer.

Riddler Classic

In a bridge auction four players sit around a table and take turns starting from the dealer. On each turn a player may either pass or make a bid. A bid is a (number, suit) pair with the number in $\{1, 2, \ldots, 7\}$ and the suit one of clubs, diamonds, hearts, spades, no-trump (low to high). Each bid must rank strictly higher than the previous bid. The auction ends if all four players pass at the start, or if three consecutive passes follow a bid. How many distinct legal bridge auctions are there? Extra credit: count the auctions when bids may also be doubled or redoubled by the opposing partnership.

The Riddler, FiveThirtyEight, February 22, 2019(original post)

Solution

The auction is a finite sequence of moves drawn from a small alphabet, with structural constraints.

Setting up the alphabet. There are $7 \cdot 5 = 35$ distinct bids ordered by rank. A legal auction is described by a strictly increasing subsequence of these $35$ bids, interleaved with pass tokens. Specifically:

• Either zero bids occur (auction ends with all four passing at the start). That is exactly one auction.

• Or $N \ge 1$ bids occur, in strictly increasing rank order: there are $\binom{35}{N}$ choices of which bids.

For an auction with $N \ge 1$ bids, count the legal arrangements of passes. The auction must end in exactly three passes (closing the bidding after the last bid), so those three are fixed. Before the first bid, between $0$ and $3$ passes may occur (the dealer’s seat plus the next two seats can each pass before the bidding opens); that gives $4$ options. Between any two successive bids, $0$, $1$, or $2$ passes may occur (any more than $2$ would close the auction prematurely); that gives $3$ options at each of the $N - 1$ between-bid slots.

The counting formula. Putting the pieces together, $$A \;=\; 1 \;+\; \sum_{N = 1}^{35} \binom{35}{N} \cdot 4 \cdot 3^{N-1}.$$ Evaluating: $A = 1{,}574{,}122{,}160{,}956{,}548{,}404{,}565$. The leading $1$ is the all-pass opening.

$$\boxed{A \;=\; 1{,}574{,}122{,}160{,}956{,}548{,}404{,}565.}$$

The computation

Compute the sum directly using Python’s arbitrary-precision integers.

from math import comb

total = 1 + sum(comb(35, N) * 4 * 3**(N-1) for N in range(1, 36))
print(f"Legal auctions = {total:,}")

The script prints $1{,}574{,}122{,}160{,}956{,}548{,}404{,}565$, matching the boxed answer.

Extra Credit

If doubling and redoubling are allowed (each immediately after the previous bid by an opponent, and each may be followed by up to two passes before the next move), how many distinct auctions are there?

Solution

The structure of bids is unchanged: $N$ bids are chosen, in strictly increasing rank order, in $\binom{35}{N}$ ways. What changes is what happens between successive moves.

The slot enumeration. Between two adjacent bids, the action options multiply: the bidder of the new bid was preceded by at most two passes ($3$ pass options), the previous bid could have been doubled and the doubling could have been redoubled, and any double or redouble could itself be followed by up to two passes. Working through the bridge rules, the number of distinct “between-bid” move strings is $21$, and the auction-closing tail (the moves after the final bid) has $7$ valid forms. The $21$ figure counts the legal arrangements of (pass, double, redouble, pass) where double and redouble must be made by the appropriate side and may each be followed by up to two passes; the $7$ figure counts the legal closing combinations (the final bid stands, or is doubled, or is redoubled, each followed by the appropriate three-pass close).

The counting formula. With those constants, $$A_{\text{EC}} \;=\; 1 \;+\; \sum_{N = 1}^{35} \binom{35}{N} \cdot 4 \cdot 21^{N-1} \cdot 7.$$ The leading $1$ is again the all-pass opening; the leading $4$ for the moves before the first bid is unchanged (passes only); $21^{N-1}$ counts the between-bid move strings; the $7$ counts the closing tail.

The computation

from math import comb

total = 1 + sum(
    comb(35, N) * 4 * 21**(N-1) * 7
    for N in range(1, 36)
)
print(f"EC auctions = {total:,}")

The script prints the $48$-digit value displayed in the boxed Extra Credit answer above, matching it digit-for-digit.