Someone shot 10 arrows at a target with 10 concentric rings, each being worth a different integer number of points from 1 to 10. How many different ways are there of scoring 10 points by doing this? (Note that not all the arrows have to hit the target and that order matters; 6 first then 4 is different from 4 first then 6. Also note that two or more arrows may hit the same ring.)

My original solution was not nearly so direct or elegant. Though I have a rather brute-forcey type beginning, the rest finds a logical formula.

There are 42 different ways to get 10 points, but this is not taking the order into account. I didn’t find a formula for this (did someone else?) – it was very hard for me to think about a way to find a formula for picking from the integers 0-10 and stopping when their sum was 10. So I just found them. Without listing the arrows that missed the target completely, here’s what I found (I hope this is readable):

1 is max: 1 way (10 1s)
2 is max: 5 ways (2, 8 1s) (2 2s, 6 1s) (3 2s, 4 1s) (4 2s, 2 1s) (5 2s)
3 is max: 8 ways (3, 7 1s) (3, 2, 5 1s) (3, 2 2s, 3 1s) (3, 3 2s, 1) (2 3s, 4 1s) (2 3s, 2, 2 1s) (2 3s, 2 2s) (3 3s, 1)
4 is max: 9 ways (4, 6 1s) (4, 2, 4 1s) (4, 2 2s, 2 1s) (4, 3 2s ) (4, 3, 3 1s) (4, 3, 2, 1) (4, 2 3s) (2 4s, 2 1s) (2 4s, 2)
5 is max: 7 ways (5, 5 1s) (5, 2, 3 1s) (5, 2 2s, 1) (5, 3, 2 1s) (5, 3, 2) (5, 4, 1) (2 5s)
6 is max: 5 ways (6, 4 1s) (6, 2, 2 1s) (6, 2 2s) (6, 3, 1) (6, 4)
7 is max: 3 ways (7, 3 1s) (7, 2, 1) (7, 3)
8 is max: 2 ways (8, 2 1s) (8, 2)
9 is max: 1 way (9, 1)
10 is max: 1 way (10)

Ok, then what you do is for each of the 42 groups you say "how many non-zero integers are there?" not caring about repeats yet, and call that number r. So for example, 8,1,1,0,0,0,0,0,0,0 has 3 non-zero integers. Let’s find 10 choose 3 permutations without replacement. What this does is finds "how many different ways can I put three items into 10 different spots?" The answer is 10!/(10-r)!.

Next, if there are any repeated integers, we have to account for solutions that are multi-counted. Why? In my example, let’s call the non-zero integers 8, 1a and 1b. I could have 8, 1a, 1b, 0,0,0,0,0,0,0 and also 8 1b, 1a, 0,0,0,0,0,0,0. These two solutions would be counted separately in my 10!/(10-r)! equation, so 8,1,1,0,0,0,0,0,0,0 would be double counted.

So how do we know what to divide by? Well let’s say that integer x is repeated a times. Cataloging the integers like x1, x2, x3, …, xa, the number of permutations of the order is simply a!. If we have one integer that is repeated a times, we divide 10!/(10-r)! by a!. What if there is more than one integer that is repeated? So let’s say we have x repeated a times, y repeated b times, z repeated c times… then we would divide by (a!*b!*c!*…and so on). For example, 3,3,2,1,1,0,0,0,0,0 has r=5, a=2, b=2. So the answer is 10! / (10-r)! / (a!*b!) = 10! / (10-5)! / (2! * 2!) = 10! / 5! / 4 = 7560.

So, using the 10!/(10-r)!/(a!*b!…) formula for each group, and then summing the results, you get 92378 ways of scoring 10 points, just like David and Nosher found.

Posted by nikki on 2004-09-23 15:08:46