You have six coffee cups labeled one through six and four identical ping pong balls. How many different ways can you put the balls into the cups if you can put up to four balls in a cup (switching balls is still the same "way")? The problem is simple if you can have only one ball in a cup. It's "six choose four". 6C4. (6 x 5 x 4 x 3)/ (1 x 2 x 3 x 4). If you are not familiar with this formula, you need to get my new short book tentatively titled Probability For Twelve Year Olds (And Maybe You) available soon. The answer to that question is fifteen. But if you can put multiple balls in the cup it seems the problem gets a lot harder.
One way to do it is to count up five different categories. The balls are separated. One cup has three balls and one cup has one ball. Two cups have two balls each. Two cups have one ball each and one contains two balls. One cup holds all four balls. The first scenario can occur, as we just calculated, in fifteen ways. If the balls are in separated 3-1, you have six choices for the three and then five choices for the one. That is thirty more ways. Two balls in two different cups is 6 choose 2 which is another fifteen ways. A 2-1-1 distribution gives us six ways to choose a cup for the two balls coupled with 5C2 ways to arrange the other two balls singly. 6 x 10 or 60. Finally there are six ways to cram four balls in one cup. Altogether that's 15 + 30 + 15 + 60 +6. 126 is the answer to the question.
Is there an easier way to do problems like these? Yep. And that's a good thing because as the number of coffee cups and ping pong balls increase, the above method becomes more and more time consuming. To avoid that problem, we will dig holes, in this case ten, lined up in a row that are big enough to hold either a coffee cup or a ping pong ball. In the far left hole, you insert cup #1. From the remaining nine holes you choose five in which to put one cup, making sure that the numbers on the cup increase from left to right. The ping pong balls go in the remaining holes. So you will have something like C1 C2 b C3 b b C4 C5 C6 b. Or C1 C2 C3 b b b C4 b C5 C6. Or you can choose where to put the four ping pong balls and put the numerically ordered cups in the remaining holes.
In this problem, there will be nine holes from which to choose where the four balls go. 9C4. The cups go in the other holes with the leftmost hole containing C1 and the other cups in numerical order left to right. What you do next is this: take every ping pong ball and put it in the cup on its left. If there is a ball on its left then keep moving left until you get to a cup to put it in. In the first example above, there will be one ball in C2, two balls in C3 and one ball in C6. In the second example there would be three balls in C3 and one ball in C4.
And here is the thing. If you use this technique, any setup can be duplicated. Or vice versa. Any way you put balls in cups can be duplicated via this technique with ten holes (where nine are awaiting assignment). Since there are 9C4 arrangements of the four balls in these nine holes we merely evaluate that expression to get our answer. (9 x 8 x 7 x 6)/ (1 x 2 x 3 x 4). 126. Once again.
With a little thought, you should see how this technique can be generalized. If you need to put x indistinguishable balls into y distinguishable coffee cups and can put as many balls as you feel like into any cup, the number of ways to do that is exactly the same as if those x balls were restricted to no more than one ball in a cup but the number of cups was increased to the original number of cups plus the number of of balls, minus one.
The second problem can most easily be illustrated with a (38 slat) roulette wheel and its roulette ball. A ball is slathered with paint. It has so much paint that when it falls or is put into a slat it leaves some paint in it during the life of this question. As the ball tours the wheel, you will know where it has been. Sometimes more than once.
But this roulette ball does not travel the wheel in the normal way. Rather it starts off at double zero and moves one direction or the other one slat at a time. Which direction it moves depends on a coin flip. You keep flipping that coin and every time you get a head (which we assume is a 50% shot) the ball moves one slat clockwise. Tails move it one slat counter clockwise.
We start out with 37 unpainted slats. But as time goes by more and more slats are visited at least once and painted. It will take a long time but eventually every slat will be painted. But which one is most likely to be last? Is it the single zero on the other side of the wheel? That would seem to make sense but it’s not the answer. The actual answer is that the probability of being the last slat painted/visited is the same for all the slats! One out of 37.
This question and answer was posted on our website twoplustwo.com and the poster asked for an explanation as to how this could be true. Several math PhD’s gave complicated answers that did not make me happy. I have learned that simple questions with simple answers almost always have simple explanations. Could I find it when PhD’s couldn't? You betcha.
The idea is to think of the problem from the perspective of a slat rather than the ball. If I am slat number 23, what do I need to happen in order to be the last slat painted? Two things. First I need the ball to bump up against me on one side or the other. Notice that when that happens for the first time, the slat on the other side of me will be unpainted. (The slats on either side of double zero fulfill this criteria instantly but that doesn't make them different.) Also notice that this event of feeling the ball next to you for the first time will be experienced by every slat. Once you experience that first bump, you now need the coin flip to tell the ball not to jump into your slat. Because if it did, you wouldn't be last. The slat on the other side is unpainted. So what you actually need to happen is for the ball to eventually make its way all the way around the wheel and plop into your neighbor on the other side. If and when it does that you are guaranteed to be the last slat painted, though it might take awhile, because there are no other unvisited slats.
So you need a parlay. The first part is 100%. As it is for all slats. The second part is the same for all. You need the ball to change course all the way to the other side of you without reaching you via the side first visited (You might realize that this is equivalent to a freezeout of coin flips where your opponent has 36 dollars and you have one dollar, giving you a 1/37 chance.) The parlay is thus equal for all slats.