Answer:
21 stamps: 16 8-cent stamps; 5 5-cent stamps
Explanation:
You want the minimum number of 5-cent and 8-cent stamps that can provide $1.53 in postage.
Ad hoc method
We know that a value of $0.40 can be achieved with either 8 5-cent stamps of 5 8-cent stamps. The minimum stamp count will use five 8-cent stamps for each $0.40.
$1.53/$0.40 = 3 remainder $0.33.
This remaining $0.33 amount is not divisible by $0.05. We can add 8-cent stamps to the 15 we already have, then check to see if the result is divisible by $0.05.
$0.33 -0.08 = $0.25, which is 5 × $0.05
So, our stamp count is 5·3 + 1 = 16 8-cent stamps and 5 5-cent stamps, for a total of 21 stamps.
Extended Euclidean algorithm
More formally, the problem can be written as a Diophantine equation. That is, we want to find coefficients x and y such that 8x +5y = 153. We can use the (recursive) Extended Euclidean algorithm to find the values of x and y.
The algorithm can be formulated as ...
define L(i) = {(a, b), (c, d), (e, g)} — a set of 3 ordered pairs
The algorithm will start with an initial set and transform it at each stage until b = 0.
L(1) = {(8, 5), (1, 0), (0, 1)}
The transformation to produce L(i+1) is ...
L(i) ⇒ L(i+1)
{(a, b), (c, d), (e, g)} ⇒ {(b, a -qb), (d, c -qd), (g, e -qg)} . . . where q = ⌊a/b⌋
Executing this algorithm, we get ...
{(8, 5), (1, 0), (0, 1)} ⇒ {(5, 3), (0, 1), (1, -1)} . . . . q = 1
{(5, 3), (0, 1), (1, -1)} ⇒ {(3, 2), (1, -1), (-1, 2)} . . . . q = 1
{(3, 2), (1, -1), (-1, 2)} ⇒ {(2, 1), (-1, 2), (2, -3)} . . . . q = 1
{(2, 1), (-1, 2), (2, -3)} ⇒ {(1, 0), (2, -5), (-3, 8)} . . . . q = 2; stop when b=0
Then the solution to the original Diophantine equation is ...
x = 153c +5n = 153(2) +5n = 306 +5n
y = 153e -8n = 153(-3) -8n = -459 -8n
From here, we want to find the minimum positive sum x+y, such that both x and y are positive.
306 +5n > 0 ⇒ n > -61.2
-459 -8n > 0 ⇒ n < -57.375
The total number of stamps is (306 +5n) +(-459 -8n) = 153 -3n. This will be minimized when n is as large as possible: -58. Then the numbers of stamps are ...
x = # of 8-cent stamps = 306 +5(-58) = 16
y = # of 5-cent stamps = -459 -8(-58) = 5
Total number of stamps: 16 +5 = 21
__
Additional comment
There are a number of different descriptions of the Extended Euclidean algorithm. We like this one because the steps are relatively simple, even though there's a lot to keep track of. A spreadsheet would be nice implementation vehicle. It can be less mental work to compute the negative of the quotient (k = -⌊a/b⌋), then do addition in the transformation (a+kb, for example).
Unfortunately, even after finding the solution to the Diophantine equation, there's still a fair amount of work to use that to answer the question. Ad hoc solutions tend to be easier to find for problems like this one. We're not sure exactly what "correct work" actually means in this case.
<95141404393>