# Thread: the dollar bill problem

1. ## the dollar bill problem

[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?

Thank you!
L

2. ## Re: the dollar bill problem

This is a binomial probability distribution. I'm going to use n for the number of digits guessed correctly out of m digits.

$p=Pr[$guessing a digit correctly$]=\dfrac 1 {10}$

$Pr[$guessing $\geq n$ correctly$]=1-Pr[$guessing $<n$ correctly$]$

$Pr[$guessing $k$ correctly$]=\begin{pmatrix}m \\ k \end{pmatrix}(1-p)^{n-k}p^k$

$Pr[$guessing $<n$ correctly$]=\displaystyle{\sum_{k=0}^{n-1}}\begin{pmatrix}m \\ k \end{pmatrix}(1-p)^{n-k}p^k$

Note that $\begin{pmatrix}m \\ k \end{pmatrix}$ is "m choose k", or the binomial coefficient(m,k) $=\dfrac {m!}{(m-k)!k!}$

so

$Pr[$guessing $\geq n$ correctly$]=1-\displaystyle{\sum_{k=0}^{n-1}}\begin{pmatrix}m \\ k \end{pmatrix}(1-p)^{n-k}p^k$

3. ## Re: the dollar bill problem

Perhaps you meant to put m-k rather than n-k as the exponent of (1-p), didn't you?
Either way, I'll have to think it through a bit longer, because at the moment I can't really fit my results to your formula.
Maybe I didn't state the problem correctly.

I'll explain what I mean, from my simpler, non-theoretical point of view.

Take the simplified case of hypothetical banknotes with serial numbers of 3 digits only.
If you pick one of these at random, it's like picking one number at random out of the 1000 integers between 000 and 999.

Suppose I bet that in this randomly picked number there is a 3.
How many of the numbers between 000 and 999 contain a 3? I just counted them (using Maxima list operations): they're 271.
So my probability of guessing the 3 right would be 271/1000.
Up to this point I agree with your last formula (with the above n to m correction): using n=1, m=3, p=0.1 I obtain Pr(guessing >=n correctly)=0.271.

Now I bet that the serial number contains a 3 and a 5.
There are 54 such numbers, so the probability would have to be 54/1000.
Your formula, with n=2, m=3, p=0.1 gives Pr=0.028.

And if I bet that it contains a 3, a 5 and a 9, there are 6 numbers (=3!, i.e. all the permutations of these 3 digits), i.e. a probability of 6/1000.
Your formula, with n=3, m=3, p=0.1 gives Pr=0.001.

So, I'll try and understand if I'm barking up the wrong tree, but at the moment I don't see how the binomial probability applies to my case for n>1.

Thanks
L

4. ## Re: the dollar bill problem

Hello, lavoisier!

We are considering the 8-digit serial number on a random bill.
You are betting that a particular digit appears on the bill.

What is the probability that a "3" is on the bill?

Consider the probability that the number does not contain a "3".
. . The first digit must be one of the other 9 digits: $\displaystyle \text{Prob.} = \tfrac{9}{10} = 0.9$
. . The second digit must be one of the other 9 digits: $\displaystyle \text{Prob.} = 0.9$
. . The third digit must be one of the other 9 digits: $\displaystyle \text{Prob.} = 0.9$
. . . . . . . . . . . . . . . . . $\displaystyle \vdots$
. . The eighth digit must be one of the other 9 digits: $\displaystyle \text{Prob.} = 0.9$

Hence: .$\displaystyle P(\text{no 3}) \,=\,\left(0.9)^8 \:=\:0.43046721 \:\approx\:0.43$

. . . . . . $\displaystyle P(\text{at least one 3}) \:=\:1-0.43 \:=\:0.57$

You will win the bet about 57% of the time.

5. ## Re: the dollar bill problem

Hi Soroban,
However, I don't understand why you say that my answers are way off.
My formula gives the same result as yours for guessing one digit right in the 8-digit serial number:

$\displaystyle {\rm pr}\left(n,p,m\right)={{\sum_{i=0}^{m}{\left(-1\right)^{i}\,{ m\choose i}\,\left(n-i\right)^{p}}}\over{n^{p}}}$

$\displaystyle {\rm pr}\left(10,8,1\right)= {{\left(-1\right)^{0}\,{ 1\choose 0}\,\left(10-0\right)^{8} + \left(-1\right)^{1}\,{ 1\choose 1}\,\left(10-1\right)^{8}}\over{10^{8}}} = {{{10^{8} - 9^{8}}\over{10^{8}}} {\approx 57 \%}$

Perhaps you looked at the examples I cited for p=3, where indeed the percentage of guessing one digit right is 27.1%. Your method would give the same result:

$\displaystyle 1 - \left(0.9\right)^3 = 27.1 \%$

My formula, yours and romsek's all agree when m=1, I got that.

The problem I was describing was to guess 3 distinct digits right in an 8-digit random number.

I know my formula works for m>1 when p=3, because I counted the actual numbers that fit the guess.
I haven't tried counting when p=8 because the enumeration of 100 million numbers is computationally too hard for my PC, so I was wondering if anyone can prove or disprove my formula from a theoretical standpoint, or perhaps suggest a simpler version of it.

I don't see how your approach covers the cases for m>1. If you can please explain...

Thanks
L

6. ## Re: the dollar bill problem

Lavoisier, first of all, let's pose the question properly. What I take it you're asking is the following: If someone has an 8-digit number, and you are asked to guess the 8 digits in order, what is the probability you will guess at least three of those 8 digits correctly?

Note, that you are not being asked the probability of getting exactly three digits right because you will win the bet if you get more than three right. So it's three or more.

Therefore, in order to solve it you must do 6 separate calculations, though if you have a little math computer like the TI-89 you can write the six as one.

So the basic idea is this: To calculate the probability of getting EXACTLY three digits correct, you compute the likelihood of getting EXACTLY three right in one particular way, and then multiply by the number of different ways that can occur.

So one particular way of getting EXACTLY three digits right is getting the first three right and then getting the next five wrong.

So that's .1(exp)3 X .9(exp)5. How many different ways are there to arrange 3 objects in 8 places? 8!/(3! X 5!) So the probability of guessing EXACTLY 3 digits right is:

.1(exp)3 X .9(exp)5 X 8!/(3! X 5!) which equals about .033.

You repeat the process to determine the probability of getting EXACTLY 4, 5, 6, 7, and 8 right and add them up. With a little math computer you do a sum of a sequence, substituting "z" for the numbers 3 through 8 and you need to write out only a single algorithm, as follows:

Sum(Sequence(.1(exp)z X .9(exp)(8-z) X 8!/(z! X (8-z)!), with z=3 to 8, with increments of 1 The answer is .038.

7. ## Re: the dollar bill problem

I may be wrong, but I believe your formula is basically the same as the binomial one proposed earlier, which doesn't seem to work in practice in the simpler case of numbers of 3 digits.
The funny thing is that I see the logic in the formulae people put forward, but then the figures don't match the actual, enumerated results, which I think proves there's something not right in the mechanism.

$\displaystyle \sum_{z=3}^{8}{{{0.1^{z} \, 0.9^{8-z} \, 8!}\over{\left(8-z\right)!\, \,z!}}} = 0.03809$

to the case where you bet on 2 digits in a 3-digit serial number:

$\displaystyle \sum_{z=2}^{3}{{{0.1^{z} \, 0.9^{3-z} \, 3!}\over{\left(3-z\right)!\, \,z!}}} = 0.028$

But we already know this result is wrong (see my 2nd post above).
If you choose for instance 3 and 5 as the two digits that must be present, you can see in practice that there are 54 numbers that contain each of these two digits at least once. Here they are:

$\displaystyle [35,53,135,153,235,253,305,315,325,335,345,350,351, 352,353,354,355,356,357,358,359,365,375,385,395,43 5,453,503,513,523,530,531,532,533,534,535,536,537, 538,539,543,553,563,573,583,593,635,653,735,753,83 5,853,935,953]$

So I think by definition we should get 54/1000 = 5.4%, not 2.8%.

Perhaps my definition of the problem is not canonical, but still, it is a real problem that can occur in practical situations, so I thought there should be a theoretical, probability-based approach to deal with it...

8. ## Re: the dollar bill problem

Hello, lavoisier!

First of all, a big apology.
It was late at night, I was out of coffee, yada-yada . . .

Here is a similar "sucker bet".

Have someone choose a bill from his wallet.
You bet that there is either a "3" or "7" in the serial number.

If he balks, remind him that you are guessing
only two digits out of a possible ten digits.

Let us calculate the probability.

What is the probability that the bill has neither a 3 nor a 7?

The 1st digit must be one of the other 8 digits: Prob = 0.8
The 2nd digit must be one of the other 8 digits: Prob = 0.8
The 3rd digit must be one of the other 8 digits: Prob = 0.8
. . . . . . . . . . $\displaystyle \vdots$
The 8th digit must be one of the other 8 digits: Prob = 0.8

Hence: $\displaystyle P(\text{no 3s, no 7s}) \:=\0.8)^8 \:=\:0.16777216$

9. ## Re: the dollar bill problem

Lavoisier, I admire your passion, as evidenced by your listing all 54 possibilities--that bespeaks uncommon zeal!! I am officially "wowed" by it!!!

And because of that I will take the time to carefully point out what I believe are your errors.

First, regarding the 8 digit problem that I addressed in my first response--my assumption was that the digits had to be predicted in order, and the question then is, What are the odds of correctly naming the digit in 3 or more places. So, for example, if the 8 digit number you are trying to predict is 12345678, then if you guess 64395218 you will have gotten three digits right, the one in the 3rd position, the 5th position and the 8th position. The probability of doing that (guessing three or more right in that manner) is exactly what I calculated it to be in my first post.

Now, what you indicated in your most recent post is that your understanding of the problem is different: You say the question is, What is the probability of all the chosen digits appearing ANYWHERE, regardless of position. So, according to you, if your first guess is 7, and 7 appears not just in the first position, but in any position, you will be given credit for getting that correct. I don't think that that's a proper understanding of the problem you posed for this reason: You didn't specify how many guesses the bar patrons got. That's crucial. For example, if the bar patrons got 8 guesses, and the problem was as you posed it, the chance they'd get 3 or more numbers right is about 99.9 %!!!!! Obviously, that's not what they were being required to do. If the bar patrons had gotten some definite number of guesses, well short of 8, that fact would have been prominently featured in the video you saw. The fact that it wasn't inclines me strongly to believe the actual problem was the one I solved in my first post.

Now, for "extra credit" let's look at the specific problem you posed in your last post: All you say is "the case where you bet on 2 digits in a 3-digit serial number".

What exactly does this mean, Lavoisier? Would you say this is a fair statement of the problem you are posing?: Someone has a secret random three digit number. You have to name two of the three numbers making up that three digit number. You get two opportunities to name digits: if both your choices appear anywhere among the three digits, you win, but both your choices must appear; that is, you can't have a wrong guess. What is the probability you will win? Is that fair, Lavoisier?

But that way of posing the problem creates issues you might have overlooked. For example, what if you take a first guess, let's say '6', and the secret number contains two 6s. Do you immediately win? Or are you compelled to take a second guess, and if wrong, you'd lose? Or what if you're not compelled to take a second guess, but are permitted to, but are not told whether you've already 'won' (by having correctly guessed two digits) or not? Or, what if the random secret number is 777? Then, in order to win, both your guesses would have to be "7". Or perhaps you intend a stipulation that the random secret number will NOT be all the same digit. But in that case, you will affect the probability of winning because you're eliminating 10 of the 1000 possibilities. I could go on!!!

So let's express the problem very precisely, but in two different ways, with different probability outcomes of course:

1)Someone has a hidden secret three-digit number. You will have two opportunities to guess at least two of the digits. If you manage to do that on your first guess, you will immediately be declared the winner. If not, you will have an opportunity to make a second guess. Between your two guesses you must have gotten at least two of the digits right, without having either guess come up empty. (So, for example, if your first guess is '5' and your second guess is '8' and the number is '388' you lose because your first guess came up empty. But if your first guess had been '8' you'd have instantly been declared a winner.) Assuming you employ the best strategy, what is your probability of winning?

2)This second version is the same as the first except that you are not told if you have already guessed two digits with your first guess. Thus you could have already achieved your objective with your first guess, but will not be aware of it. Again, assuming you employ the best strategy, what is your probability of winning?

So for Version 1, the answer is this: First, what is the chance that you will get at least two digits with your first guess and be declared the winner?

The chance of getting exactly two digits correct is .1(exp)2 X .9 X 3=.027 (Of course exp is exponent).
In words, your chance of your guess hitting the first digit and second digit of the hidden random 3 digit number and missing the third digit is .1(exp)2 X .9 and there are three ways you can do that (getting the first and second, the first and third, and the second and third).

The chance of getting exactly three digits correct with your first guess is .1(exp)3=.001.

So your chance of immediately being declared the winner with your first guess is .028.

Now, what if you're not immediately declared the winner?

We know that in order to win on your second guess, the first guess cannot be a wrong one. Therefore, we must calculate the chance that your first guess hit exactly one digit of the secret number.

That's .1 X .9(exp)2 X 3=.243.

Now, it's a little tricky. We only have 9 numbers left to choose from—what is the chance our second guess will also be correct:

1-(8/9)(exp)2)=.209876543 In words, the chance that you'll be wrong with your second guess, (that it'll miss the two remaining digits) is 8/9 squared and so the chance it'll be right is 1- 8/9 squared.

