Mathematics for Computer Science

5.4. State Machines 159

Problem 5.28.
A class of any size of 18 or more can be assembled from student teams of sizes 4
and 7. Prove this byinduction(of some kind), using the induction hypothesis:

S.n/WWDa class ofnC 18 students can be assembled from teams of sizes 4 and 7:

Problem 5.29.
Any amount of ten or more cents postage that is a multiple of five can be made
using only 10¢ and 15¢ stamps. Prove thisby induction(ordinary or strong, but say
which) using the induction hypothesis

S.n/WWD.5nC10/¢ postage can be made using only 10¢ and 15¢ stamps:

Problems for Section 5.4

Practice Problems

Problem 5.30.
Which states of the Die Hard 3 machine below have transitions to exactly two
states?

Die Hard Transitions

1. Fill the little jug:.b;l/!.b;3/forl < 3.


2. Fill the big jug:.b;l/!.5;l/forb < 5.


3. Empty the little jug:.b;l/!.b;0/forl > 0.


4. Empty the big jug:.b;l/!.0;l/forb > 0.


5. Pour from the little jug into the big jug: forl > 0,

.b;l/!

(

.bCl;0/ ifbCl 5 ,

.5;l.5b// otherwise.

6. Pour from big jug into little jug: forb > 0,

.b;l/!

(

.0;bCl/ ifbCl 3 ,

.b.3l/;3/ otherwise.