Riddle: Dartboard difficulties  Baxil [bakhHEEL'], n.
[Recent Entries][Archive][Friends][Profile]
My Sites
[Tomorrowlands]
[The TTU Wiki]
[Photos]
View My LJ
[By Tag]
04:43 pm
[Link] 
Riddle: Dartboard difficulties
roaminrob, kadyg and I were playing darts last night on Rob's dart board. We played two games of 301, and he beat us both times by narrow margins; but my real fun was to begin after the play had finished. The topic turned somehow to scoring. In 301, a round of darts consists of three throws. Each throw can either score 0 (miss the board); any number from 1 to 20 (by landing it in the corresponding section of the board); 25 for an outer bullseye; or 50 for an inner bullseye. There are also Double and Triple rings on each of the numbered slivers that score from 240 or 360 by twos or threes, respectively. Therefore, the highestscoring theoretically possible throw for a single round of darts is 180: 60 (triple20) thrown three times. "So, Bax," Rob asked me. "Is it possible to score any number from 0 to 180 in a single round of darts?" I thought for a moment. "No. A trivial counterexample is 179. To get 180, you need three 3x20s. But the next highest singledart score is a triple19. The secondhighest round you can score is therefore two 3x20s and a 3x19, which is 177. You can't score 178 or 179." Rob looked thoughtful. " So, what's the lowest score that's impossible to get in a single round?" The two of us looked at each other. Mental wheels started spinning. Five minutes later, we were kneedeep in numbers, he'd grabbed a sheet of paper, and I was assuring Kady that, no, really, we were close, we'd have the answer in a few minutes, we could start heading home soon. (Like a true mathematician, I had told him, "Let's just find the answer first. That'll help us come up with the elegant method for deriving it." Indeed, that took the better part of an evening.) Anyway, Kady only got home about five minutes late, and we've got our answer. Can you find it? Extra bonus points for a proof showing why it's the smallest (and roaminrob, you're eligible here too  I'd like to see you develop your idea from the phone message more, because it's different from the one I settled on). n.b.: I'm also going to go ahead and unscreen the answers to the previous riddle now, for those of you who haven't gotten it yet. Answers here will be screened for, um, probably a few days, or until I post the next riddle, whichever comes first.) Edit:, 812005: Answers unscreened.
Current Mood: mathematical Tags: riddles

 
 I'm not enough of a math nerd to want to attempt this puzzle, only enough to enjoy thinking about it. I just want to say that I would have had an easier time with the last riddle if you'd picked a band & a song that I had heard of. :)  From:  baxil 
Date:  July 12th, 2005 02:01 am (UTC) 

   (Link) 

I was afraid that people would cheat and solve the riddle by finding the song. I guess I shouldn't have worried. ;)
Really, though, the song wasn't my choice. Except insofar as I apparently have obscure tastes.  From:  puropis 
Date:  July 12th, 2005 02:15 am (UTC) 

   (Link) 

163.
For 0 <= n <= 20, the following ranges are valid and yield values 0 to 140: n 20 + n 2x20 + n 3x20 + n 3x20 + 20 + n 3x20 + 2x20 + n 3x20 + 3x20 + n
All values above 140 fall in one of the following three categories: 50 + 50 + 50 50 + 50 + 3n  maximum of 160 50 + 60 + 3n  maximum of 170 60 + 60 + 3n  maximum of 180
The last three above categories cover all values up to 160. Thus, the smallest nonvalid value is 50 + 50 + 3x21 = 163.
(I ran through that pretty quickly, so I may have made an error somewhere.)  From:  roaminrob 
Date:  July 12th, 2005 02:26 am (UTC) 

  The proof is in 163's pudding.  (Link) 

