[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 10^{8}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 9^{8}cases, so it is present at least once in 10^{8}-9^{8}cases, giving a probability of success of about 57%.

I hastily/naively thought I could extend this reasoning to 2 digits by doing 10^{8}-8^{8}, but I saw it didn't work, because 8^{8}is the number of cases in which *neither* of the 2 digits are present, but among the remaining 10^{8}-8^{8}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)) = 10^{8}-2*9^{8}+8^{8 }= 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) = 10^{8}-3*9^{8}+3*8^{8}-7^{8}= 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?

Thank you!

L