Have I mentioned I have the best readers? *8)
On the math problem from last time, a reader writes:
C - S + S((S-1)/S)^C
Which is lovely, and I suspect also correct.
Think about it first in the case where C=S. Imagine that all of the cards are sitting in the slots on the table, one to a slot. The number of not-on-the-felt cards here is zero, of course. If we want to raise that number to one, we take a card from some slot that has exactly one card in it, and put it into another occupied slot; that will leave one slot empty. If we then want to raise it to two, we have to move another card that's all by itself in a slot (moving the card that's already on some other card will either leave the count at one or put it back to zero). If we do move another lone card to a still-occupied slot, there will now be two not-on-the-felt cards, and two empty slots.
And in general every time we want to raise the number of not-on-the-felt cards, we also have to raise the number of empty slots by the same amount. So the number of not-on-the-felt cards is the number of empty slots. And what is the expected number of empty slots? Well that we can figure out!
The probability that a given slot will be empty is just the probability that every card goes into some other slot. The probability that any particular card goes into some other slot is (S-1)/S (if there are ten slots, the probability that the next card dealt will go into some slot other than slot five, say, is 9/10). Since the probabilities here are independant, the probability that all of the cards will go into other slots, leaving this slot empty, is ((S-1)/S)^C (S minus one over S, to the C).
Since there are S slots, the expected number of empty slots is exactly S times that probability, or S((S-1)/S)^C. (I worry that I'm overlooking some assumption here, but if I am it doesn't seem to be an important one.)
Now that was all for the C = S case. I haven't quite convinced myself that the solution is right for the C ≠ S case, but here's the argument: If C is larger than S (you have more cards than slots), then at least (C-S) cards must be in non-empty slots, so you can imagine yourself starting with at least one card in each slot and the rest wherever you like, and then continue the argument above. If C is smaller than S (fewer cards than slots), at least (S-C) slots will always be empty, so imagine starting with every card in a slot by itself, with (S-C) already empty, and again continue the argument above.
Yeah, I think that works. *8)
So thank you very extremely, treasured reader! I'll have to think about whether I can actually use that in the actual larger problem that I'm actually working on, even.
(By the by, I fixed a typo in the previous entry, where I had a "C to the power S" that should have been "S to the power C".)
Oh, and note that the Kind Reader's solution does have, in the C = S case, S^S in the denominator, as prophesied: in that form it's S((S-1)^S) over S^S. And if we evaluate S((S-1)^S) for our test cases, it turns out to be zero for 1, 2 for 2, and 24 for 3, also as expected! The exact solutions for 12 and 24 turn out to be closer to 4.224 and 8.642 than the 4.225 and 8.644 that I got from simulation; I wonder if I have a bug somewhere, hm....
So that has made me smile!
"At one time," the turtle said in didactic tones, "a solar-powered flashlight was considered a sort of oxymoron, an obviously-useless gadget: a light that works only in sunlight.
"But in reality a solar-powered flashlight charges its batteries in the sun, and later uses those batteries to provide light in the dark, and is thereby useful. Now that solar power is no longer an oddity, we have stopped basing jokes around misunderstanding it.
"One could argue that the useful device is not actually a solar-powered flashlight, but instead a battery-powered flashlight coupled to a solar-powered battery charger. But the result of packing together a solar-powered battery charger and a battery-powered flashlight simply is in fact a solar-powered flashlight. There is no alterntive."
I thought of that this morning on the drive to work for some reason. I don't know why it ended up being a turtle saying it. How would a turtle hold a flashlight (solar-powered or not)? In his litle jaws, perhaps. Or maybe this turtle has opposable thumbs.
Then we could talk about how much sense it makes to talk about a turtle with opposable thumbs. Would that still be a turtle? Why or why not? Is not having opposable thumbs more or less central to being a turtle than is, say, being unable to speak? Or not understanding the concept of solar power?