OK. First off, when I left the phone message last night, I'd forgotten about the innerbullseye for 50 points. It still works out, though. When you left, I was able to dimly understand the proof you came up with, but it didn't appeal to my sense of aesthetics. ;)
Here's the deal: since 163 is a fairly high number, you can eliminate most of the numbers from the board as possible portions of the score. For example, you can't throw a 20, and then get a 163.
In fact, the only numbers you can use to get in the neighborhood of 163 are the high triples, and the bullseye: 45, 48, 50, 51, 54, 57, and 60. (Because a 60, 60, and 45 gets you 165.)
Then, 163 has to be constructed using any three of those numbers. Being an odd number, that means we only have two plausible combinations: three odd integers, or two even integers and an odd integer.
Ruling out three odd integers is trivial: we only have 45, 51, and 57 to work with, and that doesn't even come close.
Next we can easily rule out 45 as a possible member integer (because there are only three close possibilities that include throwing a 45; 456054, 456060, or 455454. Everything else scores way too low.)
That just leaves checking a few combinations using 51 and 57. I don't need to spell those out here; by now you're probably already way ahead of me, having ruled out all of the possible combinations.
Coming up with a more elegant way to derive the solution is turning out to be a very interesting problem, though. I worked on it for a good couple of hours after you left, and it's been churning in the back of my brain ever since. The best I've been able to come up with is that I can't seem to base any part of the solution on numbers which can't be thrown  i.e., I can't seem to reduce the problem, which is infuriating. I jumped the gun a bit. What I gave isn't in any way a proof that 163 is the smallest, rather, it just shows that 163 can't be thrown.
I haven't been able to come up with a proof that 163 is the smallest; that falls under the "more elegant solution" part of the puzzle.  From:  baxil 
Date:  July 13th, 2005 09:44 am (UTC) 

  Re: Whoops.  (Link) 

roaminrob: I haven't been able to come up with a proof that () is the smallest; that falls under the "more elegant solution" part of the puzzle. All of the more elegant proofs I've been given involve classes of numbers. If you sort numbers into sets by their properties, you can show that a given set is reachable or not reachable based on those properties. For example, if you throw all three darts into the double rings, you know that your score will always be divisible by two. (This is the same as saying that your score mod 2 is equal to 0. There's only one other possibility  your score mod 2 can be equal to 1, meaning it's divisible by 2 with 1 left over.) Can you use this to show, for example, whether all numbers divisible by 2 (up to a point, anyway) can be thrown? Can you attack the other modulo set in similar ways? Would using other numbers as your modulo base make it easier or harder to say things about the sets in question? n.b.: For those who haven't gotten the answer yet, this is a pretty significant hint; but probably will help you much more with the proof than the answer itself. ;)  From:  amthrax 
Date:  July 12th, 2005 06:14 am (UTC) 

   (Link) 

Ooh. Alright, you've managed to drag me out of lurkage.
163 (if I understand the rules correctly). I have to admit, I don't have a good proof for this yet; though, I do have an O(n log n) algorithm for it.
The scene you described reminds me of how much I miss MIT...  From:  baxil 
Date:  July 13th, 2005 09:52 am (UTC) 

   (Link) 

Correct answer, amthrax! Technically, your algorithm itself would be a proof  if it iterates over all scoring possibilities, you've shown by exhaustion that the answer is inachievable and all others smaller are achievable. It may not have the elegance of a mathematical proof, perhaps, but it also has the virtue of making the computer do all the gruntwork. ;) The scene you described reminds me of how much I miss MIT... I'm lucky to have good friends. Would you believe I'm about seven years out of college and half a state away from my alma mater? Also, good to meet you! From:  lhexa 
Date:  July 12th, 2005 08:33 am (UTC) 

   (Link) 

Everything up to 140 can come from two triples and a single, or two misses and a single.
Triplebullseyedouble gets all the numbers between 140 and 150 except 149. So 148 is the new limit.
Tripletriplebullseye gets 149, 152, 155, 158, 161, 164, 167, 170. New limit is 150.
Tripletripledouble gets all even numbers up to 160, plus 151, 153, 155, 157. New limit is 153.
Triplebullseyebullseye gets 154, 157, 160. New limit is 155.
Tripletripletriple gets 156, 159, 162, etc. This exhausts the combinations, and the first number not reached is 163. There you go.  From:  baxil 
Date:  July 13th, 2005 09:56 am (UTC) 

   (Link) 

