Dartboard Question
 

A dartboard contains regions with point values in the following list:

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

Suppose you want to reach exactly N=100 points, and
that each dart toss must hit a different valued region.
How many different ways are there of doing this?
In other words, how many partitions of N=100 into sums
of numbers in the above list without repetition are there?

For what value of N does this function peak?

How many darts are you allowed to throw?

You can throw any number up to the number (43) of
different valued regions.

[QUOTE=davar55;125160]A dartboard contains regions with point values in the following list:

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

Suppose you want to reach exactly N=100 points, and
that each dart toss must hit a different valued region.
How many different ways are there of doing this?
In other words, how many partitions of N=100 into sums
of numbers in the above list without repetition are there?

For what value of N does this function peak?[/QUOTE]

Compute the coefficient of x^100 in the generating function
1/[(1-x)(2-x)(3-x)(4-x)............(60-x)]

I would not want to do this by hand. Use a SAP.

248990?

I'm a little unsure of whether SAP is an accronym that stands for something, or a derogatory term for someone who will actually spend their time calculating the answer. I certainly hope it isn't the latter.

I whipped up some PARI code to work this out, but only went up to 13 darts, because the 14th triangular number is over 100. My code takes 20 seconds to come to that answer.

[QUOTE=lavalamp;125174]248990?

I'm a little unsure of whether SAP is an accronym that stands for something, or a derogatory term for someone who will actually spend their time calculating the answer. I certainly hope it isn't the latter.

I whipped up some PARI code to work this out, but only went up to 13 darts, because the 14th triangular number is over 100. My code takes 20 seconds to come to that answer.[/QUOTE]

SAP = Symbolic Algebra Package/Program

For N=100 I get: partitions=[spoiler]258949[/spoiler]

Oops, I just saw the second part of the post.

[spoiler]Since the maximal total is 1072, the function should peak at half, N=536 with partitions=35458209440[/spoiler].

Ah, somehow I'd missed out number 39 from my list of possible numbers, I also now get [SPOILER]258,949[/SPOILER].

As a possible expansion to this problem then, what if the limitation is just a max of one dart per area rather than a max of one dart per score. For example, it's possible to score 6 in three different ways, single 6, double 3, triple 2.

Also, or perhaps instead, what if it was extended to include quadruple and quintuple numbers on the (presumably very large) board.

A third expansion might be a board with more or fewer numbers on it.

Edit: I decided I'd run some code to count all combinations for n=100 with the first expansion (one dart per area, rather than one per score). The code took a _lot_ longer to run (80 minutes up from 20 seconds), and it counted [SPOILER]75,097,688[/SPOILER].

[QUOTE=lavalamp;125241]Edit: I decided I'd run some code to count all combinations for n=100 with the first expansion (one dart per area, rather than one per score). The code took a _lot_ longer to run (80 minutes up from 20 seconds), and it counted [SPOILER]75,097,688[/SPOILER].[/QUOTE]You need a better algorithm. It is a trivial Q actually. I ran all sums up to 1072 in <1 second. Think about using [spoiler]divide and conquer methods similar to FFT[/spoiler]

[edit]For all area scores (62 areas will bullseye) I get [spoiler]82339371[/spoiler] for N=100[/edit]

[quote=retina;125243]You need a better algorithm. It is a trivial Q actually. I ran all sums up to 1072 in <1 second. Think about using [spoiler]divide and conquer methods similar to FFT[/spoiler]

[/quote]

Yes I think I can see what you mean.
David

I'd made a couple of mistakes (I'd specifically tuned my code for the previous set of scores and hadn't re-tuned it for these, so it missed some combos), also somehow I missed out the second 24. Also I stopped at 14 darts instead of running to 17.

So yeah, NOW I also get [SPOILER]82339371[/SPOILER].

Unfortunately I have no idea how FFTs work, so I don't know what specific methods you're refering to. However, I will read around and have a think as to how I could speed up my code (this last run 93 mins :shock:).

Somewhat optimized results: :whistle:

[code]
kossy@leela:~/darts2> time ./darts2
Value for N=100 is [spoiler]82339371.[/spoiler]
Peak at [spoiler]N=667: 17496397018818748.
Peak at N=668: 17496397018818748.
[/spoiler]
real 0m0.002s
user 0m0.001s
sys 0m0.001s
kossy@leela:~/darts2>
[/code]Code might run faster with mprime stopped, but ... nah. :geek:

Where did the 1072 come from, again? :unsure:

[QUOTE=ckdo;125358]Value for N=100 is [spoiler]82339371.[/spoiler]
Peak at [spoiler]N=667: 17496397018818748.
Peak at N=668: 17496397018818748.
[/spoiler][/QUOTE]Yes, I concur with that.[QUOTE=ckdo;125358]Where did the 1072 come from, again? :unsure:[/QUOTE]1072 was for the original problem with 43 unique targets. Your answer is for 62 unique targets with maximal sum of 1335, hence the peaks at floor[1335/2] and ceil[1335/2].

[quote=retina;125243]You need a better algorithm. It is a trivial Q actually. I ran all sums up to 1072 in <1 second. Think about using [spoiler]divide and conquer methods similar to FFT[/spoiler]

[edit]For all area scores (62 areas will bullseye) I get [spoiler]82339371[/spoiler] for N=100[/edit][/quote]

Ah, yes. It escaped me that the 1072 was in the unedited part of the message and I didn't conclude you were talking about the original problem. :blush:

[QUOTE=retina;125243][edit]For all area scores (62 areas will bullseye) I get [spoiler]82339371[/spoiler] for N=100[/edit][/QUOTE]Oops, that should be ... (62 areas [b]with[/b] bullseye) ... :blush:

[quote=R.D. Silverman;125172]Compute the coefficient of x^100 in the generating function
1/[(1-x)(2-x)(3-x)(4-x)............(60-x)][/quote]

Is this the right generating function?
Shouldn't it be the coefficient of x^100 in
(1+x)(1+x^2)(1+x^3)(1+x^4).....(1+x^57)(1+x^60) [43 terms]?

And then if we want to allow for one dart per area,
just raise the appropriate term to the power = #areas with that value,
e.g. (1+x^6)^3 because 6 is the value of three areas.
(Which yields 62 terms.)

I think Davar is right.

If you wanted up to three terms, I believe the term would be

(1 + x^6 + x^12 + x^18) rather than (1+x^6)^3

An interesting link, slightly related

[url]http://www.maa.org/mathland/mathland_5_19.html[/url]

I'm still intrigued by Davar's choice of 43 numbers.

[quote=davieddy;125738]I'm still intrigued by Davar's choice of 43 numbers.[/quote]

Intrigued by something other than the fact they are a list of all possible point values one can score by throwing one dart?

Doh:blush:
[quote=bsquared;125739]Intrigued by something other than the fact they are a list of all possible point values one can score by throwing one dart?[/quote]

I also appreciate Retina's symmetry argument:
put a dart in each region, and count the number of ways
of removing them to reduce the total to the required number.
He was relying on statistics to guess that the maximum wasn't
located in twin peaks equidistant from the middle.

David

[QUOTE=davieddy;125754]He was relying on statistics to guess that the maximum wasn't
located in twin peaks equidistant from the middle.[/QUOTE]Yeah I was, it is quite a safe bet with the distribution given, and also the fact that I could easily verify the fact by examining the output of the coefficient list.