In my country we have \$0.10, \$0.20, \$0.50, \$1, and \$2 coins. If I were to pour a bag of coins out on the table what would be the probability that I could buy a heap of \$1 snacks without needing any change? Does this change if the bag doesn't contain any whole dollar value coins?

I'm fairly sure the that $P=0.1$ for very large values of $N$ (as there is 10 possible cent values). I'd like to be able to prove this and be able to see how the probability changes with $N$, but I cant figure out a rule for the entire series & larger values of $N$.

I've written a little Python simulation to test $N$ values $0$ through $50$ and I'll edit with the results of that when it finishes.

EDIT: Results of my script seem to confirm my thought: http://pastebin.com/cD8PeuwT

  • $\begingroup$ The $N$ coins are each selected randomly from the five possibilities, I assume? $\endgroup$ – 6005 Sep 25 '15 at 4:07
  • $\begingroup$ @6005 Yes, or 3 possibilities, if excluding whole dollar value coins. The bag is random accumulated change. $\endgroup$ – Knells Sep 25 '15 at 4:11
  • 2
    $\begingroup$ If it helps any, you may essentially reduce this down to: how many solutions are there for $A,B,C,D,E$, integers between 0 and $N$ that satisfy $A+B+C+D+E=N$ and $10A+20B+50C\equiv0(\mod 100)$? $\endgroup$ – Brent Sep 25 '15 at 4:32
  • $\begingroup$ One would have to make assumptions about the distribution of coins in "random accumulated change". $\endgroup$ – Christian Blatter Sep 25 '15 at 12:20

You are in one of ten states; that being the number of 10c.
So treat it as a ten-vector, initially in state $v=[1,0,0,0,0,0,0,0,0,0]$. The transition matrix is either this one, for no gold:
$$A=\left[\begin{array}{cccccccccc} 0&1/3&1/3&0&0&1/3&0&0&0&0\\ 0&0&1/3&1/3&0&0&1/3&0&0&0\\ 0&0&0&1/3&1/3&0&0&1/3&0&0\\ 0&0&0&0&1/3&1/3&0&0&1/3&0\\ 0&0&0&0&0&1/3&1/3&0&0&1/3\\ 1/3&0&0&0&0&0&1/3&1/3&0&0\\ 0&1/3&0&0&0&0&0&1/3&1/3&0\\ 0&0&1/3&0&0&0&0&0&1/3&1/3\\ 1/3&0&0&1/3&0&0&0&0&0&1/3\\ 1/3&1/3&0&0&1/3&0&0&0&0&0\end{array}\right]$$ or something similar with fifths if there is gold.
The initial distribution, for no coins is $v$; for one coin is $vA$, for two coins is $vAA=vA^2$ and for $n$ coins is $vA^n$.
Look at the eigenvalues of the matrix to see how quickly the initial state approaches $[1/10,1/10,...,1/10]$
It turns out the eigenvalues are $(\omega+\omega^2+\omega^5)/3$, where $\omega^{10}=1$ is one of the tenth roots of unity. The largest of these, when $\omega=1$, is $1$. The next largest eigenvalues have amplitude 0.71632, so the distance from an even distribution decreases by that proportion when $N$ increases by 1.
The eigenvalues with gold coins are $(2+\omega+\omega^2+\omega^5)/5$, the largest of which (except 1) has absolute value 0.58713, so it reaches equilibrium more quickly.

| cite | improve this answer | |

I'm fairly sure the that $P=0.1$ for very large values of $N$

Here is a proof of this statement.

As $N$ tends to infinity,

  • The amount of extra money from 10-cent coins will tend towards a uniformly random distribution on $\{0, .1, .2, .3, .4, .5, .6, .7, .8, .9\}$.

  • The amount of extra money from 20-cent coins will tend towards a uniformly random distribution on $\{0, .2, .4, .6, .8\}$.

  • The amount of extra money from 50-cent coins will tend towards a uniformly random distribution from $\{0, .5\}$.

To find the final probability of the total money being an integer, we just add these three distributions mod $1$. But the uniform distribution added to any distribution mod 1 is again the uniform distribution. So the distribution on the sum mod 1 is (as $N \to \infty$) uniform on $\{0, .1, .2, .3, .4, .5, .6, .7, .8, .9\}$, as you conjectured.

| cite | improve this answer | |
  • $\begingroup$ Maybe the downvoter completely misunderstood what I was proving here. I have edited to clarify. If you have an actual problem with this answer, please explain. $\endgroup$ – 6005 Sep 25 '15 at 17:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.