From:  lhexa 
Date:  July 12th, 2005 08:59 am (UTC) 

   (Link) 

Now, what do these numbers mean to you: 143, 121, 107, 101, 96, 71, 61?  From:  baxil 
Date:  July 13th, 2005 09:17 am (UTC) 

   (Link) 

I have guesses for perhaps about four of those; I'll offer them separately, but I also wanted to open up the floor here to other potential respondents. :) From:  (Anonymous) 
Date:  July 12th, 2005 09:29 am (UTC) 

   (Link) 

163 166 169 172 173 175 176 178 179
Aren't computers wonderful things? That should be all the scores one cannot get in one round.
 "Yesterday upon the stair I met a man who wasn't there."  From:  baxil 
Date:  July 13th, 2005 10:02 am (UTC) 

   (Link) 

Anon3ymous, yes, computers are quite wonderful things. ;) I've had a few "proof by computational power" entries.
You are, of course, correct in your answer.  From:  packbat 
Date:  July 12th, 2005 02:06 pm (UTC) 

  Solution!  (Link) 

060 can get. Just start with three misses and add one to any darts' score until you're done. 60100 can get. First dart is 3x20, repeat above method with remaining two. 100120 can get. First dart is 3x20, second 2x20, repeat above. 120140 can get. First and second darts 3x20, repeat above.
Thus, 0140 can get.
Through similar logic, all multiples of 3 from 120 to 180 can get, and all multiples of 2 from 120 to 160 can get. 117 (60=3x20 + 57=3x19) + any multiple of 2 up to 157 can also get.
Therefore, all even numbers and all odd numbers between 120 and 158 can get. 159 = multiple of 3 (3x20, 3x20, 3x13 would satisfy), can get.
Thus, 0160 can get.
Two triples + 50 (bullseye): 170 down to 110, thus... 110 + any multiple of three up to 170 can get.
Two triples + 25 (outer bullseye): 145 maximum, already accounted for.

Up to 160 was accounted for above. Beyond 160, the only possible scores are: 1) Three triples  i.e. 120 + 3n for n = 0 to 20  or 2) Two triples and an inner bullseye  i.e. 110 + 3n for n = 0 to 20.
Thus, 161 = 120 + 41 (fails case 1) = 110 + 51 (passes case 2: n = 17). 162 = 120 + 42 (passes case 1: n = 14) 163 = 120 + 43 (fails case 1) = 110 + 53 (fails case 2).
...and 163 is the smallest impossible score. Q.E.D.  From:  necama 
Date:  July 12th, 2005 07:28 pm (UTC) 

  here you go:  (Link) 

The smallest number you can't throw is obviously bigger than 120: a triple 20 gets you 60, and you can get any number up to 60 as the sum of two darts.
Now, using two darts, here's the numbers near 120 you can get: 120, 117, 114, 111, 110, 108, 105, 102, 100...
So, our candidate numbers will have to be bigger than 120 + Z, where Z is an integer bigger than 20, and not divisible by 2 or 3. A short list: Z is in {23, 25, 29, 31, 35, 37, 41, 43, 47 ...}
So, we try each in order:
143: 105 + 19x2. Not it. 145: 105 + 20x2. Not it. 149: 111 + 19x2. Not it. 151: 111 + 20x2. Not it. 155: 117 + 19x2. Not it. 157: 117 + 20x2. Not it. 161: 110 + 17x3. Not it. (and an anomaly. Does not fit previous pattern because of the bullseye.) 163: Not attainable.
So, if you don't allow bullseyes, pattern analysis tells you that 161 is not attainable. With bullseyes, you have to go to 163.
So do I get a cookie?
 From:  baxil 
Date:  July 13th, 2005 10:11 am (UTC) 

  Re: here you go:  (Link) 

necama, yeah, accounting for those bullseyes does throw an extra twist into the mix ... Correct, of course. So do I get a cookie? Sure! I'll set one aside for you here at the house. Feel like a visit to the Sierra? We all might be doing some hiking on the last weekend of July ...  From:  taral 
Date:  July 12th, 2005 09:17 pm (UTC) 

  The proof  (Link) 

