Problem Set 5
MA221 Discrete Mathematics
Date: Oct 20, 2024
1. (a) Suppose a soccer team scores at least one goal in 20 consecutive games. If it
scores a total of 30 goals in those 20 games, prove that in some sequence of
consecutive games it scores exactly 9 goals.
(b) In how many ways can a party of 4 men and 4 women be seated at a circular
table so that no two women are adjacent?
n−1
(c) Show that there are distinct positive integer-valued vectors (x1 , · · · , xk )
k−1
satisfying
x1 + x2 + · · · + xk = n, xi > 0 for all i = 1, · · · , k
(d) How many positive integers not exceeding 2001 are multiples of 3 or 4 but not
5?
(e) Determine the number of ways to choose five numbers from the first eighteen
positive integers such that any two chosen numbers differ by at least 2?
(f) Nine chairs in a row are to be occupied by six students and Professors Alpha,
Beta and Gamma. These three professors arrive before the six students and
decide to choose their chairs so that each professor will be between two students.
In how many ways can Professors Alpha, Beta and Gamma choose their chairs?
(g) Prove that among any 16 distinct positive integers not exceeding 100 there are
four different ones a, b, c, d such that a + b = c + d.
(h) Show that whenever 25 girls and 25 boys are seated around a circular table
there is always a person both of whose neighbors are boys.
(i) There are 38 different time periods during which classes at a university can be
scheduled. If there are 677 different classes, how many different rooms will be
needed?
(j) How many ways are there to pack eight identical DVDs in to five indistinguish-
able boxes so that each box contains at least one DVD?
(k) Solve the recurrence relation T (n) = nT 2 ( n2 ) with initial condition T (1) = 6
when n = 2k for some integer k. [Hint: Let n = 2k and then make the substi-
tution ak = log T (2k ) to obtain a linear nonhomogeneous recurrence relation.]
(l) Find a recurrence relation and give initial conditions for the number of bit
strings of length n that do not have two consecutive 0s. How many such bit
strings are there of length five?
(m) The French mathematician Edouard Lucas, called the Tower of Hanoi, consists
of three pegs mounted on a board together with disks of different sizes. Initially
these disks are placed on the first peg in order of size, with the largest on the
bottom. The rules of the puzzle allow disks to be moved one at a time from
one peg to another as long as a disk is never placed on top of a smaller disk.
The goal of the puzzle is to have all the disks on the second peg in order of size,
with the largest on the bottom. Let Hn denote the number of moves needed to
solve the Tower of Hanoi puzzle with n disks. Set up a recurrence relation for
the sequence Hn .
(n) Solve the following questions:
(i) Find a recurrence relation for the number of ternary strings of length n that
do not contain two consecutive 0s or two consecutive 1s.
(ii) What are the initial conditions?
(iii) How many ternary strings of length six do not contain two consecutive 0s
or two consecutive 1s?
(o) Consider the non-homogeneous linear recurrence relation an = 3an−1 + 2n
(i) Show that an = n2n is a solution of the recurrence relation.
(ii) Find all the solution of this recurrence relation.
(iii) Find the solution with a0 = 2.
(p) What is the general form of the particular solution guaranteed to exist of the
non-linear homogeneous recurrence relation an = 6an−1 −12an−2 +8an−3 +F (n)
if
(i) F (n) = n2 (ii) F (n) = 2n
(iii) F (n) = n2 2n (iv) F (n) = 3
(q) Find all solutions of the recurrence relation an = 5an−1 − 6an−2 + 2n + 3n.
(r) Find all solutions of the recurrence relation an = 4an−1 − 4an−2 + (n + 1)2n .
(s) Find the solution of the recurrence relation an = 4an−1 − 3an−2 + 2n + n + 3
with a0 = 1 and a1 = 4.
Best wishes
Page 2