How are nine-dart finishes related to determining the composition of atoms?

Short Answer: Both are applications of the change-making problem.

A leg (single game) of darts requires the player to score exactly 501 points, ending with either a double or the bullseye. Each shot consists of 3 darts, and each dart may at most score 60 points (triple 20). Therefore, the minimum number of darts necessary to finish a game is 9. The most traditional way to achieve this feat is by scoring a triple 20 on each of the first 6 throws, leaving 141 to score on the final three darts (known as the outshot). There are three preferred ways for performing the outshot:

1. Triple 20, triple 19, and double 12
2. Triple 20, triple 15, and double 18
3. Triple 17, triple 18, and double 18

However, there are many more than 3 ways to achieve this score. As a matter of fact, Wikipedia provides a handy table showing there are 3944 ways of achieving such a finish (574 if double-in, double-out). Calculating the number of ways of achieving this score is an application of the change-making problem, itself a special case of the knapsack problem.

The change-making problem seeks to find the fewest number of coins (of integer denominations) that add up to a given amount of money. This is directly analogous to finding the fewest number of darts (which are each worth integer scores) to reach 501 (the “given sum of money”). The change-making problem is a variation on the coin change problem – in which one wishes to find the possible ways of using infinite coins of prespecified denominations to make change for a specific amount of money. With a few constraints, it is easy to imagine how these problems relate to the nine-dart finish question. At first blush, it seems one could solve these problems by using as many of the largest denomination coin/dart as possible, then progressing to the next largest etc. This technique actually works for American coin denominations. However, this “greedy” algorithm does not work in general. For example, using 8 triple 20s (480), will leave a remainder of 21, which cannot be achieved with a double.

Instead, these problems may be solved in pseudo-polynomial time by using dynamic programming. Without going too much into technical details, this technique involves finding all combinations of smaller values that sum to the current threshold, then using this stored information to work up to the goal amount.

Another application of the change-making problem is in finding combinations of atoms that could comprise a mass/charge (m/z) peak in mass spectrometry (MS). In this case, the possible constituent atoms each have an integer mass/charge (denomination of coins) that we will try to sum up to an observed mass/charge peak (“given sum of money”).

Bonus questions:

1. Who has the most televised nine-dart finishes in history?
2. Who achieved the first televised nine-dart finish?
3. Who plays Ted Lasso in Ted Lasso?

References

1. Burns, Brian. Encyclopedia of Games: Rules and Strategies. Page 269.
2. https://en.wikipedia.org/wiki/Nine-dart_finish
3. https://algodaily.com/challenges/the-coin-change-problem

Answers:

1. Phil Taylor with 11. Michael van Gerwen is in second with 7.
2. John Lowe
3. Jason Sudeikis