So the chance you'll win with your second guess is .243 X .209876543=.051 (exactly .051, which you'd expect since we're dealing with chances out of a thousand).

So, the chance of winning overall in this first version is .028 + .051=.079.

Now let's tackle the second version of the problem, where you're not told if you've won with your first guess. The best strategy is to assume you haven't (since winning with your first guess is only a .028 chance, as we've already determined), and you take a second guess.

So, in order to win with the second guess, you must have hit one or two digits with the first guess (but not three, because then you'd automatically miss with a second guess of a different number).

So if you hit EXACTLY one digit with your first guess, now you must hit with your second guess, and it's:

.243 X (1-8/9(exp)2)=.051 (The .243 is from earlier—the chance of getting exactly one digit, and the second expression is from earlier too—see above)

And if you hit EXACTLY two digits with your first guess, now you must get the remaining one with your second guess:

As we determined earlier, hitting exactly two digits with the first guess is .027, so, hitting exactly two and then getting the second guess right (of the remaining digit) is:

.027 X 1/9=.003.

So, winning the bet in the second version is .051 + .003=.054. This second version is basically what you did, guess two different numbers, with no wrong guess allowed, which is why you got the 54/1000 possibilities you zealously enumerated to begin all this madness!!

But just to remind you Lavoisier, all of these calculations don't apply to the bar problem you originally posed, which I dealt with in my first post.

10. ## Re: the dollar bill problem

Thank you all for your replies and for taking the time to examine this problem, which is now solved!

No need to apologise, Soroban, I suppose we were all just trying to understand how things worked and to contribute constructively to the solution of this problem; mistakes are forgivable (or at least, I think they should be).

Perhaps my formulation of the problem was confusing / incomplete. Sorry. I suggested at the beginning that this might happen, given that I'm not a mathematician.
I suppose what matters is that the results are the same, for my intended interpretation of the situation. That's what I was trying to understand.

For total clarity, if I can hope to manage that: what I wanted to calculate was how many numbers, in the set of all 10^p positive or zero integers of p digits, contain a given set of m distinct digits, regardless of what these digits are, of their position, and of repetitions (if any). I included n (all the possibilities for each digit, in our case the 10 integers from 0 to 9) just to add generality. p, n and m are positive integers, with 1 <= m <= min(n,p).
I am told that, for this purpose, my formula was correct - someone in another forum proved it theoretically; and another guy ran a computer simulation to show that the measured percentages matched regardless of the choice of the m digits.
Phew! Relief... no mental asylum needed for me, yet :O)

By the way, cornucopia, I got a computer to enumerate the 54 numbers, so it was much less strenuous an effort than it might have looked at first sight. And as far as zeal is concerned, I think we can safely say that your latest post beats me hands down! :O)

11. ## Re: the dollar bill problem

Hi Lavoisier, I too am glad mathematics was not responsible for putting you in a "mental asylum"; it certainly has, in various ways, driven people mad, or at least driven them to commit acts suggestive of temporary insanity--it's said the Pythagoreans forced one of their members to swim out in the Aegean--and keep swimming--until he drowned, because he had proved, heretically, the irrationality of the square root of 2.

But the reason for this post is to ask if you'd be so kind as to give me a link to, or at least the name of the forum where you said someone proved your formula theoretically--I'd like to read that proof. Thanks.

12. ## Re: the dollar bill problem

Sure, here it is:

the dollar bill problem