# Puzzles

## 2001/2002 Puzzles

### 7 May 2001 (Postage Stamp)

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-11C grogs in 5-grog stamps. The number of 5-grog stamps will be Int((A-11C)/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.