?

Log in

No account? Create an account
Riddle: Dartboard difficulties - Baxil [bakh-HEEL'], n. My Sites [Tomorrowlands] [The TTU Wiki] [Photos]
View My LJ [By Tag]


July 11th, 2005
04:43 pm
[User Picture]

[Link]

Previous Entry Share Next Entry
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 2-40 or 3-60 by twos or threes, respectively. Therefore, the highest-scoring theoretically possible throw for a single round of darts is 180: 60 (triple-20) 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 single-dart score is a triple-19. The second-highest 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 knee-deep 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:, 8-1-2005: Answers unscreened.

Current Mood: creativemathematical
Tags:

(48 comments | Leave a comment)

Comments
 
Page 1 of 2
<<[1] [2] >>
[User Picture]
From:copperwolf
Date:July 12th, 2005 12:27 am (UTC)
(Link)
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. :)
[User Picture]
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.
[User Picture]
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 non-valid value is 50 + 50 + 3x21 = 163.

(I ran through that pretty quickly, so I may have made an error somewhere.)
[User Picture]
From:baxil
Date:July 13th, 2005 09:31 am (UTC)
(Link)
puropis, correct! Quite methodical, and congrats on the first right answer.
[User Picture]
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 inner-bullseye 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; 45-60-54, 45-60-60, or 45-54-54. 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.
[User Picture]
From:roaminrob
Date:July 12th, 2005 02:34 am (UTC)

Whoops.

(Link)
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.
[User Picture]
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. ;-)
[User Picture]
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...
[User Picture]
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.

Triple-bullseye-double gets all the numbers between 140 and 150 except 149. So 148 is the new limit.

Triple-triple-bullseye gets 149, 152, 155, 158, 161, 164, 167, 170. New limit is 150.

Triple-triple-double gets all even numbers up to 160, plus 151, 153, 155, 157. New limit is 153.

Triple-bullseye-bullseye gets 154, 157, 160. New limit is 155.

Triple-triple-triple gets 156, 159, 162, etc. This exhausts the combinations, and the first number not reached is 163. There you go.
[User Picture]
From:baxil
Date:July 13th, 2005 09:56 am (UTC)
(Link)
lhexa, that would be it!
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?
[User Picture]
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."
[User Picture]
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.
[User Picture]
From:packbat
Date:July 12th, 2005 02:06 pm (UTC)

Solution!

(Link)
0-60 can get. Just start with three misses and add one to any darts' score until you're done.
60-100 can get. First dart is 3x20, repeat above method with remaining two.
100-120 can get. First dart is 3x20, second 2x20, repeat above.
120-140 can get. First and second darts 3x20, repeat above.

Thus, 0-140 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, 0-160 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.
[User Picture]
From:baxil
Date:July 13th, 2005 10:07 am (UTC)

Re: Solution!

(Link)
packbat, right answer! The "provide solutions for all lesser numbers and show this one's not reachable" method has been justifiably popular, and you did a good job parceling them up elegantly.
[User Picture]
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?

[User Picture]
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 ...
[User Picture]
From:taral
Date:July 12th, 2005 09:17 pm (UTC)

The proof

(Link)

S = the union of {0..20}, {2x|x ∈ {0..20}}, {3x|x ∈ {0..20}}, {25, 50}.

Show that 163 is the smallest natural number not in the set S3 = {a + b + c|a ∈ S, b ∈ S, c ∈ S}.

We consider only natural numbers for this discourse.

First show that 163 is not in S3:

The largest numbers in S for each value mod 3:

  • 0: 60
  • 1: 40
  • 2: 50

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 S3.

Next, assume that X ≤ 163.

Case analysis mod 3:

  • If X ≤ 60, then X is in S3 because S includes {0..20}.
  • If X ≡ 0: X is in S3 because S includes {3x|x ∈ {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 S3. QED

[User Picture]
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, modulo-equals, and element-of 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.
[User Picture]
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 bloody-minded 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 bloody-minded grind of how I did it on request.
[User Picture]
From:baxil
Date:July 13th, 2005 10:27 am (UTC)
(Link)
I'd just like to say that the cube-root 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.)
[User Picture]
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 0-20. You can get 40 by throwing a double-20, and 60 by throwing a triple-triple. It's not hard to show that by combinations running from 0-0-0 = 0 to 60-60-20 = 140 you can cover all integers from 0 to 140. So all you have to worry about are 141-180.

I wrote the numbers 141-180 as a matrix and crossed off the values you'd get if you hit 60-60- and some double for the third throw; 60-60-some triple, 60-60-25 and 60-60-50 (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.
[User Picture]
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. Double-check your low ones, and remember that throwing a bulls-eye instead of a triple-20 gives you a few more scoring options!
[User Picture]
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;
}
[User Picture]
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 self-commenting code practices. Very good habit to maintain!

The answer, needless to say, is correct. Throw in an explanation of why those single-throw values are the only accessible ones and you'd have a formal proof (by exhaustion) on your hands.
[User Picture]
From:gelgisith
Date:July 13th, 2005 01:09 pm (UTC)
(Link)
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.
[User Picture]
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.
Tomorrowlands Powered by LiveJournal.com