5.4. State Machines 157
Inductive step: Suppose thatn 2 and thatiis a pusp for every integeriwhere
2 i < nC 1. We must show thatP.nC1/holds, namely, thatnC 1 is also a
pusp. We argue by cases:
IfnC 1 is itself prime, then it is the product of a length one sequence consisting
of itself. This sequence is unique, since by definition of prime,nC 1 has no other
prime factors. SonC 1 is a pusp, that isP.nC1/holds in this case.
Otherwise,nC 1 is not prime, which by definition meansnC 1 D kmfor
some integersk;msuch that 2 k;m < nC 1. Now by the strong induction
hypothesis, we know thatkandmare pusps. It follows that by merging the unique
prime sequences forkandm, in sorted order, we get a unique weakly decreasing
sequence of primes whose product equalsnC 1. SonC 1 is a pusp, in this case as
well.
SoP.nC1/holds in any case, which completes the proof by strong induction
thatP.n/holds for alln 2.
Problem 5.23.
Define thepotential,p.S/, of a stack of blocks,S, to bek.k 1/=2wherekis the
number of blocks inS. Define the potential,p.A/, of a set of stacks,A, to be the
sum of the potentials of the stacks inA.
Generalize Theorem 5.2.1 about scores in the stacking game to show that for any
set of stacks,A, if a sequence of moves starting withAleads to another set of stacks,
B, thenp.A/p.B/, and the score for this sequence of moves isp.A/ p.B/.
Hint:Try induction on the number of moves to get fromAtoB.
Homework Problems
Problem 5.24.
A group ofn 1 people can be divided into teams, each containing either 4 or
7 people. What are all the possible values ofn? Use induction to prove that your
answer is correct.
Problem 5.25.
The following Lemma is true, but theproof given for it below is defective. Pin-
pointexactlywhere the proof first makes an unjustified step and explain why it is
unjustified.
Lemma.For any primepand positive integersn;x 1 ;x 2 ;:::;xn, ifpjx 1 x 2 :::xn,