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
re: Solution by Nosher)
Nosher, I think the problem is probably mine, not yours. I hurriedly wrote up my solution before heading to class, and the method of proof is a classic one - people who've heard it before recognize it instantly but it certainly needs a clearer explanation for people who haven't heard it before. So here goes:
Think of the 10 points scored as 10 balls. Think of each shot as a bin. You have 10 bins - one for each arrow shot - and the bins are arranged in order, corresponding to the first shot, the second shot, etc.
The problem is then to find the total number of ways to put these 10 identical balls into the 10 distinct bins. Now, think of the 10 balls as lying in a row - you are now going to place dividers between the balls, and the regions between consecutive dividers will represent the bins. Since there are 10 bins to be formed, you need to place 9 dividers.
The classic trick is then to show the following equivalence:
(# of ways to put n identical balls into k distinct bins, where some bins may be empty) = (# of ways to put (n+k) identical balls into k distinct bins, where each bin must have at least one ball)
To see why they are equivalent, note that in any configuration with n identical balls in k distinct bins, you can add one more ball in each bin (k additional balls) to get a configuration with (n+k) identical balls in each bin, with at least one ball in each bin. Conversely, if you have (n+k) identical balls in each bin, with at least one ball in each bin, you can remove one ball from each bin to get the former type.
You just need to compute the number of ways to put (n+k) identical balls in k distinct bins, then, where each bin has at least one ball. In our particular problem, this is 20 balls, 10 bins. To solve this version, note that each of the 9 dividers that form the walls of the bins need to go between two balls, and that there cannot be more than one divider between two balls (since the corresponding bin would then be empty). There are 19 spaces between the balls, so to put 10 dividers in them, the answer is 19 choose 10, which again, can be computed by searching "19 choose 10" on Google.com (I think that is so cool!).
Hope that helps.
Clearer Explanation
