Chapter 1

The Honest Prince and the Rancher’s Children

The Riddler for March 17, 2017. The Express is a one-question logic puzzle with three princes (one always honest, one always lying, one mischievous); the Classic asks for the probability that four houses, one in each of four neighbouring ranches, form a convex quadrilateral.

Riddler Express

You are choosing whom to marry among a king’s three sons. The eldest prince always tells the truth, the youngest always lies, and the middle prince is mischievous, telling the truth sometimes and lying the rest of the time. The three look identical, so you cannot tell them apart by sight. The king lets you ask exactly one yes-or-no question to exactly one of the three. You will be happy marrying either the truthful eldest or the consistent-liar youngest; you want to avoid marrying the mischievous middle. What question guarantees you avoid the middle prince?

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

Solution

The crucial observation is that whoever you ask, you cannot marry that one. So the strategy must use the answer to pick between the other two, and it must produce the right pick regardless of whether the asked prince is honest, mischievous, or a liar. If the asked prince happens to be the middle, his answer is junk; but the other two are then exactly the eldest and the youngest, and any choice between them is acceptable. The work is to make the strategy correct when you ask one of the truthful brothers (eldest or youngest).

The princes’ roles are tied to age: eldest = honest, middle = mischievous, youngest = liar. Pick any prince and call him $A$ ; call the other two $B$ and $C$ in some fixed order. Ask $A$ : $\text{``Is $B$ older than $C$?''}$ Marry $C$ if $A$ says yes, marry $B$ if $A$ says no.

Why it works: split on who $A$ is.

$A$ is the eldest (honest). Then $\{B, C\}$ are the middle and the youngest. $A$ truthfully says whether $B > C$ in age. “Yes” means $B$ is older, so $B$ is the middle and $C$ is the youngest; the strategy picks $C$ , the youngest, who is the honest liar. “No” means $C$ is older (or equal, but they have distinct ages), so $C$ is the middle and $B$ is the youngest; the strategy picks $B$ , the youngest. Either way you marry the youngest, who is fine.
$A$ is the youngest (liar). Then $\{B, C\}$ are the eldest and the middle. The truth is that the eldest of these two is older; $A$ lies. If $B$ is in fact older (so $B$ is the eldest), $A$ says “no”; the strategy picks $B$ , the eldest. If $C$ is older, $A$ says “yes”; the strategy picks $C$ , the eldest. Either way you marry the eldest, who is fine.
$A$ is the middle. You will not marry $A$ in any case. The strategy picks one of $B$ or $C$ ; both are non-middle, so you are fine.

In every branch you avoid the middle. The boxed strategy:

The computation

Encode the problem exactly. Enumerate every assignment of identities to $(A, B, C)$ , simulate each truth-telling rule, and verify the strategy never returns the middle prince. The mischievous prince is allowed to answer either way; we check both.

from itertools import permutations, product

# Roles by age: eldest=2 (honest), middle=1 (mischievous), youngest=0 (liar).
def answer(role, b_older_than_c):                # answer to "is B older than C?"
    if role == 2: return [b_older_than_c]        # truth
    if role == 0: return [not b_older_than_c]    # lies
    return [True, False]                         # mischievous, either possible

bad = []
for A_role, B_role, C_role in permutations([0, 1, 2]):
    b_older = (B_role > C_role)                  # true if B is older than C
    for a in answer(A_role, b_older):
        chosen_role = C_role if a else B_role
        if chosen_role == 1:                     # marrying the mischievous = failure
            bad.append((A_role, B_role, C_role, a))
print("failure cases:", bad)
# failure cases: []

Riddler Classic

Four neighbouring square ranches are arranged in a $2 \times 2$ grid, sharing a common corner. Each ranch is a unit square, and each family builds its house at a point chosen uniformly at random inside its own ranch. The four houses are then joined in cyclic order, giving a quadrilateral. What is the probability that this quadrilateral is convex?

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

Solution

Place the ranches as the four unit squares meeting at the origin: $J$ uniform in the bottom-left, $K$ in the top-left, $L$ in the top-right, $M$ in the bottom-right (any cyclic labelling works). Join them in this order to form the quadrilateral $JKLM$ .

The quadrilateral is always simple. The two “vertical” sides $JK$ and $LM$ lie strictly in the left and right half-planes respectively, so they cannot meet; the two “horizontal” sides $KL$ and $MJ$ lie strictly in the upper and lower half-planes, so they cannot meet. The cyclic polygon is therefore self-non-crossing, and convex reduces to every interior turn bends the same way.

