568 Appendix B. Mathematical Induction and the Well-Ordering Princip le

(b) Repeat the process from p art (a) to ﬁnd a formula for

1

4

+ 2

4

+ ···+ n

4

.

Then prove your formula.

(16) The Towers of Hanoi. In an ancien t city in India, so the legend goes, monks in a temple have

to move a p ile of 64 sacred disks from one location to another. The d isks are frag ile; only o ne

can be carried at a time. A disk may not be placed on top of a smaller, less valuable disk. In

addition, there is only one other locatio n in the temple (besides the original an d d estination

locations) sacre d en ough that a pile of disks can be placed there.

So the mo nks begin moving d isk s back and forth, between the original pile, the pile at the

new location, and the intermediate location, always keeping the piles in order (largest on the

bottom, smallest on the top). The legend is tha t, before the monks make the ﬁnal move to

complete the pile in the new location, the temple will turn to dust and the world will end .

Generalize this problem to show that if there were n disks to move, it would take a total of

2

n

− 1 moves to complete the transfer from one location to another. Should we be worried

about the world coming to an end?

(17) The usual total ordering given by ≤ on Z behaves nicely with respect to addition. Sh ow that

there is no total ordering of Z

n

that behaves nicely with respect to addition in Z

n

. That is,

show that there is no total ordering on Z

n

such that, for all [a], [b], [c] ∈ Z

n

, if [a] ≤ [b], then

([a] + [c]) ≤ ([b] + [c]). (Hint: If there is such an ordering with [0] ≤ [1], use transitivity to

show that [0] ≤ [n −1], and explain why this leads to a contradiction. Then think about wh a t

similar argument needs to be made to complete the proof.)

Get *Abstract Algebra* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.