Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was thinking about how I might go about solving a problem of, given an ATM that dispenses $50's and $20's, find all the combinations of notes dispensed that would be valid for a given amount.

Say, for $160, that could be 8 $20's or 2 $50's and 3 $20's.

Now, I can do this in my head easily enough (for small numbers and only 2 variables), but I want to find out how to solve this properly.

As far as I can tell, this formula is Ax + By = C, where A = 20, B = 50, C = 160.

Because this is talking about real-world paper notes being dispensed, A and B both have to be integers >= 0.

I can plug this into Wolfram Alpha: http://www.wolframalpha.com/input/?i=%2850*x+%2B+20*y%29+%3D+160%3B+x+%3E%3D+0%3B+y+%3E%3D+0

So obviously a computer can determine the result.

But from my shaky recollection of high school mathematics, to solve something like this you need 2 equations to substitute in.

Or is my condition of "integers >= 0" another equation?

Also, there can be more than 1 answer (or 0 answers) for different values.

Is this done by brute-forcing numbers in a loop, or is there an equation you can use to solve this?

I had a look into matrixes, but most of it went over my head, and I couldn't figure out what I needed to actually insert into the matrix to find the result, or whether it was even applicable to my situation.

share|improve this question
2  
The "two equations are necessary" only holds in certain situations. Here, "integers >= 0" is not an equation, but it will still make it so that you only have a finite number of solutions. Matrices are irrelevant here; you want to look into linear diophantine equations. –  only Aug 30 '12 at 5:11
2  
So, $20x+50y=160$ where $x,y$ are non-negative integers $\implies 2x+5y=16\implies5y=2(8-x)\implies 0≤x<8$, similarly $0≤y<4$, So $\frac{y}{2}=\frac{8-x}{5}=z$(say) where $z$ is an integer $\implies y=2z, x=8-5z$ So, $y$ can be $0,2$, the respective values of $x$ are $8,3$. –  lab bhattacharjee Aug 30 '12 at 5:24

2 Answers 2

up vote 2 down vote accepted

This is a complete answer only for $50x+20y=m$. It is clear that $m$ must be a multiple of $10$, say $m=10n$. So we want to find the number of non-negative solutions of $5x+2y=n$. Clearly there are none unless $n \ge 0$. So from now on suppose that $n \ge 0$.

It is easy to see that $x_0=n$, $y_0=-2n$ is a solution of the equation $5x+2y=n$. Unfortunately, except when $n=0$, one of $x_0$ or $y_0$ is negative.

However, it is not hard to show that the integer solutions of the equation $5x+2y=n$ are given by $$x=n-2t,\qquad y=-2n+5t,\tag{$1$}$$ where $t$ ranges over the integers, positive, negative, or $0$.

We have $x\ge 0$ and $y\ge 0$ iff $t\le \frac{n}{2}$ and $t \ge \frac{2n}{5}$. So the condition on $t$ can be summarized by the inequalities $$\frac{2n}{5}\le t \le \frac{n}{2}.$$ This gives an explicit way of generating all non-negative solutions. We can also get an explicit formula for the number of non-negative solutions. Informally, it is the number of integers in the interval $2n/5 \le t \le n/2$.

We can use fancier symbols. The integer parameter $t$ travels from $\left\lceil \frac{2n}{5}\right\rceil$ to $\left\lfloor\frac{n}{2}\right\rfloor$, where $\lceil x\rceil$ is the smallest integer $\ge x$, and $\lfloor x\rfloor$ is the greatest integer which is $\le x$. So the number of non-negative solutions is $$\left\lfloor\frac{n}{2}\right\rfloor-\left\lceil \frac{2n}{5}\right\rceil +1.$$

Remark: All of the above can be generalized. Assume that $a$ and $b$ are positive, with greatest common divisor equal to $1$. (The case where the greatest common divisor is $\gt 1$ can be dealt with by the same trick that got us from $50$ and $20$ to $5$ and $2$.)

Suppose that we have found a solution $(x_0,y_0)$ of $ax+by=1$. Then one integer solution of the equation $ax+by=n$ is $(nx_0,ny_0)$. It turns out that all integer solutions are given by $x=nx_0-bt$, $y=ny_0+at$, where $t$ ranges over the integers.

To force the solutions to be non-negative, we obtain inequalities of the same character as the ones we got in the case $a=5$, $b=2$.

Now we briefly mention the often difficult part, finding one solution of $ax+by=1$. We can, for small numbers, find a solution by experimentation. For larger $a$ and $b$, we use the Extended Euclidean Algorithm.

Note that we have only discussed the problem of two kinds of "bills." the problem for $k$ kinds of bills can be tackled using generating functions. But the general case is very much more complicated than the case $k=2$ discussed above, and the answers are quite a bit less satisfactory.

share|improve this answer

You are looking for integers $x,y$ that satisfy $50x+20y = d$, and $x, y \geq 0$.

First notice that since $\gcd(50,20) = 10$, you must have $10 \mid d$. So we look for solutions to $5 x + 2 y = \frac{d}{10}$ instead (having 2 and 5 be coprime is convenient).

We notice that $5 - 2\cdot 2 = 1$, so we can easily determine a solution (ignoring the non-negativity constraint for the moment) by $x_0= \frac{d}{10}, y_0 = - \frac{2d}{10}$, since $5 x_0 + 2 y_0 = \frac{d}{10}$.

Now suppose $(x_1, y_1)$ and $(x_2,y_2)$ are two solutions (possibly negative; we will deal with that in a moment), then we have $5 (x_1-x_2) + 2(y_1-y_2) = 0$. It follows from this that $5 \mid (y_1-y_2)$, hence $(y_1-y_2) = 5k$, for some integer $k$. It then follows that $x_1-x_2 = -2 k$.

This tells us that all solutions are given by $(\frac{d}{10}-2k, - \frac{2d}{10} + 5k)$, where $k \in \mathbb{Z}$.

Now we are in a position to deal with the non-negativity constraint. To satisfy the positivity constraints, we need $\frac{d}{10}-2k \geq 0$, and $-\frac{2d}{10} + 5k \geq 0$, or in other words, $k \geq \frac{2d}{50} = \frac{d}{25}$, and $k \leq \frac{d}{20}$. This gives all non-negative solutions.

To illustrate with your example, let $d = 160$. Then the solutions are:

$k = 7, (x, y) = (2, 3), 50x+20y = 160$

$k = 8, (x, y) = (0, 8), 50x+20y = 160$

share|improve this answer
    
Thanks - I feel bad that I have to pick one answer, seeing as I'm not in much of a position to make a real judgement call over which is more accurate, so I can only make a choice based on the other answer indirectly mentioning that there is not a direct answer for all cases of different numbers of bills. –  steveh7 Aug 30 '12 at 9:23
    
No problem at all. –  copper.hat Aug 30 '12 at 14:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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