Can You Cut The Cookies?

The Riddler for December 4, 2020. The Express is a Secret Santa derangement, and the Classic is a hard (still open) dissection of an isosceles right triangle into three congruent pieces.

Riddler Express

A family of five draws names from a hat for a book exchange; if anyone draws their own name, everyone redraws. What is the probability that no one draws their own name?

The Riddler, FiveThirtyEight, December 4, 2020(original post)

Solution

This asks for the chance a random permutation of five elements is a derangement (no fixed point). Of the $5! = 120$ permutations, count those with no one mapped to themselves. By inclusion–exclusion, the number of derangements is $$D_5 = 5!\sum_{k=0}^{5}\frac{(-1)^k}{k!} = 120\left(1 - 1 + \tfrac12 - \tfrac16 + \tfrac1{24} - \tfrac1{120}\right) = 44.$$ Equivalently, by cycle structure: a derangement of five elements is either a single $5$-cycle ($4! = 24$ of them) or a $3$-cycle plus a $2$-cycle ($\binom{5}{2}\cdot 2 = 20$), totalling $44$. So $$P(\text{no fixed point}) = \frac{44}{120} = \boxed{\frac{11}{30}} \approx 0.367.$$

The computation

Encode the definition: count permutations of five with no fixed point.

import itertools
from fractions import Fraction
derangements = sum(1 for p in itertools.permutations(range(5))
                   if all(p[i] != i for i in range(5)))
print(derangements, Fraction(derangements, 120))    # 44  11/30

The probability of a clean draw is $44/120 = 11/30$.

Riddler Classic

You have cookie dough shaped as an isosceles right triangle and want to cut three congruent cookies, as large as possible, lying within the triangle without overlapping. What is the greatest percentage of the dough the three cookies can use?

The Riddler, FiveThirtyEight, December 4, 2020(original post)

Deferred (open problem)

Two or four congruent pieces can tile the isosceles right triangle exactly (it is “rep-tile” with $2$ and $4$ copies), wasting nothing. Three congruent pieces, however, leave dough behind, and the best achievable fraction is not known. The puzzle traces to Karl Scherer (Journal of Recreational Mathematics, 2002–03), whose published dissection used $90\%$. Better constructions accumulate: a trapezoidal cut reaches about $94.1\%$ (independently the column’s top entry and Scherer-era work by Dean Ballard), and a construction by Robert Wainwright and Richard Hess reaches about $$\boxed{\approx 95.5\% \text{ (best known; open problem)}}.$$ The column states plainly that whether one can do better remains open, so there is no exact optimum to compute; the answer is recorded as the best-known $\approx 95.5\%$. (With non-convex cutters allowed, the related “sphinx” version can approach $100\%$, but that does not settle the triangle.)