4

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

Knells
  • 143
  • The $N$ coins are each selected randomly from the five possibilities, I assume? – Caleb Stanford Sep 25 '15 at 04:07
  • @6005 Yes, or 3 possibilities, if excluding whole dollar value coins. The bag is random accumulated change. – Knells Sep 25 '15 at 04:11
  • 2
    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)$? – Brent Sep 25 '15 at 04:32
  • One would have to make assumptions about the distribution of coins in "random accumulated change". – Christian Blatter Sep 25 '15 at 12:20

2 Answers2

3

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.

Empy2
  • 50,853
0

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.

Caleb Stanford
  • 45,895
  • 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. – Caleb Stanford Sep 25 '15 at 17:49