How do i find all possible ways of obtaining a total value of 40 cents from 5 cent and 8 cent stamps?

Question

You have an inexhaustible supply of $5$-cent and $8$-cent stamps.

List all possible ways of obtaining a total value of $40$ cents with these stamps.

I used a probability tree to solve this problem. But I feel like there's a better way and the probability tree took too much time. There are more questions like this and they the cents turn into dollars and they keep getting bigger.

I was wondering if anyone has a more efficient way?

Answer 1

First, see that $40$ can be divided by $5$ and $8$, and so you get $5 \times 8.$ That means you can get $40$ by using $8$ $5$-cent stamps or using $5$ $8$-cent stamps.
Now using both stamps :
Check if there are any positive integer solutions for $a$ and $b$:
$5a + 8b=40$
$8b=40-5a$
$40 - 5a$ is a multiple of $5$ which is smaller than $40$ so $8b$ has to be a multiple of $5$ which is smaller than $40$
but no such $b$ exists so the answers are $8$ $5$-cent stamps or $5$ $8$-cent stamps

Answer 2

Well, clearly you can have as many as $5$ eight cents (and no fives cents) or as few as $0$ eight cents (and eight five cents). So you can have $0,1,2,3,4,$ or $5$ eight cents.

That adds to $0,8,16,24,32$ or $40$ cent's meaning the rest must be made up of only five cent stamps, but the remaining balance of $40, 32,24,16,8, $ or $0$ must be divisible by $5$ and only $0$ or $40$ are.

So $5$ eight cents and $0$ fives, or $8$ fives and $0$ eights are the only two ways two do it.

Now, with a bit of experience, knowing $8$ and $5$ are relatively prime and $40$ is the least common multiple that $5a + 8b = \text{lcm}(5,8)$ can only occur if $a$ or $b$ is zero, but I wouldn't expect that to be immediately obvious.

Answer 3

$$ 5x+8y = 40$$

$$ 5x=40 - 8y$$

$$ x=8-\frac {8y}{5} $$

Thus $y$ must be a multiple of $5$

The only non-negative integral solutions are $y=5 , x=0 $ or $y=0, x=8 $

Thus the answer is you can only use one kind of stamps to fulfil your demand.

Answer 4

The problem is to find non-negative solutions to the Diophantine equation $5x+8y = 40$. So solve in the usual way to get

$$x = 8-8t$$ $$y = 5t.$$

Now you need both $x$ and $y$ to be non-negative, so solve the inequalities

$$8-8t \geq 0$$ $$5t \geq 0$$

to get

$$ t \leq 1$$ $$ t\geq 0.$$

Conclude that the only solutions are when $t=0$ and $t=1$. This technique should work for problems with bigger numbers. You might get a whole range of values for $t$.

Answer 5

$\newcommand{cent}{{c\!\!{\small |\:}}}$ The immediate question has been well answered so I will address the "more questions like this... getting bigger" part.

The first task is to see if there is any answer at all. If the task is, for example, to make $80 \cent$ value from $6\cent$ and $15\cent$ stamps, it cannot be done, because the stamps are both multiples of $3$ and the target value is not.

Thus for feasible problems we could divide the two stamp rates by their $\gcd$, and also the target value, to reduce to a case like that given, where the stamps have no common factor. So for example attempting a target of $99\cent$ with $6\cent$ and $15\cent$ stamp is exactly equivalent (in terms of counting variations) to a target of $33\cent$ from stamps of $2\cent$ and $5\cent$.

There remains a possibility of having no solutions but that can emerge naturally from the next phase of calculation, where you establish the smallest number (possibly zero) of one stamp (for example, the larger) that will allow you to reach the target with some multiple of the smaller stamp value. Then you can simply swap stamps in groups between the larger and the smaller, The exchange stamp counts are given by the results of the division by $\gcd$ - so $6\cent$ and $15\cent$ stamps exchange in the ratio $5$ to $2$. So for example for $99\cent$ in these stamps, we cannot make the amount with only $6\cent$ stamps, but one $15\cent$ stamp makes the target reachable with $84/6= 14$ $6\cent$ stamps, so the solutions are $(14,1), (9,3), (4,5)$ by exchanging $5$ $6\cent$ stamps for $2$ $15\cent$ stamps each time.

---

Things get significantly more complicated if there are three different stamp denominations.

Answer 6

Your case is enough simple that it can be solved by trials. But if I understood properly your post, you are looking for a more general and systemic approach.

So, let's consider the general diphantine equation $$ Ax + By = C $$

