Mathematics for Computer Science

Chapter 5 Induction160

Problem 5.31.
Prove that every amount of postage of 12 cents or more can be formed using just
4-cent and 5-cent stamps.

Homework Problems

Problem 5.32.
In the late 1960s, the military junta that ousted the government of the small re-
public of Nerdia completely outlawed built-in multiplication operations, and also
forbade division by any number other than 3. Fortunately, a young dissident found
a way to help the population multiply any two nonnegative integers without risking
persecution by the junta. The procedure he taught people is:

proceduremultiply.x;y: nonnegative integers/
rWDx;
sWDy;
aWD 0 ;
whiles¤ 0 do
if 3 jsthen
rWDrCrCr;
sWDs=3;
else if 3 j.s1/then
aWDaCr;
rWDrCrCr;
sWD.s1/=3;
else
aWDaCrCr;
rWDrCrCr;
sWD.s2/=3;
returna;

We can model the algorithm as a state machine whose states are triples of non-
negative integers.r;s;a/. The initial state is.x;y;0/. The transitions are given by
the rule that fors > 0:

.r;s;a/!

8

ˆ<

ˆ:

.3r;s=3;a/ if 3 js
.3r;.s1/=3;aCr/ if 3 j.s1/
.3r;.s2/=3;aC2r/ otherwise:
(a)List the sequence of steps that appears in the execution of the algorithm for
inputsxD 5 andyD 10.