Through a marksmanship contest, there are 4 strings of 4 glass balls hanging down from a horizontal post. Each bullet can only hit one glass ball at a time, so 16 shots need to be fired.

The only problem is if you shoot a glass ball that has a glass ball hanging below it (on the same string), it will fall off. So given the rule that you can't shoot a glass ball with a glass ball underneath it (and on the same string), how many ways can you shoot all the glass balls?

The obfuscation employed in the problem statement is masterful, but with enough thought one finally cuts through it to see that what we are doing is sucessively choosing in any order any of the strings that haven't yet been completely wiped out. This is the same as making up all possible strings of 16 characters chosen from an alphabet of 4 characters each of which is to be used exactly 4 times. This is a special case of the problem of strings made out of a multiset, and the count of all possible such strings is a multinomial coefficient. The answer in the particular case of the present problem is as given in the previous two comments.

Posted by Richard on 2004-01-31 01:09:24