S = the union of {0..20}, {2xx ∈ {0..20}}, {3xx ∈ {0..20}}, {25, 50}.
Show that 163 is the smallest natural number not in the set S^{3} = {a + b + ca ∈ S, b ∈ S, c ∈ S}.
We consider only natural numbers for this discourse.
First show that 163 is not in S^{3}:
The largest numbers in S for each value mod 3:
Observe that 163 ≡ 1 mod 3. There are three ways of achieving this value with a sum of 3 numbers:
 (0, 0, 1): The largest such number is 60 + 60 + 40 = 160.
 (0, 2, 2): The largest such number is 60 + 50 + 50 = 150.
 (1, 1, 2): The largest such number is 40 + 40 + 50 = 130.
Therefore 163 is not in S ^{3}.
Next, assume that X ≤ 163.
Case analysis mod 3:
 If X ≤ 60, then X is in S^{3} because S includes {0..20}.
 If X ≡ 0: X is in S^{3} because S includes {3xx ∈ {0..20}}.
 If X ≡ 1 ∧ 40 ≤ X ≤ 160 = 60+60+40: ∃a,b  a,b ∈ S ∧ a,b ≡ 0 ∧ X = a + b + 40.
 If X ≡ 2 ∧ 50 ≤ X ≤ 170 = 60+60+50: ∃a,b  a,b ∈ S ∧ a,b ≡ 0 ∧ X = a + b + 50.
Therefore 163 is the smallest number not in S^{3}. QED  From:  baxil 
Date:  July 13th, 2005 10:18 am (UTC) 

  Re: The proof  (Link) 

taral, you get bonus points for having a proof that looks like it could be planted straight into a mathematics textbook. You're going to have to tell me how to get <=, And, Exists, moduloequals, and elementof out of HTML codes. I'm sorely tempted to just unscreen this now and let people marvel, but I want to give folks a little more time to solve it.  From:  hafoc 
Date:  July 12th, 2005 09:45 pm (UTC) 

   (Link) 

I'm not a math geek, but I tried to find an answer. I have one. How can I give it, and see if I'm right, without spoiling the riddle for everyone else?
In fact, I was bloodyminded enough that I think I found all possible answers.
Let's see: Anybody should be able to solve this if they want but it will hide it from those who don't want to see it. Cube root of 2924207.
Description of bloodyminded grind of how I did it on request.  From:  baxil 
Date:  July 13th, 2005 10:27 am (UTC) 

   (Link) 

I'd just like to say that the cuberoot idea is a really excellent one. I'll have to remember that one for answering riddles where comments aren't screened.
(I'll leave this unscreened since solving the cube root won't help others.)  From:  hafoc 
Date:  July 13th, 2005 01:10 am (UTC) 

   (Link) 

(sigh) I'm being Dum. You're not posting these until you get answers, are you?
The answer I get is 143. The other scores you can't get should be 149, 151, 157, 161, 163, 164, 166, 167, 169, 172, 173, 176, 178, and 179.
I don't remember how to do a mathematical proof. However, it's pretty easy to eliminate values from consideration.
Any throw can be 020. You can get 40 by throwing a double20, and 60 by throwing a tripletriple. It's not hard to show that by combinations running from 000 = 0 to 606020 = 140 you can cover all integers from 0 to 140. So all you have to worry about are 141180.
I wrote the numbers 141180 as a matrix and crossed off the values you'd get if you hit 6060 and some double for the third throw; 6060some triple, 606025 and 606050 (bullseye). Crossing these values off the matrix gave me my list of "unreachable" numbers.
Of course, I'm not really sure I understand how you score this game.  From:  baxil 
Date:  July 13th, 2005 10:22 am (UTC) 

   (Link) 

hafoc: Writing down the matrix and crossing off achievable values is exactly how roaminrob and I did it, so you're in good company. :) You've got the answer. You also have a few extra answers in your list. Doublecheck your low ones, and remember that throwing a bullseye instead of a triple20 gives you a few more scoring options!  From:  chipuni 
Date:  July 13th, 2005 03:28 am (UTC) 

   (Link) 

