Counting Honest Politicians and Burning Ropes

The Riddler for February 17, 2017, in tribute to logician Raymond Smullyan. The Express is a one-line logic puzzle; the Classic is a timing puzzle whose count doubles with every rope.

Riddler Express

A legislature has $100$ politicians, each honest or crooked. Some are honest and some are crooked, and among any two chosen at random at least one is crooked. How many are honest?

The Riddler, FiveThirtyEight, February 17, 2017(original post)

Solution

“Any two contain at least one crook” is just a vivid way of saying no two of them are both honest, that is, you can never pick two honest politicians. So there is at most one honest politician. But we are also told some of the legislature is honest, so there is at least one. The two facts pin it exactly: $$\boxed{1 \text{ honest politician}}$$ (and $99$ crooked). The clause “at least one of any pair is crooked” forbids a second honest member, and the clause “some are honest” forbids zero.

The computation

Encode the condition literally: over all splits into $h$ honest and $100-h$ crooked, which $h$ satisfy both “at least one honest” and “every pair has a crook” (i.e. no pair of honest members exists, which fails as soon as $h \ge 2$)?

from math import comb
valid = [h for h in range(0, 101)
         if h >= 1 and comb(h, 2) == 0]      # comb(h,2)=0 means no two honest can be picked
print("possible honest counts:", valid)
# possible honest counts: [1]

Riddler Classic

You have four ropes and a lighter. Each rope takes exactly one hour to burn end to end but burns at a non-constant rate, and you may light either end of any rope whenever you choose. How many distinct lengths of time can you measure?

Extra credit: how many with $N$ ropes?

The Riddler, FiveThirtyEight, February 17, 2017(original post)

Solution

The one trick that unlocks everything: lighting both ends of a rope makes the two flames meet after exactly $30$ minutes of burning, whatever the uneven rate, because together they consume the whole hour’s worth of rope at double speed. More generally, if a rope has $t$ minutes of burn left (at single-end speed) and you light its second end, it finishes in $t/2$. Each time a rope burns out is a clock tick you can act on: light fresh ends to start new timers. So the measurable times are exactly the elapsed-time marks reachable by lighting ends, waiting for a burnout, lighting more, and so on.

Enumerating those marks, the number of distinct measurable lengths is $2, 5, 11, 23$ for $1, 2, 3, 4$ ropes, so with four ropes you can measure $$\boxed{23 \text{ different lengths}},$$ running from $30$ minutes up to $240$. The counts double-and-add: each new rope lets you both reach further out (its full hour, and combinations beyond) and bisect every interval you could already make, which gives the closed form $$\boxed{T(N) = 3\cdot 2^{\,N-1} - 1}.$$ For example $71.25$ minutes comes from a four-rope cascade: light both ends of rope 1 and one end each of ropes 2 and 3; at $30$ min (rope 1 done) light rope 2’s other end and one end of rope 4; at $45$ min (rope 2 done) light rope 3’s other end; at $52.5$ min (rope 3 done) light rope 4’s other end, which finishes $18.75$ min later, at $71.25$.

The computation

Encode the burning process exactly. A state is the multiset of ropes still burning, each with its remaining single-end time and how many ends are lit. From any state, light any set of available ends, advance to the next burnout (recording the elapsed time as measurable), and recurse. Collecting every reachable mark reproduces the counts and the lists.

from fractions import Fraction as F
from itertools import product
import sys; sys.setrecursionlimit(100000)

memo = {}
def reach(state):                            # state: sorted tuple of (remaining, ends_lit)
    if state in memo: return memo[state]
    if not state: return frozenset()
    out, burning = set(), any(e > 0 for _, e in state)
    for add in product(*[range(0, 2 - e + 1) for _, e in state]):   # ends to light now
        new = [(r, e + a) for (r, e), a in zip(state, add)]
        if not any(e > 0 for _, e in new): continue                 # nothing burning
        if sum(add) == 0 and not burning: continue
        dt = min(F(r, e) for r, e in new if e > 0)                  # time to next burnout
        after = tuple(sorted((r - e * dt, e) for r, e in new if e == 0 or r - e * dt > 0))
        out.add(dt)
        out |= {dt + d for d in reach(after)}
    res = frozenset(out); memo[state] = res; return res

for N in (1, 2, 3, 4):
    memo.clear()
    times = sorted(reach(tuple(sorted((F(60), 0) for _ in range(N)))))
    print(f"N={N}: {len(times)} lengths  (3*2^(N-1)-1 = {3*2**(N-1)-1})")
print("N=4:", [float(t) for t in sorted(reach(tuple(sorted((F(60),0) for _ in range(4)))))])
# N=1: 2 lengths  (3*2^(N-1)-1 = 2)
# N=2: 5 lengths  (3*2^(N-1)-1 = 5)
# N=3: 11 lengths  (3*2^(N-1)-1 = 11)
# N=4: 23 lengths  (3*2^(N-1)-1 = 23)
# N=4: [30.0, 45.0, 52.5, 56.25, 60.0, 67.5, 71.25, 75.0, 78.75, 82.5, 86.25, 90.0,
#       97.5, 105.0, 112.5, 120.0, 127.5, 135.0, 150.0, 165.0, 180.0, 210.0, 240.0]

The list shows $56.25$ minutes where FiveThirtyEight’s published list has a typographical “$56.5$”; the burning cascade gives $56.25$, which the doubling structure confirms.