## 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

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

## How many chess grandmasters have the same first and last name?

The short answer is 6 (3 pairs).

Alireza Firouzja just became the youngest player to reach 2800 ELO at 18 years and 5 months, surpassing Magnus Carlsen’s record of 18 years and 11 months. He did so by grinding out a tricky endgame at the European Team Chess Championships over GM Shakhriyar Mamedyarov. Alireza is truly a prodigy, and he certainly has the potential to become the world champion. He recently qualified for the Candidates Tournament 2022 (a tournament in which players compete for a spot to challenge the reigning world champion), giving him an opportunity to become the youngest world champion ever (a record currently held by Garry Kasparov at 22 years of age).

Two of Alireza Firouzja’s teammates on the French team had somewhat similar names, Maxime Lagarde and Maxime Vachier-Lagrave (although Alireza was born in Iran, he changed federation due to Iranian rules barring their athletes from competing with Israelis). By some free association, this reminded me of the saga of Tigran Petrosian. Last fall, a friend sent an article about an Armenian grandmaster, Tigran Petrosian, who had been permanently banned from chess.com after cheating in the Pro Chess League. I naturally expressed surprise that a former world champion (and one that must be very elderly at that) would stoop to such lows. Moreover, Tigran Petrosian apparently sent unsavory messages to the GM that had reported him (Wesley So, Filipino-American super-GM and #7 on the live rankings).

“You are a biggest looser I ever seen in my life! You was doing PIPI in your pampers when I was beating players much more stronger then you!”

Tigran L Petrosian to Wesley So

To my surprise, it turns out there were actually two chess grandmasters named Tigran Petrosian! There was the world champion Tigran V. Petrosian (1929-1984), and Tigran L. Petrosian who was named after the world champion (1984-). The two were not related at all. Tigran V. was an 8-time Candidate, and became the first Armenian world champion in 1963 by defeating Boris Spassky. Tigran L. is a strong grandmaster (peak rating 2671, currently 2573) but is certainly not a super-GM.

In any case, this had me wondering how many chess grandmasters had the same name. I sorted through a Wikipedia list containing all 1948 chess grandmasters to try to identify other examples. The most common repeated last names were Guseinov (4), Hansen (5), Ivanov (5), and Petrosian (4). The only other grandmasters with identical first and last names that I identified were:

1. Alexander Ivanov (b. 1956) and Alexander A. Ivanov (b. 1965). This was almost certainly just a concidence.
2. Alexander Zaitsev (b. 1935) and Alexander Zaitsev (b. 1985). I was not able to find details on whether the younger Zaitsev was named after the other.
1. Not a chess player, but Alexander Zaitsev (figure skater) and his partner Irina Rodnina are two-time Olympic gold medalists. See their short program at Innsbruck, Austria in 1976 below.