We can factor out the greatest common divisor of $A$ and $B$ to obtain $$ \frac{A} {{\gcd \left( {A,B} \right)}}x + \;\frac{B} {{\gcd \left( {A,B} \right)}}y = \frac{C} {{\gcd \left( {A,B} \right)}}\quad \Rightarrow \quad ax + by = c $$ and first of all, we must have that $c$ be an integer, because it is not possible to sum integers and get a non-integral result.

So let's consider $$ \bbox[lightyellow] { ax + by = c\quad \left| \matrix{ \;0 \le a,b,c \in Z \hfill \cr \;\gcd (a,b) = 1 \hfill \cr \;0 \le x,y \in Z \hfill \cr} \right. } \tag{1}$$

which is represented by the line in the following sketch

Now if $(x_1,y_1)$ and $(x_2,y_2)$ are two solutions, then it means that $$ \left\{ \matrix{ ax_{\,1} + by_{\,1} = c \hfill \cr ax_{\,2} + by_{\,2} = c \hfill \cr} \right.\quad \Rightarrow \quad a\left( {x_{\,2} - x_{\,1} } \right) + b\left( {y_{\,2} - y_{\,1} } \right) = 0\quad \Rightarrow \quad a\Delta x + b\Delta y = 0 $$ i.e., that $(\Delta x,\Delta y)$ is a solution to the homogeneous equation.

So we have $$ \left\{ \matrix{ \Delta x = - kb \hfill \cr \Delta y = ka \hfill \cr} \right.\quad \Rightarrow \quad \quad \left\{ \matrix{ \Delta x = - b \hfill \cr \Delta y = a \hfill \cr} \right.\quad $$ because, since $\gcd(a,b) = 1$, the minimal $\Delta$ are given by $k=1$ (or $k=-1$).

From the sketch is clear that, "for a high enough value of $c$" the number of solutions in the first quadrant will be $$ \eqalign{ & n = 1 + \left\lfloor {{{c/a} \over {\left| {\Delta x} \right|}}} \right\rfloor = 1 + \left\lfloor {{{c/b} \over {\left| {\Delta y} \right|}}} \right\rfloor = 1 + \left\lfloor {{c \over {ab}}} \right\rfloor = \cr & = 1 + \left\lfloor {{{C\gcd \left( {A,B} \right)} \over {AB}}} \right\rfloor = 1 + \left\lfloor {{C \over {{\rm lcm}(A,B)}}} \right\rfloor \cr} $$

What does it mean $c$ high enough,intuitively speaking, is that it shall so high as to assure that the point indicated by $P_0$ in the sketch exist.
In your case for instance, you will never be able to attain a value of $1,2,3,4$ clearly, but also e.g. not $11$ ... and finally not $22$.
That is all the powers of $x$ which are missing in the series expansion of $$ f(x) = \frac{1} {{\left( {1 - x^{\,5} } \right)\left( {1 - x^{\,8} } \right)}} = \left( {1 + x^{\,5} + x^{\,10} + \cdots } \right)\left( {1 + x^{\,8} + x^{\,16} + \cdots } \right) = \sum\limits_{0\, \leqslant \,n} {s_{\,n} x^{\,n} } $$ which is the generating function for the number of ways $s_n$ to compose the sum $n$, and in general you have that the number of ways to to compose the sum $n$ through (unrestriceted number of) pieces of value $a,b,c,\cdots$ is $$ \bbox[lightyellow] { f(x) = \frac{1} {{\left( {1 - x^{\,a} } \right)\left( {1 - x^b } \right)\left( {1 - x^c } \right) \cdots }} = \sum\limits_{0\, \leqslant \,n} {s_{\,n} x^{\,n} } } \tag{2}$$

The algebraic computation of the $s_n$ is quite complicated, even in the 2D case, because of involving the modular inverse operation.
Using this, the 2D case is solved through the interesting Popoviciu's Theorem, which tells that the number of solutions $s_c$ to our starting equation (1) is: $$ \bbox[lightyellow] { s_{\,c} = 1 + {c \over {ab}} - \left\{ {{{c\,b^{\,( - 1)} } \over a}} \right\} - \left\{ {{{c\,a^{\,( - 1)} } \over b}} \right\}\quad \left| \matrix{ \;b^{\,( - 1)} b \equiv 1\;\left( {\bmod a} \right) \hfill \cr \;a^{\,( - 1)} a \equiv 1\;\left( {\bmod b} \right) \hfill \cr \;\left\{ x \right\} = x - \left\lfloor x \right\rfloor \hfill \cr} \right. } \tag{3}$$

The general problem goes under the name of Frobenius Coin Problem, and you can have an exhaustive introduction in this interesting notes by Mathias Beck.