From Games Magazine: given a dart board with two scores (5 & 7), and as many darts as you like, what is the highest total score that cannot be achieved?
What's the general solution with available scores A & B?
Oh boy, modular arithmetic.
In the specific case where 5 is a possible score, there's a fairly straightforward approach to finding the answer. We can group all positive numbers by the least significant digit. If we can get that last digit correct, we can hit our desired number by throwing pairs of darts into the 5 ring (scoring 10 points, which does not change the last digit). Zero and five are easy. Sinking one dart into the 7 gives us sevens and twos. Two darts in the sevens gives us the fours and nines. Four sevens gives us the eights and threes, and five sevens gives us the fives - which we already had. So specifically for 5 & 7, the largest unattainable score is 23.
In the general case, we are taking advantage of this fact:
( a + k ) mod a = k mod a
k mod a is just the remainder - the bit that's left over after the integer division k/a.
Put simply to hit any particular number, we simply figure out the remainder, throw darts to hit the lowest number with the same remainder, then throw darts into A until the desired score is achieved.
An important point comes up here. If our possible scores are A & B, these numbers must be relatively prime if we are going to do anything interesting. The proof goes like this. Let A = ak, B = bk, with k the largest common factor of A and B. Any score we can achieve can be expressed by
S = mA + nB
S = mak + nbk
S = (ma+nb)k
Now try to achieve Zk-1 for any Z
Zk-1 = (ma+nb)k
1 = (Z-ma+nb)k
The variables are all integers, so a solution is possible only if k=1. Therefore A and B are relatively prime.
Recognizing this contraint, we turn back to the main problem. AB mod A = 0; that remainder is achieved trivially. So the highest surviving remainder occurs at B(A-1). This score is achievable [A-1 darts into the B ring], but it is the lowest achievable result with this remainder. But if we subtract A, we don't change the remainder, so B(A-1)-A has the same remainder, but is smaller than the smallest achievable number with that remainder. So it must not be possible to score, and is thus our answer.
If we rearrange the terms, we can express this value as AB - (A+B); the solution is symmetric. It would be disturbing if the final solution did not have this property (my first "solution" wasn't symmetric, which was the big clue that I had screwed something up on the first attempt).
AB - (A+B) != mA + nB
June 22, 2003 11:53 AM
| TrackBack