Hi,
On a dartboard, the only two points you can score are 9 and 16. What is the highest score you cannot obtain through this dartboard?

How do you solve this problem?

It is a very complicated problem indeed. A possible solution is following:
Suppose we can get number m. Since we can only score 9 or 16 we can present m as
m = 9k + 16n, where k and n are some non-negative integers (it means we hit 9 score k times and n score n times).

Let’s see how we can get (m + 2) score.

m + 2 = 9(k + 2) + 16(n – 1)

Why is it so?

Since we can add or deduct only multiples of 9 or 16 let’s write them out (in two columns):

9 16
18 32
27 48
36 64
45 80
54 96
63 112
72 128

We need to pick one number from one column with “+” sign and another from the other column with “–“ sign, so that the result would be m + … – … = m + 2
We can see that +18 and – 16 fits.

So m + 2 = m + 18 – 16 = m + 9 × 2 – 16 × 1
Note that m = 9k + 16n, so m + 2 = 9k + 16n + 9 × 2 – 16 × 1 = 9(k + 2) + 16(n – 1)
Using same reasoning we can get:

m + 1 = 9(k - 7) + 16(n + 4)
m + 2 = 9(k + 2) + 16(n – 1)
m + 3 = 9(k – 5) + 16(n + 3)
m + 4 = 9(k + 4) + 16(n – 2)
m + 5 = 9(k – 3) + 16(n + 2)
m + 6 = 9(k + 6) + 16(n – 3)
m + 7 = 9(k – 1) + 16(n + 1)
m + 8 = 9(k + 8) + 16(n – 4)

Therefore if k is greater or equals 7 and n is greater or equals 4 we can score any number greater than m.

If k = 7 and n = 4 m = 127.

If k = 6 and n = 4 m=118. Using above stated representation for m + 1, m + 2 … We can represent any number from 120 to 126 but we can not do it for 119.

We can show that 119 can not be represented as 9k + 16n. For that we deduct multiples of 16 from 119 and check if the result is divisible by 9.

119 – 16 = 103
119 –32 = 87
119 – 48 = 71
119 – 64 = 55
119 – 80 = 39
119 – 96 = 23
119 – 112 = 7

None of the results is divisible by 9. So 119 can not be a score in this game. We also have proven that any number greater than 119 can be.

So the answer is 119.