[Caveat: I'm not a mathematician and I can't write formulae in Tex, so please bear with my non-professional approach and editing].
A few days ago I was watching a TV programme about maths-based gambles/heists.
Our guy goes to a bar that has its walls completely covered with 1-dollar bills, so the gamble is about banknotes.
To cut a long story short, basically he bets with the people in the bar that they won't be able to guess 3 digits out of the 8 digits in a randomly picked bill's serial number. And indeed, as it turns out, people get at most 1 or maybe 2 right, but not 3.
He then asks the lady at the till to pick out a 50-dollar bill and he bets he can guess 3 digits right. And he does. And he walks away with the 50 dollars.
He later explains that 'it's not so easy to guess 3 digits right', and that he could do it because the 50-dollar bill was his own (he had paid a drink with it earlier, etc etc...).
The point is, after seeing this I tried to calculate the probability of guessing the 3 digits right (assuming banknotes had completely random serial numbers), and then more in general to guess m digits right in a number of p digits.
This is how I tried to do it.
8 digits each from 0 to 9 means a total of 108 numbers.
Guessing 1 digit right happens whenever this digit is present at least once in the number (i.e. from 1 to 8 times). Or whenever the opposite doesn't happen, i.e. whenever it's not true that the digit is present 0 times.
The digit is present 0 times in 98 cases, so it is present at least once in 108-98 cases, giving a probability of success of about 57%.
I hastily/naively thought I could extend this reasoning to 2 digits by doing 108-88, but I saw it didn't work, because 88 is the number of cases in which *neither* of the 2 digits are present, but among the remaining 108-88 cases there are many numbers where only one of them is present and the other isn't.
So I had to think a bit harder about it, and I eventually used simple set theory to reduce any expression with multiple digits to guess to a sum of 'simpler' cases.
For instance, I found that the number of cases in which 2 chosen (and distinct) digits, say 3 and 5, appear in the serial number is:
N(3 and 5) = N(3)-N(3 and not(5))=N(all)-N(not(3))-N(not(3))+N(not(3) and not(5))=N(all)-2*N(not(3))+N(not(3) and not(5)) = 108-2*98+88 = 30683774, i.e. a probability of about 31%.
By the same reasoning, for 3 (distinct) digits like for instance 3, 5 and 8, I found:
N(3 and 5 and 8) = 108-3*98+3*88-78 = 15426684, i.e. a probability of about 15%.
As the number resembled the ones from the binomial theorem, only with alternating sign, I thought there was a pattern emerging here, and I made a wild guess that perhaps the number of cases where m chosen distinct digits are all present in a number of p digits each being able to take n random values could be:
N(m digits all present) = Sum ( (n-i)p * (-1)i * m!/(m-i)!/i! ) for i going from 0 to m
My questions are:
- is this result correct?
- is there any simpler expression for it?
- would you advise an easier/more direct approach to solve this kind of problem?