Posted on May 26, 2019
This is a solution to the problem posed on May 24's edition of the Riddler Classic on fivethirtyeight.com, "One Small Step For Man, One Giant Coin Flip For Mankind".
We will show that there are $12$ nontrivial solutions to the $3$astronaut problem with $4$ coins and $2$ nontrivial solutions to the $5$astronaut problem with $6$ coins.
The problem statement walks through the impossibility of using two coins, with $2^2=4$ outcomes, to determine a winner for three astronauts. The same can be said for three flips, which we will briefly discuss.
The key to attacking this problem for an $n$astronaut scenario is equally distributing outcomes amongst the first $n1$ astronauts. For the $3$astronaut, $3$flip case this translates to the following: among the $1$, $3$, $3$, and $1$ outcomes ($0$ heads, $1$ head, $2$ heads, and $3$ heads respectively), the first and second astronauts should have the same number each of $0$head, $1$head, $2$head, and $3$head outcomes. One possible assignment that meets this parameter is for the first and second astronauts to each have the distributions $0$, $1$, $1$, $0$, leaving the third astronaut with the distribution $1$, $1$, $1$, $1$. This is summarized in the table, below.
3 Heads 0 Tails  2 Heads 1 Tail  1 Head 2 Tails  0 Heads 3 Tails 


Astro #1  0  1  1  0 
Astro #2  0  1  1  0 
Astro #3  1  1  1  1 
Total  1  3  3  1 
This distribution, however, implies that the probability of flipping three heads and zero heads is both zero, a contradiction. All distributions with $3$ astronauts and $3$ coins yield similar contradictions.
There is no rigorous proof here to the claim that the first $n1$ astronauts must have the same distribution of outcomes, but the likelihood of them having different outcomes that independently add up to a very specific fraction is highly unlikely. Further work below will show it's analogous to polynomials with different integer coefficients having an identical real root between $0$ and $1$.
We broaden our horizons to a $4$coin solution, which has the $2^4=16$ outcomes of $1$, $4$, $6$, $4$, $1$, for $4$, $3$, $2$, $1$, and $0$ heads respectively. For three astronauts, we have significantly more ways to distribute the coin flips. For example, the first two astronauts could each be given the outcome distribution $0$, $2$, $3$, $2$, $0$, leaving $1$, $0$, $0$, $0$, $1$ for the third astronaut. This is summarized in the table, below.
4 Heads 0 Tails  3 Heads 1 Tail  2 Heads 2 Tails  1 Head 3 Tails  0 Heads 4 Tails 


Astro #1  0  2  3  2  0 
Astro #2  0  2  3  2  0 
Astro #3  1  0  0  0  1 
Total  1  4  6  4  1 
We now have to see if a solution exists with this distribution. Let $h$ be the probability of flipping a heads, and $t=1h$ be the probability of flipping a tails. We generate the probabilities of each flipping outcome: for $k$ heads in $n$ flips, a specific outcome (ignoring rearrangments) is $h^k t^{nk} = h^k (1h)^{nk}$. Using the current example from the above table, our probability polynomial for astronaut 1 (and equivalently astronaut 2) becomes
\begin{eqnarray} 2 h^3 (1h) + 3 h^2 (1h)^2 + 2 h (1h)^3 &=& \frac{1}{3} \\ h^4 + 2h^3 3 h^2 + 2h &=& \frac{1}{3} \end{eqnarray} $$ h = \frac{1}{6} \left( 3 \pm \sqrt{3 \left(4\sqrt{6} 9\right)} \right) \approx 0.242, 0.758 $$Therefore, we can state that one solution is with $h=.242$, the first astronaut getting assigned $2$, $3$, and $2$ each of the $3$head, $2$head, and $1$head outcomes, and the third astronaut being assigned the $4$head and $0$head outcomes.
As an aside, it makes sense to have symmetric solutions here (that is, they add up to $1$), since we picked symmetric coefficients $2$, $3$, and $2$. We expect an asymmetric pick like $1$, $3$, $2$ to not yield symmetric solutions.
Let's generalize further to find all $3$astronaut, $4$coin solutions. There are $4$ outcomes with $3$ heads, so astronauts one and two could each get $0$, $1$, or $2$. Similarly they could get $0$, $1$, $2$, or $3$ and $0$, $1$, or $2$ of the $2$head outcomes and $1$head outcomes respectively. We need to test all of these scenarios, which we accomplish using the following code.
import numpy as np import operator as op from functools import reduce from collections import namedtuple Solution = namedtuple('Solution', 'coefficients roots') def ncr(n, r): """Implementation of n choose r = n!/(r!*(nr)!)""" r = min(r, nr) numer = reduce(op.mul, range(n, nr, 1), 1) denom = reduce(op.mul, range(1, r+1), 1) return numer / denom def create_polys(num_coins): """Creates polynomial expansions in list form for n1 to 1 heads""" polys = [] for i in range(1, num_coins): poly = [] neg = (1)**i for j in range(0, i+1): poly.append(ncr(i, j) * neg) neg *= 1 for k in range(i+1, num_coins): poly.append(0) polys.append(poly) return polys def create_coeff_limits(num_coins, num_astronauts): """Determines the maximum allocation of head/tail outcomes based off the number of coins and astronauts""" coeffs = [] for i in range(1, num_coins): coeffs.append(ncr(num_coins, i) // (num_astronauts  1) + 1) return coeffs def is_valid_solution(root): """Checks if root is valid. Must be real and between 0 and 1.""" return np.isreal(root) and 0 < root < 1 def solve_poly(coeffs, polys, prob): """Generates and solves polynomials using np.roots coeffs: list of "coefficients", i.e. multipliers for the number of out head/tail outcomes polys: generated with create_polys prob: the negated probability 1/num_astronauts returns all valid solutions a list on named tuples """ sum_poly = [] valid_solutions = [] for degree in range(len(polys[0])): term = 0 for j in range(len(polys)): # for each polynomial term += coeffs[j] * polys[j][degree] sum_poly.append(term) sum_poly.append(prob) ans = np.roots(sum_poly) for root in ans: if is_valid_solution(root): valid_solutions.append(Solution(coeffs, root)) return valid_solutions def main(): num_astronauts = 3 num_coins = 6 prob = 1.0/num_astronauts polys = create_polys(num_coins) coeff_limits = create_coeff_limits(num_coins, num_astronauts) solutions = [] # Loop through all possible coefficient combinations coeff_dividers = [] for i in range(1, len(coeff_limits)): coeff_dividers.append(reduce(op.mul, coeff_limits[i:], 1)) # This helps us avoid recursion and nested for loops for i in range(reduce(op.mul, coeff_limits, 1)): coeffs = [] for j in range(len(coeff_dividers)): coeffs.append((i // coeff_dividers[j]) % coeff_limits[j]) coeffs.append(i % coeff_limits[1]) solutions += solve_poly(coeffs, polys, prob) for solution in solutions: print solution.coefficients, np.real(solution.roots) #strip 0.j print "Number of solutions:", len(solutions) if __name__ == '__main__': main()
This code, with num_astronauts=3 and num_coins=4 yields the following 12 solutions, where the five listed values correspond to distributions with $4$, $3$, $2$, $1$, and $0$ heads respectively.
$h$  Astronauts 1 & 2  Astronaut 3 

0.4505  0, 0, 3, 2, 0  1, 4, 0, 0, 1 
0.2861  0, 0, 3, 2, 0  1, 4, 0, 0, 1 
0.6051  0, 1, 3, 2, 0  1, 2, 0, 0, 1 
0.2578  0, 1, 3, 2, 0  1, 2, 0, 0, 1 
0.6967  0, 2, 2, 2, 0  1, 0, 2, 0, 1 
0.3033  0, 2, 2, 2, 0  1, 0, 2, 0, 1 
0.7139  0, 2, 3, 0, 0  1, 0, 0, 4, 1 
0.5495  0, 2, 3, 0, 0  1, 0, 0, 4, 1 
0.7422  0, 2, 3, 1, 0  1, 0, 0, 2, 1 
0.3949  0, 2, 3, 1, 0  1, 0, 0, 2, 1 
0.7579  0, 2, 3, 2, 0  1, 0, 0, 0, 1 
0.2421  0, 2, 3, 2, 0  1, 0, 0, 0, 1 
The problem is easily generalized with the above code to higher numbers of astronauts. There are two solutions for $5$ astronauts and $6$ coins, where the seven listed values correspond to distributions with $6$, $5$, $4$, $3$, $2$, $1$, and $0$ heads respectively.
$h$  Astronauts 1, 2, 3, & 4  Astronaut 5 

0.4326  0, 1, 3, 5, 3, 1, 0  1, 2, 3, 0, 3, 2, 1 
0.5674  0, 1, 3, 5, 3, 1, 0  1, 2, 3, 0, 3, 2, 1 
$h$  Astronauts 1, 2, 3, & 4  Astronaut 5 

0.4662  0, 0, 3, 8, 8, 5, 1, 0  1, 7, 9, 3, 3, 1, 3, 1 
0.3636  0, 0, 3, 8, 8, 5, 1, 0  1, 7, 9, 3, 3, 1, 3, 1 
0.4536  0, 0, 4, 7, 8, 5, 1, 0  1, 7, 5, 7, 3, 1, 3, 1 
0.3863  0, 0, 4, 7, 8, 5, 1, 0  1, 7, 5, 7, 3, 1, 3, 1 
0.5215  0, 0, 4, 8, 8, 5, 1, 0  1, 7, 5, 3, 3, 1, 3, 1 
0.3468  0, 0, 4, 8, 8, 5, 1, 0  1, 7, 5, 3, 3, 1, 3, 1 
0.527  0, 0, 5, 7, 8, 5, 1, 0  1, 7, 1, 7, 3, 1, 3, 1 
0.359  0, 0, 5, 7, 8, 5, 1, 0  1, 7, 1, 7, 3, 1, 3, 1 
0.5343  0, 0, 5, 8, 7, 5, 1, 0  1, 7, 1, 3, 7, 1, 3, 1 
0.3845  0, 0, 5, 8, 7, 5, 1, 0  1, 7, 1, 3, 7, 1, 3, 1 
0.543  0, 0, 5, 8, 8, 4, 1, 0  1, 7, 1, 3, 3, 5, 3, 1 
0.4207  0, 0, 5, 8, 8, 4, 1, 0  1, 7, 1, 3, 3, 5, 3, 1 
0.5513  0, 0, 5, 8, 8, 5, 0, 0  1, 7, 1, 3, 3, 1, 7, 1 
0.4487  0, 0, 5, 8, 8, 5, 0, 0  1, 7, 1, 3, 3, 1, 7, 1 
0.5742  0, 0, 5, 8, 8, 5, 1, 0  1, 7, 1, 3, 3, 1, 3, 1 
0.3363  0, 0, 5, 8, 8, 5, 1, 0  1, 7, 1, 3, 3, 1, 3, 1 
0.4564  0, 1, 2, 8, 8, 5, 1, 0  1, 3, 13, 3, 3, 1, 3, 1 
0.3758  0, 1, 2, 8, 8, 5, 1, 0  1, 3, 13, 3, 3, 1, 3, 1 
0.5278  0, 1, 3, 8, 8, 5, 1, 0  1, 3, 9, 3, 3, 1, 3, 1 
0.3532  0, 1, 3, 8, 8, 5, 1, 0  1, 3, 9, 3, 3, 1, 3, 1 
0.5376  0, 1, 4, 7, 8, 5, 1, 0  1, 3, 5, 7, 3, 1, 3, 1 
0.3673  0, 1, 4, 7, 8, 5, 1, 0  1, 3, 5, 7, 3, 1, 3, 1 
0.5519  0, 1, 4, 8, 7, 5, 1, 0  1, 3, 5, 3, 7, 1, 3, 1 
0.396  0, 1, 4, 8, 7, 5, 1, 0  1, 3, 5, 3, 7, 1, 3, 1 
0.5674  0, 1, 4, 8, 8, 4, 1, 0  1, 3, 5, 3, 3, 5, 3, 1 
0.4326  0, 1, 4, 8, 8, 4, 1, 0  1, 3, 5, 3, 3, 5, 3, 1 
0.5793  0, 1, 4, 8, 8, 5, 0, 0  1, 3, 5, 3, 3, 1, 7, 1 
0.457  0, 1, 4, 8, 8, 5, 0, 0  1, 3, 5, 3, 3, 1, 7, 1 
0.5995  0, 1, 4, 8, 8, 5, 1, 0  1, 3, 5, 3, 3, 1, 3, 1 
0.3409  0, 1, 4, 8, 8, 5, 1, 0  1, 3, 5, 3, 3, 1, 3, 1 
0.5566  0, 1, 5, 6, 8, 5, 1, 0  1, 3, 1, 11, 3, 1, 3, 1 
0.3849  0, 1, 5, 6, 8, 5, 1, 0  1, 3, 1, 11, 3, 1, 3, 1 
0.5831  0, 1, 5, 7, 7, 5, 1, 0  1, 3, 1, 7, 7, 1, 3, 1 
0.4169  0, 1, 5, 7, 7, 5, 1, 0  1, 3, 1, 7, 7, 1, 3, 1 
0.604  0, 1, 5, 7, 8, 4, 1, 0  1, 3, 1, 7, 3, 5, 3, 1 
0.4481  0, 1, 5, 7, 8, 4, 1, 0  1, 3, 1, 7, 3, 5, 3, 1 
0.6155  0, 1, 5, 7, 8, 5, 0, 0  1, 3, 1, 7, 3, 1, 7, 1 
0.4657  0, 1, 5, 7, 8, 5, 0, 0  1, 3, 1, 7, 3, 1, 7, 1 
0.6287  0, 1, 5, 7, 8, 5, 1, 0  1, 3, 1, 7, 3, 1, 3, 1 
0.351  0, 1, 5, 7, 8, 5, 1, 0  1, 3, 1, 7, 3, 1, 3, 1 
0.6151  0, 1, 5, 8, 6, 5, 1, 0  1, 3, 1, 3, 11, 1, 3, 1 
0.4434  0, 1, 5, 8, 6, 5, 1, 0  1, 3, 1, 3, 11, 1, 3, 1 
0.6137  0, 1, 5, 8, 7, 4, 0, 0  1, 3, 1, 3, 7, 5, 7, 1 
0.5464  0, 1, 5, 8, 7, 4, 0, 0  1, 3, 1, 3, 7, 5, 7, 1 
0.6327  0, 1, 5, 8, 7, 4, 1, 0  1, 3, 1, 3, 7, 5, 3, 1 
0.4624  0, 1, 5, 8, 7, 4, 1, 0  1, 3, 1, 3, 7, 5, 3, 1 
0.641  0, 1, 5, 8, 7, 5, 0, 0  1, 3, 1, 3, 7, 1, 7, 1 
0.473  0, 1, 5, 8, 7, 5, 0, 0  1, 3, 1, 3, 7, 1, 7, 1 
0.649  0, 1, 5, 8, 7, 5, 1, 0  1, 3, 1, 3, 7, 1, 3, 1 
0.3713  0, 1, 5, 8, 7, 5, 1, 0  1, 3, 1, 3, 7, 1, 3, 1 
0.6242  0, 1, 5, 8, 8, 2, 1, 0  1, 3, 1, 3, 3, 13, 3, 1 
0.5436  0, 1, 5, 8, 8, 2, 1, 0  1, 3, 1, 3, 3, 13, 3, 1 
0.6364  0, 1, 5, 8, 8, 3, 0, 0  1, 3, 1, 3, 3, 9, 7, 1 
0.5338  0, 1, 5, 8, 8, 3, 0, 0  1, 3, 1, 3, 3, 9, 7, 1 
0.6468  0, 1, 5, 8, 8, 3, 1, 0  1, 3, 1, 3, 3, 9, 3, 1 
0.4722  0, 1, 5, 8, 8, 3, 1, 0  1, 3, 1, 3, 3, 9, 3, 1 
0.6532  0, 1, 5, 8, 8, 4, 0, 0  1, 3, 1, 3, 3, 5, 7, 1 
0.4785  0, 1, 5, 8, 8, 4, 0, 0  1, 3, 1, 3, 3, 5, 7, 1 
0.6591  0, 1, 5, 8, 8, 4, 1, 0  1, 3, 1, 3, 3, 5, 3, 1 
0.4005  0, 1, 5, 8, 8, 4, 1, 0  1, 3, 1, 3, 3, 5, 3, 1 
0.6637  0, 1, 5, 8, 8, 5, 0, 0  1, 3, 1, 3, 3, 1, 7, 1 
0.4258  0, 1, 5, 8, 8, 5, 0, 0  1, 3, 1, 3, 3, 1, 7, 1 
0.6678  0, 1, 5, 8, 8, 5, 1, 0  1, 3, 1, 3, 3, 1, 3, 1 
0.3322  0, 1, 5, 8, 8, 5, 1, 0  1, 3, 1, 3, 3, 1, 3, 1 
The code below is an bruteforce solution to the Riddler Express problem about soccer team selection. The smallest solution found was with jersey numbers $1$, $5$, $6$, $8$, $9$, $10$, $12$, $15$, $18$, $20$, and $24$.
import itertools def brute_soccer(team_list): average_score = sum([1./i for i in team_list]) if abs(average_score2.0) < 1e8: print team_list, average_score for i in itertools.combinations(range(1, 25), 11): brute_soccer(i)