When in doubt, use heavy computing power. The answer is 163. The numbers that can't be reached are: 163 166 169 172 173 175 176 178 179 #include < iostream > const int POSSIBLE_SINGLE_SCORES = 44; const int POSSIBLE_TRIPLE_SCORES = 180; int main (int argc, char * const argv[]) { bool arboMissed[POSSIBLE_TRIPLE_SCORES]; int arinSingleScores[POSSIBLE_SINGLE_SCORES] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 36, 38, 39, 40, 42, 45, 48, 50, 51, 54, 57, 60}; int score; int throw1, throw2, throw3; // Initialize all variables for (score = 0; score < POSSIBLE_TRIPLE_SCORES; score++) { arboMissed[score] = true; } // Make all possible throws. for (throw1 = 0; throw1 < POSSIBLE_SINGLE_SCORES; throw1++) { for (throw2 = 0; throw2 < POSSIBLE_SINGLE_SCORES; throw2++) { for (throw3 = 0; throw3 < POSSIBLE_SINGLE_SCORES; throw3++) { arboMissed[arinSingleScores[throw1] + arinSingleScores[throw2] + arinSingleScores[throw3]] = false; } } } // Print what wasn't hit. for (score = 0; score < POSSIBLE_TRIPLE_SCORES; score++) { if (arboMissed[score]) { std::cout << score << std::endl; } }
return 0; }
 From:  baxil 
Date:  July 13th, 2005 10:33 am (UTC) 

   (Link) 

chipuni, extra bonus points for posting source code to my journal. ;D I see you follow selfcommenting code practices. Very good habit to maintain! The answer, needless to say, is correct. Throw in an explanation of why those singlethrow values are the only accessible ones and you'd have a formal proof (by exhaustion) on your hands. Like others, i have employed the usefull aid of a computer to solve this riddle. Because of your wording in a single round, rather than with three darts, i presume a zero throw is a valid outcome for any dart. (If it isn't, the answer is, of course, simply 0 (or barring that, 1), because then each dart will score at least 1, with a minimum total of 3.) Here's the source (in QBasic):
DIM score$(180): FOR t=1 to 180: score$(t)="N": NEXT t: REM list of scores FOR dart1=0 TO 20: FOR dart2=0 TO 20: FOR dart3=0 TO 20: REM dart counters FOR m1=1 TO 3: FOR m2=1 TO 3: FOR m3=1 TO 3: REM multiplication counters score=dart1*m1+dart2*m2+dart3*m3: score$(score)="Y": REM calculate scores & change score in list to "yes" NEXT m3, m2, m1, dart3, dart2, dart1 * (see below) FOR t=0 TO 180: IF score$(t)="N" THEN PRINT t,: REM check scores list, and print if "no" NEXT t
This first run spewed out 13 numbers (less than i had expected), the lowest of which was 161. Of course, i knew i wasn't there yet; there's also the bullseye to take into account, so i added the following lines at the *:
FOR dart1=0 TO 20: FOR dart2=0 TO 20: dart3=25: REM dart counters, dart3 fixed at bullseye FOR m1=1 TO 3: FOR m2=1 TO 3: FOR m3=1 TO 2: REM multiplication counters score=dart1*m1+dart2*m2+dart3*m3: score$(score)="Y": REM calculate scores & change score in list to "yes" NEXT m3, m2, m1, dart2, dart1
This time, there were nine numbers, with 163 the lowest.
I realised later that i had forgotten to add the possibility of two darts hitting bullseye, but it doesn't really matter, since the highest score one can get with that is below 163.  From:  baxil 
Date:  July 13th, 2005 10:18 pm (UTC) 

   (Link) 

gelgisith, right answer! (And, yes, your assumption that a zero score for a dart is legal is correct  actually, I think I specified that in the problem terms.) Ah, QBasic. I miss it, I really do. :) I used to program in it in high school. Used to be included free with Windows; these days I'm not even sure you can find it any more. 