Only one vertex at a time can spoil it. A simple quadrilateral fails to be convex exactly when one of its four vertices lies inside the triangle formed by the other three. By symmetry of the setup across the four ranches, the four “bad” events have equal probability, and only one of them can occur at a time (you cannot have two vertices inside the triangles of the other three in a simple quadrilateral). So $P(\text{convex}) = 1 - 4 \, P(K \text{ is inside triangle } JLM).$

The single bad probability. Fix the two neighbours $J = (-a, -b)$ and $L = (p, q)$ in their respective ranches, with $a, b, p, q$ each uniform on $[0, 1]$ . The line $JL$ cuts across the top-left ranch (the one containing $K$ ), and the bad region for $K$ is the triangle bounded by $JL$ and the two axes (the boundary of the top-left ranch closest to the origin). Working out the slope-intercept geometry, this triangle has one vertex at the origin and legs of lengths $x = \frac{bp - aq}{b + q}, \qquad y = \frac{bp - aq}{a + p},$ so its (signed) area is $\tfrac12 xy$ , with sign flipping when $bp - aq$ flips. Squaring kills the sign, and another factor of $\tfrac12$ averages over the two configurations in which the triangle is actually inside the ranch (the other half of the time the bad region sits in the opposite ranch and is counted by symmetry). Each ranch has unit area, so the probability that $K$ lies in the bad triangle is the expected (signed-corrected) area: $\begin{aligned} P(K \in \text{bad triangle}) &= \frac{1}{4}\, \mathbb{E}\!\left[\frac{(bp - aq)^2}{(a + p)(b + q)}\right] \\ &= \frac{1}{4} \int_0^1\!\!\int_0^1\!\!\int_0^1\!\!\int_0^1 \frac{(bp - aq)^2}{(a + p)(b + q)}\, da\, db\, dp\, dq. \end{aligned}$

Closed form. This iterated integral can be evaluated either by hand (partial fractions then a $\ln 2$ collection) or symbolically. The result is $\begin{aligned} \int_0^1\!\!\int_0^1\!\!\int_0^1\!\!\int_0^1 \frac{(bp - aq)^2}{(a + p)(b + q)}\, da\, db\, dp\, dq &= \frac{4\ln 2}{3} - \frac{5}{6}. \end{aligned}$ Putting it together with the four-fold symmetry, $P(\text{convex}) = 1 - 4 \cdot \tfrac{1}{4}\!\left(\frac{4\ln 2}{3} - \frac{5}{6}\right) = 1 - \frac{4\ln 2}{3} + \frac{5}{6} = \frac{11}{6} - \frac{4 \ln 2}{3}.$ So $\boxed{P(\text{convex}) = \frac{11}{6} - \frac{4 \ln 2}{3} \approx 0.909137}.$

The computation

Two independent checks: a symbolic evaluation of the integral above with sympy, and a Monte Carlo of the original random experiment (drop one house in each ranch, form the cyclic quadrilateral, test convexity). Both should reproduce $11/6 - 4\ln 2/3$ to their respective precisions.

import sympy as sp
a, b, p, q = sp.symbols('a b p q', positive=True)
integrand = (b * p - a * q) ** 2 / ((a + p) * (b + q))
I = sp.integrate(integrand, (a, 0, 1), (b, 0, 1), (p, 0, 1), (q, 0, 1))
P_bad = sp.Rational(1, 4) * I
P_convex = 1 - 4 * P_bad
print("integral =", sp.simplify(I))
print("P(convex) =", sp.simplify(P_convex), "=", float(P_convex))
# integral = -5/6 + 4*log(2)/3
# P(convex) = 11/6 - 4*log(2)/3 = 0.9091370925867396

import numpy as np
from numpy.linalg import det
rng = np.random.default_rng(0)

def is_convex(poly):
    signs = set()
    for i in range(4):
        a = poly[i] - poly[(i + 1) % 4]
        b = poly[(i + 2) % 4] - poly[(i + 1) % 4]
        signs.add(np.sign(det(np.array([a, b]))))
    return len(signs) == 1                          # every turn bends the same way

runs = 1_000_000; convex = 0
for _ in range(runs):
    q_poly = np.array([
        [rng.uniform(0, 1),  rng.uniform(0, 1) ],   # top-right
        [rng.uniform(-1, 0), rng.uniform(0, 1) ],   # top-left
        [rng.uniform(-1, 0), rng.uniform(-1, 0)],   # bottom-left
        [rng.uniform(0, 1),  rng.uniform(-1, 0)],   # bottom-right
    ])
    convex += is_convex(q_poly)
print(convex / runs)                                # ~0.9091