3
$\begingroup$

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.

  • 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$.2012-08-30

2 Answers 2

2

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.

3

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$

  • 0
    No $p$roblem at all.2012-08-30