The problem statement from the Ole Miss Problems of the Week page is:

The country of Zin’s monetary unit is the grog. The nation’s postal service sells only 5 grog and 11 grog stamps. Using Zin stamps, a person can make exact postage of 21 grogs with two 5-grog stamps and one 11-grog stamp. However, one cannot make exact postage of 23 grogs by using any combination of only 5-grog and 11-grog stamps. What is the greatest value in grogs that one cannot use for postage in the country of Zin?

Why, this sounds like a job for a programmable calculator. Amazingly enough, we have one, a Casio CFX-9850G or FX-7400G, right here! Let’s get to it, then.

Well, the first thing we need to do is figure out an overall control structure. Generating a postage amount and then checking if it can be made with Zin stamps seems reasonable. Assume a magic program, P050701A, that takes a postage amount in A and returns in B the postage breakdown (or 0 if there is none). The program resulting is available in a text file with .CAT file contents, or here in text form. Lines and parts of lines starting with a semicolon (“;”) are comments and are not actually entered into the calculator.

; Variables: ; A is amount of postage to make ; B is stamp combination to make postage (from P050701A) ; C is used by P050701A ; D is used by P050701A ; Symbols: ; -> is assignment arrow ; <= is less than or equal to comparison ; = is equal comparision ; _ is the display triangle 1->A ; Initialize postage amount to 1 grog While A<=500 ; Repeat for each postage amount up to 500 grogs Prog "P050701A" ; Try to make the postage If B=0 ; Test whether there is no stamp combination to ; make the postage Then A_ ; If there is none, display the postage amount IfEnd ; [End of test for stamp combinations] A+1->A ; Get the next postage amount to test WhileEnd ; [End of loop on postage amount] "Done" ; Note we are done

Now, let’s figure out how to write the magic program P050701A.
To make a postage amount *A*, we will need between 0 and
Int(*A*/11) 11-grog stamps — we can’t have fewer
than 0 11-grog stamps, and more than Int(*A*/11) 11-grog
stamps would be too many.
So we will try Int(*A*/11), then Int(*A*/11)-1, then
..., then 0 11-grog stamps.
With *C* 11-grog stamps, we need to make up the rest of the
*A*-11*C* grogs in 5-grog stamps.
The number of 5-grog stamps will be Int((*A*-11*C*)/5).
If the 11-grog stamps and 5-grog stamps together make up the amount
*A*, then we can make *A* grogs in postage; otherwise,
we try the next number of 11-grog stamps.
If we run out of 11-grog stamps before we have made the correct
amount in postage, then we cannot make *A* grogs in postage.
A program P050701 to do this computation is:

; Variables: ; A is the amount of postage to try to make ; B is the postage breakdown as 1000 times the number of 11-grog ; stamps, plus the number of 5-grog stamps (we assume we will ; be able to make postage with less than 1000 5-grog stamps) ; C is the number of 11-grog stamps being attempted ; D is the number of 5-grog stamps being attempted ; Symbols: ; -> is the assignment arrow ; / is the division operator ; = is the equal relational ; >= is the greater than or equal relational 0->B ; Assume we cannot make the proper postage Int (A/11)->C ; Get the maximum number of 11-grog stamps Do ; Repeat until we are out of possibilities or have ; a way to make postage Int ((A-11C)/5)->D ; Get the number of 5-grog stamps left when we ; use C 11-grog stamps If (11C+5D)=A ; Test whether that made exact postage Then 1000C+D->B ; If so, note the number of stamps to make ; postage IfEnd ; [End of test for exact postage] C-1->C ; Prepare for one fewer 11-grog stamps LpWhile C>=0 And B=0;[End of possibilities/postage loop]

These programs, of course, are available here in text or as a download as a text file with .CAT file contents.

And now we run the program P050701, and it displays the postage values that cannot be represented in 5- and 11-grog stamps. We put them here in columns to save space:

1 7 14 24 2 8 17 28 3 9 18 29 4 12 19 34 6 13 23 39

and then the program prints

Done

Okay, then, that is that.

Well, maybe not.
Look carefully at the second line of the first program.
See that “A<=500”?
That is a limit test on the number of grogs of postage we are trying
to make up.
So what the program does is show the postage values of less than or
equal to 500 grogs that cannot be made with 11- and 5-grog stamps.
We could, of course, just take away the limit and let the calculator
run.
But no matter how far it got without finding any more postage values
that cannot be made with 5- and 11-grog stamps, we would never be
*sure* that there was not another value out there that could
not be made with 5- and 11-grog stamps.
Maybe the next value would be the one that could not be made with
5- and 11-grog stamps.

Sigh.
We have to *think* again.
How very annoying.

Suppose we have some amount *A* in stamps.
If we take away two 5-grog stamps and add in one 11-grog stamps, we
have made up *A*+1 grogs in stamps.
This assumes, of course, there are two 5-grog stamps to take away.
Now, we can get 40 grogs with 8 5-grog stamps; 41 with 6 5-grog stamps
and one 11-grog stamp; 42 with 4 and 2; 43 with 2 and 3; and 44 with
0 5-grog stamps and 4 11-grog stamps.
At 45 grogs, we can use 9 5-grog stamps, and so get to 49 with 1
5-grog stamp and 4 11-grog stamps.
At 50 grogs, we can start with 10 5-grog stamps, and so on.
We can keep this up — counting by 5-grog units —
forever.
So we can, in fact, make *any* amount of postage of 40 or
more grogs with 5- and 11-grog stamps.

So 39 grogs actually is the largest amount of postage we could need which we could not make with only 5- and 11-grog stamps.

[ Previous page | Top of page | Next page ]

Copyright © 2001 Brian Hetrick

Page last updated 25 November 2001.