Chapter 5 Induction170
Exam Problems
Problem 5.42.
There is a bucket containing more blue balls than red balls. As long as there are
more blues than reds, any one of the following rules may be applied to add and/or
remove balls from the bucket:
(i) Add a red ball.(ii) Remove a blue ball.(iii) Add two reds and one blue.(iv) Remove two blues and one red.(a)Starting with 10 reds and 16 blues, what is the largest number of balls the
bucket will contain by applying these rules?
Letbbe the number of blue balls andrbe the number of red balls in the bucket
at any given time.
(b)Prove thatb r 0 is a preserved invariant of the process of adding and
removing balls according to rules (i)–(iv).
(c)Prove that no matter how many balls the bucket contains, repeatedly applying
rules (i)–(iv) will eventually lead to a state where no further rule can be applied.
Problem 5.43.
The following problem is a twist on the Fifteen-Puzzle problem that we did in class.
LetAbe a sequence consisting of the numbers1;:::;nin some order. A pair
of integers inAis called anout-of-order pairwhen the first element of the pair
both comesearlierin the sequence, andis larger, than the second element of the
pair. For example, the sequence.1;2;4;5;3/has two out-of-order pairs: .4;3/
and.5;3/. We lett.A/equal the number of out-of-order pairs inA. For example,
t..1;2;4;5;3//D 2.
The elements inAcan be rearranged using theRotate-Tripleoperation, in which
three consecutive elements ofAare rotated to move the smallest of them to be first.
For example, in the sequence.2;4;1;5;3/, theRotate-Tripleoperation could
rotate the consecutive numbers4;1;5, into1;5;4so that
.2;4;1;5;3/ !.2;1;5;4;3/: