Horse race puzzle

Introduction

This post is part pedagogical rant, part discussion of a beautiful technique in combinatorics, both motivated by a recent exchange with a high school student, about an interesting dice game that seems to be a common introductory exercise in probability:

There are 12 horses, numbered 1 through 12, each initially at position 0 on a track.  Play consists of a series of turns: on each turn, the teacher rolls two 6-sided dice, where the sum of the dice indicates which horse to advance one position along the track.  The first horse to reach position n=5 wins the race.

At first glance, this seems like a nice exercise.  Students quickly realize, for example, that horse #1 is a definite loser– the sum of two dice will never equal 1– and that horse #7 is the best bet to win the race, with the largest probability (1/6) of advancing on any given turn.

But what if a student asks, as this particular student did, “Okay, I can see how to calculate the distribution of probabilities of each horse advancing in a single turn, but what about the probabilities of each horse winning the race, as a function of the race length n?”  This makes me question whether this is indeed such a great exercise, at least as part of an introduction to probability.  What started as a fun game and engaging discussion has very naturally led to a significantly more challenging problem, whose solution is arguably beyond most students– and possibly many teachers as well– at the high school level.

I like this game anyway, and I imagine that I would likely use it if I were in a similar position.  Although the methods involved in an exact solution might be inappropriate at this level, the game still lends itself nicely to investigation via Monte Carlo simulation, especially for students with a programming bent.

Poissonization

There is an exact solution, however, via several different approaches.  This problem is essentially a variant of the coupon collector’s problem in disguise: if each box of cereal contains one of 12 different types of coupons, then if I buy boxes of cereal until I have n=5 of one type of coupon, what is the probability of stopping with each type of coupon?  Here the horses are the coupon types, and the dice rolls are the boxes of cereal.

As in the coupon collector’s problem, it is helpful to modify the model of the horse race in a way that, at first glance, seems like unnecessary additional complexity: suppose that the dice rolls occur at times distributed according to a Poisson process with rate 1.  Then the advances of each individual horse (that is, the subsets of dice rolls with each corresponding total) are also Poisson processes, each with rate equal to the probability p_i of the corresponding dice roll.

Most importantly, these individual processes are independent, meaning that we can easily compute the probability of desired states of the horses’ positions on the track at a particular time, as the product of the individual probabilities for each horse.  Integrating over all time yields the desired probability that horse j wins the race:

P(j) = \displaystyle\int_{0}^{\infty} p_j \frac{e^{-p_j t}(p_j t)^{n-1}}{(n-1)!} \prod\limits_{i \neq j} \sum\limits_{k=0}^{n-1} \frac{e^{-p_i t}(p_i t)^k}{k!} dt

Intuitively, horse j advances on the final dice roll, after exactly n-1 previous advances, while each of the other horses has advanced at most n-1 times.

Generating functions

This “Poissonization” trick is not the only way to solve the problem, and in fact may be less suitable for implementation without a sufficiently powerful computer algebra system.  Generating functions may also be used to “encode” the possible outcomes of dice rolls leading to victory for a particular horse, as follows:

G_j(x) = p_j \frac{(p_j x)^{n-1}}{(n-1)!} \prod\limits_{i \neq j} \sum\limits_{k=0}^{n-1} \frac{(p_i x)^k}{k!} 

where the probability that horse j wins on the m+1-st dice roll is m! times the coefficient of x^m in G_j(x).  Adding up these probabilities for all possible m yields the overall probability of winning.  This boils down to simple polynomial multiplication and addition, allowing relatively straightforward implementation in Python, for example.

The results are shown in the following figure.  Each curve corresponds to a race length, from n=1 in black– where the outcome is determined by a single dice roll– to n=6 in purple.

Probability distribution of each horse winning, with each curve corresponding to a race length n from 1 to 6.

As intuition might suggest, the longer the race, the more likely the favored horse #7 is to win.  This is true for any non-uniformity in the single-turn probability distribution.  For a contrasting example, consider a race with just 6 horses, with each turn decided by a single die roll.  This race is fair no matter how long it is; every horse always has the same probability of winning.  But if the die is loaded, no matter how slightly, then the longer the race, the more advantage to the favorite.

The hardest 24 puzzles

Introduction

Once again motivated by a series of interesting posts by Mark Dominus, a “24 puzzle” is a set of 4 randomly selected numbers from 1 to 9, where the objective is to arrange the numbers in an arithmetic expression using only addition, subtraction, multiplication, and division, to yield the value 24.  For example, given the numbers (3, 5, 5, 9), one solution is

5(3 + \frac{9}{5}) = 24

Solutions are in general not unique; for example, another possibility is

3(9 - \frac{5}{5}) = 24

This is a great game for kids, and it can be played with no more equipment than a standard deck of playing cards: remove the tens and face cards, shuffle the remaining 36 cards, and deal 4 cards to “generate” a puzzle.  Or keep all 52 cards, and generate potentially more difficult puzzles involving numbers from 1 to 13 instead of 1 to 9.

Or you could play the game using a different “target” value other than 24… but should you?  That is, is there anything special about the number 24 that makes it more suitable as a target value than, say, 25, or 10, etc.?  And whatever target value we decide to use, what makes some puzzles (i.e., sets of numbers) more difficult to solve than others?  What are the hardest puzzles?  Finally, subtraction is one of the allowed binary operations; what about unary minus (i.e., negation)?  Is this allowed?  Does it matter?  These are the sort of questions that make a simple children’s game a great source of interesting problems for both mathematics and computer science students.

