CHAP. 6] ADVANCED COUNTING TECHNIQUES, RECURSION 121
SupplementaryProblems
ADVANCED COUNTING TECHNIQUES, INCLUSION–EXCLUSION
6.13. A store sellsM=4 kinds of cookies. Find the number of ways a customer can buy:
(a) 10 cookies; (b) 15 cookies.
6.14. Find the numbermof nonnegative solutions tox+y+z=20 with the conditions thatx≥5,y≥3, andz≥1.
6.15. LetEbe the equationx+y+z=20. Find the numbermof nonnegative solutions toEwith the conditions thatx<8,
y<9,z<10.
6.16. Find the numbermof positive integers not exceeding 1000 which are not divisible by 3, 7, or 11.
6.17. Find the number of ways that 14 people can be partitioned into 6 committees, such that 2 committees contain 3 people
and the other committees contain 2 people.
6.18. Assume that a cell can be empty. Find the numbermof ways that a set:
(a) With 3 people can be partitioned into: (i) three ordered cells; (ii) three unordered cells.
(b) With 4 people can be partitioned into: (i) three ordered cells; (ii) three unordered cells.
6.19. Find the numberNof surjective (onto) functions from a setAto a setBwhere:
(a)|A|= 8 ,|B|= 3 ; (b)|A|= 6 ,|B|= 4 ; (c)|A|= 5 ,|B|= 5 ; (d)|A|= 5 ,|B|= 7.6.20. Findthenumber of derangements ofX={ 1 , 2 , 3 ,..., 2 m}such that the firstmelements of each derangement are:
(a) the firstmelements ofX; (b) the lastmelements ofX.
PIGEONHOLE PRINCIPLE
6.21. Find the minimum number of students that can be admitted to a college so that there are at least 15 students from one
of the 50 states.
6.22. Consider nine lattice points in space. Show that the midpoint of two of the points is also a lattice point.
6.23. Find an increasing subsequence of maximum length and a decreasing subsequence of maximum length in the sequence:
14, 2, 8, 3, 25, 15, 10, 20, 9, 4.
6.24. Consider a line of 50 people with distinct heights. Show there is a subline of 8 people which is either increasing or
decreasing.
6.25. Give an example of a sequence of 25 distinct integers which does not have a subsequence of 6 integers which is either
increasing or decreasing.
6.26. Suppose a teamXplays 19 games in a two-week period of 14 days, and plays at least one game per day. Show there is
a period of consecutive days thatXplayed exactly 8 games.
6.27. Suppose 10 points are chosen at random in the interior of an equilateral triangleTwhere each side has length three
inches. Show that the distance between two of the points must be less than one inch.
6.28. LetX={xi}be a set ofnpositive integers. Show that the sum of the integers of a subset ofXis divisible byn.
6.29. Consider a group of 10 people (where each pair are either friends or strangers). Show that there is either a subgroup of
4 mutual friends or a subgroup of 3 mutual strangers.
6.30. For the Ramsey numbersR(p, q)show that: (a)R(p, q)=R(q, p); (b)R(p, 1 )=1; (c)R(p, 2 )=p.
RECURSION
6.31. For each recurrence relation and initial conditions, find: (i) general solution; (ii) unique solution with the given initial
conditions:
(a)an= 3 an− 1 + 10 an− 2 ;a 0 = 5 ,a 1 = 11 (d)an= 5 an− 1 − 6 an− 2 ;a 0 = 2 ,a 1 = 8
(b)an= 4 an− 1 + 21 an− 2 ;a 0 = 9 ,a 1 = 13 (e)an= 3 an− 1 −an− 2 ;a 0 = 0 ,a 1 = 1
(c)an= 3 an− 1 − 2 an− 2 ;a 0 = 5 ,a 1 = 8 (f)an= 5 an− 1 − 3 an− 2 ;a 0 = 0 ,a 1 = 1
6.32. Repeat Problem 6.31 for the following recurrence relations and initial conditions:
(a)an= 6 an− 1 ;a 0 = 5 (c)an= 4 an− 1 − 4 an− 2 ;a 0 = 1 ,a 1 = 8
(b)an= 7 an− 1 ;a 0 = 5 (d)an= 10 an− 1 − 25 an− 2 ;a 0 = 2 ,a 1 = 15