Dartboard Question

[davar55]

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?

[michaf]

How many darts are you allowed to throw?

[davar55]

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

[R.D. Silverman]

Originally Posted by davar55

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?

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.

[lavalamp]

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.

[R.D. Silverman]

Originally Posted by lavalamp

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.

SAP = Symbolic Algebra Package/Program

[retina]

For N=100 I get: partitions=258949

[retina]

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

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

[lavalamp]

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

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 75,097,688.

[retina]

Originally Posted by lavalamp

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 75,097,688.

You need a better algorithm. It is a trivial Q actually. I ran all sums up to 1072 in <1 second. Think about using divide and conquer methods similar to FFT

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

[davieddy]

Originally Posted by retina

You need a better algorithm. It is a trivial Q actually. I ran all sums up to 1072 in <1 second. Think about using divide and conquer methods similar to FFT

Yes I think I can see what you mean.
David