(Aside: Is it “these are the sort of questions” or “these are the sorts of questions”?  I got embarrassingly derailed working on that sentence.  I could have re-worded to avoid the issue entirely, but it’s interesting enough that I choose to leave it in.)

Enumerating possible expressions

Following is my Mathematica implementation of a 24 puzzle “solver”:

trees[n_Integer] := trees[n] =
  If[n == 0, {N},
   Flatten@Table[Outer[Star,
      trees[k], trees[n - 1 - k]],
     {k, 0, n - 1}]]

sub[expr_, values_List, ops_List] :=
 Quiet@Fold[
   ReplacePart[#1,
     MapThread[Rule, {Position[#1, First[#2]], Last[#2]}]] &,
   expr,
   {{N, values}, {Star, ops}}]

search[visit_, values_List, ops_List] :=
 Outer[visit,
  trees[Length[values] - 1],
  Permutations[values],
  Tuples[ops, Length[values] - 1], 1]

The function trees[n] enumerates all possible expression trees involving n binary operations, which are counted by the Catalan numbers.  Each expression tree is just a “template,” with placeholders for the numbers and operators that will be plugged in using the function sub.  For example, a standard 24 puzzle with 4 numbers requires n=3 operators, in one of the following 5 patterns:

N * (N * (N * N))
N * ((N * N) * N)
(N * N) * (N * N)
(N * (N * N)) * N
((N * N) * N) * N

The function search takes a puzzle represented as a set of numbers and set of available operators, and simply explores the outer product of all possible expression trees, permutations of numbers, and selections of operators, “visiting” each resulting expression in turn.

The choice of visitor depends on the question we want to answer.  For example, the following code solves a given puzzle for a given target value, with a visitor that checks each evaluated expression’s value against the target, and pretty-prints the expression if it matches:

show[expr_, values_List, ops_List] :=
 ToExpression[
  ToString@sub[expr, ToString /@ values, ToString /@ ops],
  InputForm, HoldForm]

solve[target_Integer, values_List, ops_List] :=
 Reap@search[
     If[sub[##] == target, Sow@show[##]] &,
     values, ops] // Last // Flatten

But another useful visitor is just sub itself, in which case search computes the set of all possible values that can be made from all possible arithmetic arrangements of the given numbers and operators.  We can use this information in the following sections.

Why 24?

Suppose that we draw 4 random cards from a deck of 36 cards (with face cards removed); what is the probability that the resulting puzzle is solvable?  The answer depends on the target– are we trying to find an expression that evaluates to 24, or to some other value?  The following figure shows the probability that a randomly selected puzzle is solvable, as a function of the target value.

Probability that a randomly selected puzzle, as dealt from a 36-card deck, is solvable, vs. the target value (usually 24).

The general downward trend makes sense: it’s more difficult to make larger numbers.  But most interesting are the targets that are multiples of 12 (highlighted by the vertical grid lines), whose corresponding probabilities are distinctly higher than their neighbors.  This also makes sense, at least in hindsight (although I doubt I would have predicted this behavior): multiples of 12 have a relatively large number of factors, allowing more possible ways to be “built.”

So this explains at least in part why 24 is “the” target value… but why not 12, for example, especially since it has an even higher probability of being solvable (i.e., an even lower probability of frustrating a child playing the game)?  The problem is that the target of 12 seems to be too easy, as the following figure shows, indicating for each target the expected number of different solutions to a randomly selected solvable puzzle:

Expected number of solutions to a randomly selected puzzle, conditioned on the puzzle being solvable, vs. the target value.

Of course, this just pushes the discussion in the other direction, asking whether a larger multiple of 12, like 36, for example, wouldn’t be an even better target value, allowing “difficult” puzzles while still having an approximately 84% probability of being solvable.  And it arguably would be, at least for more advanced players or students.

More generally, the following figure shows these two metrics together, with the expected number of solutions on the x-axis, and the probability of solvability on the y-axis, for each target value, with a few highlighted alternative target values along/near the Pareto frontier:

Probability of solvability vs. expected number of solutions.

The hardest 24 puzzles

Finally, which 24 puzzles are the hardest to solve?  The answer depends on the metric for difficulty, but one reasonable choice is the number of distinct solutions.  That is, among all possible expression trees, permutations of the numbers in the puzzle, and choices of available operators, how many yield the desired target value of 24?  The fewer the possible arrangements that work, the more difficult the puzzle.

It turns out that there are relatively few puzzles that have a unique solution, with exactly one possible arrangement of numbers and operators that evaluates to 24.  The list is below, where for completeness I have included all puzzles involving numbers up to 13 instead of just single digits.  (It’s worth noting that Mark’s example— which is indeed difficult– of arranging (2, 5, 6, 6) to yield 17, would not make this list.  And some of the puzzles that are on this list are arguably pretty easy, suggesting that there is something more to “hardness” than just uniqueness.)

  • (1, 2, 7, 7)
  • (1, 3, 4, 6)
  • (1, 5, 11, 11)
  • (1, 6, 6, 8)
  • (1, 7, 13, 13)
  • (1, 8, 12, 12)
  • (2, 3, 5, 12)
  • (3, 3, 5, 5)
  • (3, 3, 8, 8)
  • (4, 4, 10, 10)
  • (5, 5, 5, 5)
  • (5, 5, 8, 8)
  • (5, 5, 9, 9)
  • (5, 5, 10, 10)
  • (5, 5, 11, 11)
  • (5, 5, 13, 13)

And one more: (3, 4, 9, 10), although this one is special.  It has no solution involving only addition, subtraction, multiplication, and division.  For this puzzle, we must expand the set of available operators to also include exponentiation… and then the solution is unique.