Expert: Paul Klarreich - 9/4/2007

Question
If there is a dartboard with scores 8 and 5 and you have an infinite amount of darts, what is the highest score you CANNOT get thant is under 100. I got this as a freshman math question, and I know its probably really easy, but I can't figure it out.

Answer
Questioner:   Hayden
Category:  Advanced Math
Private:  No
 
Subject:  Dartboard Problem
Question:  If there is a dartboard with scores 8 and 5 and you have an infinite amount of darts, what is the highest score you CANNOT get that is under 100. I got this as a freshman math question, and I know its probably really easy, but I can't figure it out.

Hi, Hayden,

The 100 has nothing to do with the problem.  We shall prove that the largest such number is 27 -- anything over 100, in fact anything 28 or more can be done.

.........................................

Before I answer this question, I propose this Mathematical Induction proof.  If you are not familiar with MI, it works this way:

.........................................

You want to prove a statement true for all integers n that are at least some basic number, called the Base Case.  (Usually that is 1, but it can be any number and in our example it will be 31.)  You proceed as follows:

A. Check that the statement is true in the base case. (Usually very easy.)
B. Assume it is true for  n = k, then prove it is true for n = k+1, using the assumption.

..........................................

I will change the terms a bit.  Instead of the dartboard, I will make up 'coins' that are worth either 5 cents or 8 cents.  Then I ask 'what is the largest amount that can NOT be paid with these coins without requiring change?'

Example:  You CAN buy something for  43 cents using 7 5-c pieces and one 8-cent piece.  You CANNOT buy something for 9 cents.
.....................................
Claim:  Any amount that is at least 34 cents can be bought this way.

Proof: Base case is n = 34.  (Three 8's = 24) plus (two 5's = 10) = 34.

Now given a pile of coins worth k cents, made with 5's and 8's.  Can this pile be converted into a pile worth one cent more, still using 5's and 8's?  

Yes.

Suppose the pile (worth at least 34, remember) contains at least three 5's.  Then take out the three 5's, worth 15, and replace them with two 8's, worth 16, increasing the value by 1.

Suppose it does not have at least three 5's.  Then whatever 5's are in the pile can be worth at most 10 cents, therefore the 8's in the pile (worth at least 34, remember) are worth at least 24 cents, and thus there are at least three of them.  Replace the three 8's, worth 24, by five 5's, worth 25, again increasing the value by 1.


So we can easily prove that any value at least 34 can be achieved; therefore our highest unmakable score must be less than 34 and we can simply check them going down:

33 = 8 + 25
32 = 4*8
31 = 16 + 15
30 = 5*6
29 = 5 + 24
28 = 8 + 20
27 cannot be done.  That's it.