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.)
(In reply to
Clearer Explanation by David Shin)
I still don't quite understand David's solution, even with your longer explanation. I am not asking you to try again – I think I just need a little more time to absorb it.
However, your solution kind of made me think of this. What if you had 10 balls in a row, and they represented the total number of points to be scored. Next, you place the dividers anywhere (I'll describe how many in a moment).
You could put them in between two balls. You could put two or more dividers between two balls, making an empty bin that just represents a missed arrow between two shots. You could put some dividers outside of the row of balls completely, making empty bins before or after some shots.
Using this representation, how should I place the bins, and how many bins can I place, that will represent making 10 shots? Here's an example of what I mean.  represents a divider, O represents a ball.
    O OOOOOOOOO  
So this would represent a miss, miss, miss, miss, 1, miss, 3, 6, miss, miss. Notice there are 11 dividers, and there are basically 11 locations that the dividers are allowed to go in (with repeats): before ball 1, between ball 1 and ball 2, …, between ball 9 and ball 10, after ball 10.
Hmmm, but what if I move the last 3 dividers to the beginning, so that I have:
       O OOOOOOOOO
Oops! I just made 11 bins, which is like making 11 shots when I only have 10 arrows. Ok, so I have a little bit of a restriction with these dividers. Maybe I can't allow open bins. See how the last bin of 6 is open? Maybe two of my dividers must be right after and right before the balls, but I can choose where the other 9 go. Almost like I start out with OOOOOOOOOO and place 9 more dividers.
Ok, that could work. Remember, I am allowed "repeats" meaning I am allowed to place a divider between ball n and ball n+1 even if there is already a divider there, for example.
How would that representation get interpreted into a formula? I think the representation is more intuitive, but the step to the formula is not.
Well, this is like "with replacement" in permutations or combinations since you can choose the same spots more than once. The order in which you place the dividers doesn't matter, that doesn't produce a unique solution. So that would make this a combination problem, not a permutation problem. So is that like 11 choose 9 combinations with replacement? What is that? (11+91)!/[9!*(111)!] = 19!/(9!*10!) = 92378. Woah! That worked! I totally wasn't expecting that!
Sorry for the stream of consciousness, but that's how I thought about the problem. That was fun! Thanks, David, I totally wouldn't have even started thinking about this kind of solution without your "20" divider solution.
Side note: I didn't write a program like Nosher did, but I did try another way of finding the answer (much more complicated) and got the same answer of 92378, so I have another approach that further boosts our confidence that we were all correct. I'll post that in more detail.
(edit: fixed a confusing sentence that I didn't finish the first time)
Edited on September 23, 2004, 3:19 pm

Posted by nikki
on 20040923 15:06:28 