Discrete Mathematics (2016-17)

Exercises
Although this listing contains some original exercises the vast majority of the exercises included here have been copied from other sources (in particular, the books [3, 1, 4, 2]). Some
exercises, marked with the symbol ('), have a higher degree of difficulty. Some of the exercises
in this listing will not be solved in class. They are included here so that the student can do some
extra practice.

Propositional logic. Syntaxis and logical equivalence

You can find more exercises about this topic in sections 1.1 and 1.2 in [3]. You might also solve
the exercises in sections 1.1 and 1.2 in [4].
1. Let p, q, and r be the propositions:
p: You get a 10 on the final exam.
q: You do every exercise in this book.
r: You get a 10 in this class.
Write the following propositions using p, q, and r and logical connectives
(a) You get a 10 in class, but you do not do every exercise in this book.
(b) You get a 10 in the final, you do every exercise in this book, and you get a 10 in this class.
(c) To get a 10 in this class, it is necessary for you to get a 10 on the final.
(d) You get a 10 on the final, but you dont do every exercise in this book; nevertheless, you
get a 10 in this class.
(e) Getting a 10 on the final and doing every exercise in this book is sufficient for getting a 10
in this class.
(f) You will get a 10 in this class if and only if you either do every exercise in this book or you
get a 10 on the final.
2. State the converse, contrapositive and inverse of each of these implications:
(a) If it snows today, I will ski tomorrow.
(b) I come to class whenever there is going to be a exam.
(c) A positive integer is a prime only if it has no divisors other than 1 and itself.
3. Construct a truth-table for each of these propositions:
(a) p p
(b) p p
(c) p (p q)
(d) (p q) (p q)
1

(e) (p q) (q p)
(f) (p q) (q p)
4. Four friends have been identified as suspects for an unauthorized access to a computer system.
They have made statements to the investigating authorities. Alice said Carlos dit it. John said
I did not do it. Carlos said Diana did it. Diana said Carlos lied when he said that I did it.
(a) Assume that the authorities know that exactly one of the four suspects is telling the truth.
Who did it?
(b) Assume that the authorities know that exactly one of the four suspects is lying. Who did
it?
Explain your reasoning.
5. Show that each of the these implications is a tautology by using truth tables:
(a) (p (p q)) q
(b) ((p q) (q r)) (p r)
(c) (p (p q)) q)

onlyn way not

abtautology is when..

(d) ((p q) (p r) (q r)) r

6. Find a formula involving the connectives , , and that has the following truth table
P
F
F
T
T

Q
F
T
F
T

???
T
F
T
T

p or (not
q and p)

7. Show that each implication in exercise 5 is a tautology without using truth tables. As an
example, we shall show that the first implication is a tautology
(a) We need to see that every assignment of p and q that makes the antecedent (p (p q))
of the implication true must also make the consequent, q, true. Assume then that we have
an assignment such that the antecedent (p (p q)) is true. It follows that p and p q
are true. If p is true it follows that p is false. Now, if p q is true and p is false it follows
that q is true. Since q is the consequent we are done.
8. Show that (p q) r and p (q r) are not logically equivalent.
9. Show that (p q) (p r) and p (q r) are logically equivalent.
10. Note that the associative laws say only that parentheses are unnecessary when combining
three statements with or . In fact, these laws can be used to justify leaving parentheses
out when more than three statements are combined. Use the associative laws to show that
(P (Q R)) S is equivalent to (P Q) (R S)
11. How many lines will there be in the truth table for a statement containing n propositional
variables?
12. (') Use the first De Morgans law and the double negation law to prove the second De
Morgans law
2

Propositional logic. Deduction

You can find more exercises about this topic in sections 1.2.1-1.2.3 of [2].
13. Prove the sequent
(p q) r ` p (q r)
14. Prove the sequent
(q (p r)), r, q ` p
15. Prove the sequent
p ` q (p q)
16. Prove the sequent
p q, p r, q r ` r
17. Prove the sequent
(p r) (q r) ` (p q) r
18. Prove the sequent
q r ` (p q) (p r)
19. Prove the sequent
p q, r s ` p r q s
20. Prove the sequent
p q ` r ((p q) r)
21. Prove the sequent
p q, r s ` p r q s
22. Prove the sequent
p q r ` (p q) (p r)
23. Prove the sequent
p (p q) ` p
24. Prove the sequent
p (q r), q s, r s ` p s
25. Prove the sequent
` (p q) p
26. Prove the sequent
(p (r q)) ((p (r q)) (q p)) ` (q p)
27. Prove the sequent
p ` (p q) q
28. Prove the sequent
p (q r), p q ` p r
29. Prove the sequent
(p (q p)) q ` p
3

30. Prove the sequent

(p q) ` ((p q) p) (p (p q))
31. Prove the sequent
p q ` q p
32. Prove the sequent
r, p (r q) ` p (q r)
33. Prove the sequent
(p q) (p r) ` p (q r)
34. (')Prove the sequent
p ` p q
This proof is hard to find without some rules that we will introduce the next theory session.
(Hint: note that if we could derive q p then we could derive p q by adapting the proof
in exercise 31.)
35. Prove these sequents without using the MT rule:
(a) p q ` q p
(b) p q ` (p q)
(c) p, p q ` q
(d) p q, q r ` p r
(e) p (q r), q, r ` p
(f) p q ` (p q)
(g) p p ` (r q) (r q)
(h) (p q) ` p
36. Prove the following sequents:
(a) p q ` (p q)
(b) ` (p q) (q r)
(c) (')` ((p q) q) ((q p) p)
(d) ` (p q) ((p q) q)

Predicates and Quantification

You can find more exercises about this topic in [3] (sections 1.3 and 1.4) and [4] (sections 2.1
and 2.2).
37. Let T (x, y) be the predicate expressing
student x likes cuisine y

where the universe of discourse for x consists of all students at your school and the universe of y
consists of all cuisines. Express each one of these statements by a simple sentence using natural
language:
(a) T (Abdallah Hussein, Japanese)
(b) x T (x, Korean) x T (x, Mexican)
(c) y (T (Monique Arsenault, y) T (Jay Johnson, y)
(d) xzy ((x 6= z) (T (x, y) T (z, y)))
(e) xzy (T (x, y) T (z, y))
(f) xzy (T (x, y) T (z, y))
38. Let Q(x, y) be the predicate expressing
student x has been a contestant on tv show y
where the universe of discourse for x consists of all students at your school and the universe for y
consists of all tv shows on television. Express each one of the following sentences using Q(x, y),
quantifiers and logical connectives:
(a) There is an student at your school that has been a contestant on a tv show.
(b) No student at your school has ever been a contestant on a tv show.
(c) There is a student at your school that has been a contestant on Gran Hermano and on
Operaci
on Triunfo.
(d) At least two students from your school have been contestants on Gran Hermano.
39. Determine the truth value of each of these statements if the universe of discourse for all
variables consists of all integers:
(a) nm(n2 < m)
(b) nm(n < m2 )
(c) nm(n + m = 0)
(d) nm(nm = m)
(e) nm(n2 + m2 = 5)
(f) nm(n2 + m2 = 6)
(g) nm(n + m = 4 n m = 1)
(h) nm(n + m = 4 n m = 2)
(i) nmp(p = (m + n)/2)
40. Rewrite each of these statements so that negations appear only within predicates (that is,
so that no negation is outside a quantifier or an expression involving logical connectives)
(a) xyP (x, y)
5

(b) yxP (x, y)

(c) yx(P (x, y) Q(x, y))
(d) (xyP (x, y) xyQ(x, y))
(e) x(yzP (x, y, z) zyP (x, y, x))
41. Let S(x) be the predicate x is a student, F (x) be the predicate x is a professor and A(x, y)
be the predicate x has asked y a question, where the universe of discourse consists of all people
associated with your school. Use quantifiers to express each of these statements:
(a) Lois has asked professor Michaels a question.
(b) Every student has asked professor Gross a question.
(c) Every professor has either asked professor Miller a question or been asked a question by
professor Miller.
(d) Some student has not asked any professor a question.
(e) There is a professor who has never been asked a question by a student.
(f) Some student has asked every professor a question.
(g) There is a professor who has asked every other professor a question.
(h) Some student has never been asked a question by a professor.
42. (')Determine which of the following equivalences are true and which are false. Justify your
answers:
(a) Is xyP (x, y) equivalent to xyP (x, y)?
(b) Is xP (x) xQ(x) equivalent to x(P (x) Q(x))?
(c) Is xP (x) xQ(x) equivalent to x(P (x) Q(x))?
(d) Is xP (x) xP (x) equivalent to xy(P (x) Q(y))?
43. (')Determine which of the following equivalences are true and which are false. Justify your
answers:
(a) Is xP (x) xQ(x) equivalent to xy(P (x) Q(y))?
(b) Is xP (x) xQ(x) equivalent to xy(P (x) Q(y))?
44. Let L(x, y) be the predicate
x likes y
where the universe of discourse is the set of students in class. Express the following sentences
using L, quantifiers, and logical connectives:
(a) Every student likes at least two students.
(b) (')Carla likes exactly one student.
(c) Everyone likes someone that does not like anybody
6

(Hint: You can use x = y to indicate that x is equal to y).

45. (')Consider the sentence Everyone has a relative he does not like. This sentence can
be expressed as xy(R(x, y) L(x, y)) where R and L are the predicates that express the
relationship relative and likes respectively. But this is not the only way. Another, perhaps
less obvious way, to express the previous sentence is xy(R(x, y) L(x, y)). Show that both
logical statements are equivalent.
46. (') In class we have seen two quantification elimination laws. The first law states that
xP (x) is equivalent to xP (x) and the second law states that xP (x) is equivalent to
xP (x). Show that each one of these laws can be derived from the other. (Hint: Use the
double negation law).

Sets
You can find more exercises about this topic in [3] (sections 1.6 and 1.7) and [4] (sections 1.4
and 2.3).
47. Let A = {1, 2, 3, 4, 5} and B = {0, 3, 6}. Find:
(a) A B
(b) A B
(c) A B
(d) B A
(e) P(B)
48. Determine whether each of the following statements is true of false.
(a) x {x}
(b) {x} {x}
(c) {x} {x}
(d) {x}, {{x}}
(e) {x}
(f) {x}
(g) P({x})
(h) {x} P({x})
(i) {x} P(P({x}))
(j) P(P({x}))
(k) {{x}} P(P({x}))
(l) {{x}, } P(P({x}))
49. Let A and B sets. Using membership tables show that:
7

(a) A (A B) = A
(b) (A B) A
(c) A (A B)
(d) A B A
(e) A (B A) =
(f) A (B A) = A B
50. Let Ai = { , 2, 1, 0, 1, . . . , i} for i = 1, 2, 3, . . . . Find:
Sn
(a) i=1 Ai
Tn
(b) i=1 Ai
51. Let A, B, and C sets. Show that
A (B C) = (C B) A)
without using membership tables. Instead, show the identity by combining some the identities
that have been seen in class.

Basic proof strategies

You can find more exercises about this topic in [4] (section 3), [3] (section 1.5), and [1] (sections
3.1-3.4).
52. Suppose that a and b are real numbers. Prove that if a < b then

a+b
2

<b

53. Suppose that a, b, c, and d are real numbers, 0 < a < b and d > 0. Prove that if ac bd
then c > d
54. Consider the following incorrect theorem:
Incorrect theorem: Suppose x and y are real numbers and x + y = 10. Then x 6= 3 and y 6= 8.
(a) Whats wrong with the following proof of the theorem?
Proof: Suppose the conclusion of the theorem is false. Then x = 3 and y = 8. But
then x + y = 11, which contradicts the given information that x + y = 10. Therefore the
conclusion must be true.
(b) Show that the theorem is incorrect giving a counterexample.
55. Suppose that A B, a A, and a 6 B \ C. Prove that a C.
56. Prove that if A B \ C then A and C are disjoint.
57. Prove that for every real number x, if x > 2 there is a real number y such that y + 1/y = x.
58. Prove that if F is a collection of sets and A F then F A.
59. An integer number n is even if there exists an integer k such that n = 2k and it is odd if
there is an integer k such that n = 2k + 1. Prove that if an integer n is even then n2 is even.
8

60. Let n be an integer. Prove that if 3n + 2 is odd then n is odd. (Hint: Try to prove the
contrapositive)
61. Consider the following theorem:
Theorem: For every real number x, x2 0.
Whats wrong with the following proof of the theorem?
Proof: Suppose not. Then, for every real number x, x2 < 0. In particular plugging in x = 3
we would get 9 < 0, which is clearly false. This contradiction shows that for every number x,
x2 0.
62. Consider the following incorrect theorem:
Incorrect theorem: x R y R(xy 2 = y x).
Whats wrong with the following proof of the theorem?
Proof: Let x = y/(y 2 + 1). Then
yx=y

y
y3
y
=
= 2
y 2 = xy 2
y2 + 1
y2 + 1
y +1

63. Suppose that a and b are nonzero real numbers. Prove that if a < 1/a < b < 1/b then
a < 1.
64. Prove that if x(P (x) Q(x)) is true then xP (x) xQ(x) is true.
65. Prove that for every integer n, if n2 is even then n is even.
66. A real number x is rational if there exists integers p, q such that x = p/q. Prove that if x
and y are rational numbers then xy is a rational number.
67. Suppose that F and G are families of sets. Prove that if F G then F G.
68. Prove that for every real number x there is a real number y such that for every real number
z, yz = (x + z)2 (x + z)2 .
69. Supose that B is a set and F is a family of sets. Prove that if F B then F P(B)
70. Suppose that F and G are families of sets and that every element of F is a subset of every
element of G. Prove that F G.
71. Prove that nm(m > n2 ) where the universe of discourse is the set of natural numbers.
72. An integer k is a perfect square if there exist an integer k such that n = k 2 . Assume that
we want to prove the following theorem:
Theorem: For every positive integer m there is a positive integer n such that mn + 1 is a perfect
square.
(a) Try to prove the statement. The proof is not easy and later we will give you some hint but
it is nice that you try a little bit before continuing.
(b) The following proof has a mistake. Can you find it?
Proof: Proof: Let m be any arbitrary positive integer and let n =
2
m mm1 + 1 = m2 which is a perfect square.
9

m2 1
m .

Then mn + 1 =

(c) Now we want you to give a correct proof. In the previous proof we tried to define n such
that mn + 1 is m2 but if you think about it the choice of m2 is arbitrary. We could as
well have chosen (m + 1)2 or any other perfect square. Try to define n such that mn + 1
is always (m + 1)2 .
(d) (')Prove that for every positive integer m there is a positive integer n such that mn + 8
is a perfect cube.
73. In exercise 43 we have seen informally that x(P (x) Q(x)) and xP (x) xQ(x) are
equivalent. Now we are ready to give a formal proof of the previous equivalence, so we ask you
prove that (x(P (x) Q(x))) (xP (x) xQ(x))
74. Prove that the sum of an irrational number and a rational number is irrational using a proof
by contradiction.
75. Prove that if A B and A 6 C then B 6 C
76. (')Suppose A C B C and A C B C. Prove that A B.
77. Let A, B, and C sets. Prove that A \ C (A \ B) (\C)
78. Prove that an integer n is odd if and only if n2 is odd.
79. Prove that if x and y are real numbers then max(x, y) + min(x, y) = x + y. (Hint: Use a
proof by cases, with the two cases corresponding to x y and x < y respectively)
80. Prove the triangle inequality that states that if x and y are real numbers then |x|+|y| |x+y|
(where |x| represents the absolute value of x)
81. Let m and n integers. Prove that:
(a) m + n is even if and only if both m and n are even or both m and n are odd.
(b) mn is even if and only m or n are even.
82. Prove the following statement
If n and m are integers such that n2 + m2 is even then n + m is even.
83. Prove that there are 100 consecutive positive integers that are not perfect squares. Is your
proof constructive or nonconstructive?
84. Prove that either 2 10500 + 15 or 2 10500 + 16 is not a perfect square. Is your proof
constructive or nonconstructive? (Hint: do not try to evaluate those numbers)
85. Show that if a and b are odd integers with a 6= b then there is a unique integer c such that
|a c| = |b c|.
86. Prove that x R(y R(x + y = xy) x 6= 1)
87. (')Suppose A, B, and C are sets. Prove that A (B C) (A B) C.
88. Prove that for every real number x, if |x 3| > 3 then x2 > 6x. (Hint: Break the proof into
cases. Assume that x 3 0 in case 1 and that x 3 < 0 in case 2.)
89. Prove that for every real number x, |2x 6| > x if and only if |x 4| > 2.
10

90. Use a proof by cases to show that min(a, min(b, c)) = min(min(a, b), c) whenever a, b, and c
are real numbers.
91. (') Prove that the last digit of square of a integer cannot be a 2. (Hint: Let n be the an
integer and let l be its last digit. Then n = 10k + l for some k. Do a proof by cases depending
on the value of l)
92. Prove that n2 + 5n + 3 is odd for every integer number n.
93. (')Prove that at least one of the real numbers a, b, c is greater or equal to the average of
these numbers.
94. For any real number x we shall denote by bxc the largest integer that is less than or equal
to x. Prove bn/2cbn/2c = bn2 /4c for all integers n.
95. Show that the product of two of the numbers 651000 82001 + 3177 , 791212 92323 + 22001
and 244493 58192 + 71777 is nonnegative.
96. Show that if n is an odd integer then there is a unique integer k such that n is the sum of
k 2 and k + 3.
97. Prove that for every real number x there is a unique real number y such that x2 y = x y.
98. Let P (x) be the predicate
student x does all the homework
where the universe of discourse consists of all students in class.
(a) Write a logical sentence that expresses the statement
there is a student such that if this student does the homework then all the students in the
class also do the homework
(b) (')The previous statement is true (although it might appear false at first glance). Prove
it.

Integer Division
You can find more exercises about this topic in [3] (sections 2.4 and 2.6). You might also solve
the exercises in [1] (section 4.1).
99. Show that if a|b and b|a where a and b are integers, then a = b or a = b
100. Show that if a|c and b|d where a, b, c, and d are integers, then ab|cd
101. What are the quotient and remainder when
(a) 777 is divided by 21?
(b) 123 is divided by 19?
(c) 1 is divided by 23?
102. (')
11

(a) Prove that if n is an odd number then n then there exists some q such that n = 4q + 1 or
n = 4q + 3 (Hint: Use the division theorem)
(b) Prove that if n is an odd number then 8|(n2 1) (Hint: Use the result shown in (a))
103. Are these integers primes?
(a) 19
(b) 27
(c) 93
(d) 101
(e) 107
(f) 113
104. Find the prime factorization of each of these integers:
(a) 39
(b) 81
(c) 101
(d) 143
(e) 289
(f) 899
105. Which positive integers less than 30 are relatively prime to 30?
106. What are the greatest common divisors and the least common multiple of these pairs of
integers?
(a) 37 53 73 , 211 35 59
(b) 2331 , 2317
(c) 41 43 53, 41 43 53
(d) 313 517 , 212 721 .
(e) 1111, 0
107. Decide whether each one of these integers is congruent with 5 modulo 17.
(a) 80
(b) 103
(c) -29
(d) -122

12

108. Show that if n|m where n and m are positive integers and a b (mod m) where a and b
are integers then a b (mod n).
109. Show that if a, b, c, m are integers such that c, m > 0 and a b (mod m), then ca
bc (mod cm).
110. (')Prove that for every integer n, at least one of the integers n, n + 2, n + 4 is divisible
by 3
111. Let a, m integers where m > 0. We say that an integer b is the inverse of a modulo m if
ab 1 (mod m). For example 3 is the inverse of 2 modulo 5 because 2 3 1 (mod 5).
(a) Find an inverse of 4 modulo 7.
(b) Find an inverse of 4 modulo 5.
(c) Inverses are very useful to solve equations of the form ax b (mod m). Such type of
equations are called linear. For example, assume that we want to solve the equation
13x 61 (mod 2436). If you think about it, it is not entirely obvious how to solve such
equation. Think a little bit about it before continuing.
(d) Now assume that we know that the inverse of 13 modulo 2436 (you can verify it) is 937.
Now we can solve the previous equation. Can you do it?
(e) Does every number have an inverse modulo 7?
(f) Does every number have an inverse modulo 6?
112. (')The goal of this exercise is to understand under which conditions an integer a has an
inverse modulo m. Before trying this exercise you must have understood very well the solution
of Exercise 111.
(a) Prove that if a and m are relatively primes then a has an inverse b modulo m. (Hint: Use
Bezouts identity)
(b) Prove that the inverse b is unique modulo m. That is, for any other inverse c of a modulo
m we have that b c (mod m).
113. Prove that if a, b are relative prime positive integers then mcm(a, b) = a b.
114. Say whether each of the following is true or false for all positive integers a, b, c, d, m. Prove
your answers.
(a) If a|bc then a|b or a|c.
(b) If a|c and b|c then ab|c.
(c) (')If a|c and b|c then mcm(a, b)|c.
(d) If a b (mod m) then ak bk (mod m) for every positive integer k.
(e) If ac bc (mod m) then a b (mod m)
115. (')Prove that the sum of five consecutive integers is divisible by 5. (Hint: use the division
theorem).
116. (')How many zeros are at the end of 100!?
13

117. (')Prove that if a is an odd integer then 24|a(a2 1). (Hint: Exercises 102 and 114(c)
might be useful)
118. (')Prove that if a, b are positive integers then mcd(a, b) = mcd(b, r) where r is the remainder of the division of a by b. (Hint: Show that the common divisors of a and b are the same as
the common divisors of b and r)
119. (')Prove that if a and m are not relatively prime then a does not have an inverse modulo
m. Before trying this exercise you must have understood well the solution of Exercise 111
120. We would like to identify positive integers m such that every integer has an inverse modulo
m. What could you say about the integers m satisfying this condition?

Induction and Recursion

You can find more exercises about this topic in [3] (sections 3.3 and 3.4). You might also solve
the exercises in [4] (section 6) and [1] (section 3.5).
121. Find a formula for

1
1
1
+
+ +
12 23
n(n + 1)

by examining the values of this expression for small values of n. Use mathematical induction to
prove your result.
122. Show that 12 +22 + +n2 = n(n+1)(2n+1)/6 for every positive integer n using induction.
123. Show that 12 + 32 + 52 + (2n + 1)2 = (n + 1)(2n + 1)(2n + 3)/3 for every positive integer
n using induction.
124. Prove that 3n < n! whenever n is an integer greater than 3.
125. Show that 12 22 + 32 + (1)n1 n2 = (1)n1 n(n + 1)/2 whenever n is a positive
integer.
126.

(a) Show, using strong induction, that any postage that is a positive integer number of
cents greater than 7 can be formed using just 3-cent stamps and 5-cent stamps.

(b) Determine which amounts of postage can be formed using just 5-cent and 6-cent stamps.
Prove your answer using induction.
127. Prove that 1 +

1
4

1
9

++

1
n2

< 2 1/n whenever n is a positive integer greater than 1.

128. Give a recursive definition of

(a) the set of positive integers
(b) the set of positive integers powers of 3
(c) the set of positive integers congruent to 2 modulo 3
(d) the set of positive integers not divisible by 5
129. Let S be the set of integers defined recursively by:
BASIC STEP: 6 S and 8 S
RECURSIVE STEP: If a, b S then a + b S (Note that a and b are not necessarily different).

14

(a) Use structural induction to show that every element of S is even.

(b) Use strong induction to show that every even integer greater than 10 belongs to S.
130. (')Let an be the number of bit strings of length n that do not have two consecutive 0s.
(a) Give a recursive definition of an .
(b) What is the value of a5 ?
131. The function ones(s) counts the number of ones in a bit string s. For example ones(11011) =
4 and ones(1000101) = 3. Give a recursive definition of the function ones(s) (Hint: Adapt the
recursive definition of length(s) given in class).
132. Describe the set of strings that belong to the set A defined recursively as follows
BASIC STEP: A
RECURSIVE STEP: If x A then 0x1 A.
133. Describe the set of strings that belong to the set A defined recursively as follows
BASIC STEP: A, 1 A
RECURSIVE STEP: If x A then 0x A and x0 A.
134. A sequence a0 , a1 , . . . is defined recursively by the equations a0 = 0, and
an = 2an1 + n
Prove that an = 2n n + 1 for every n 0.
135. (')Solve Exercise 102 using mathematical induction.
136. (')Show by mathematical induction that if h > 1 then 1 + nh (1 + h)n for all
nonnegative integers. This is called Bernouillis inequality.
137. Consider an inductive definition of a version of Ackermanns function. This function,
which was named after a great mathematician called Wilhelm Ackermann, plays a role in theory
of computing and the study of certain data-structure algorithms. (There are several different
variants of this function).

2n
if m = 0

0
if m 1 and n = 0
A(m, n) =
2
if m 1 and n = 1

A(m 1, A(m, n 1) if m 1 and n 2

(a) Find these values of Ackermanns function: A(1, 0), A(0, 1), A(1, 1), A(2, 2).
(b) Show that A(1, n) = 2n for every n 1.
(c) Find these values of Ackermanns function: A(2, 3), (')A(3, 3).
138. Let S be the set of integers defined recursively by:
BASIC STEP: 9 S and 21 S
RECURSIVE STEP: If a, b S then a b S. (Note that a and b do not need to be necessarily
different)

15

(a) Use structural induction to show that every element of S is divisible by 3.

(b) (')Prove that S contains every integer divisible by 3 (Hint: Start showing that 3 S and
use this fact in your proof).
139. The reversal of a string is the string consisting of the symbols of the string in reverse order.
(a) Find the reversal of the following bit strings: 0101, 11011, 100010010111,
(b) (')Give a recursive definition of the function rev(s) that returns the reversal of string s.
(Hint: Try to adapt the definition of function length seen in class)
140. (')A bit string is a palindrome if it is equal to its reversal. For example 00100, and 1001
are palindromes whereas 011 is not. Give a recursive definition of the set of bit strings that are
palindromes.
141. (')A sequence a0 , a1 , . . . is defined recursively by the equations a0 = 0, and
an = (an1 )2 + 1/4
Prove that 0 an < 1 for every n 0. (Hint: Surprising, it is easier to prove that 0 an < b
for some suitable chosen value of b instead of 1. Think about which would be the right value for
b and prove it.)
142. (')Let an be the number of bit strings of length n that have two consecutive 0s.
(a) Give a recursive definition of an .
(b) What is the value of a7 ?
143. (')Assume that you are in a fountain of water with two empty jars. One of the jars has
a capacity of 5 liters whereas the other has a capacity of 3 liters but none of the jars has any
measuring markings on it.
(a) You would like to obtain exactly 4 liters of water. Could you do it? Prove your answer
(b) Assume that, instead, the capacity of your bottles is 6 and 20. Could you obtain exactly
3 liters of water? Prove your answer.
144. (')Show, using induction, that a set with n elements where n 2 has n(n 1)/2 subsets
containing exactly 2 elements.

Graphs. Basic definitions

You can find more exercises about this topic in [3] (sections 8.1 and 8.2).
145. Let G be the graph
b
a
c
e
d

f
16

(a) List the nodes of G.

(b) List the edges of G.
(c) List all the vectors adjacent to d.
(d) Which is the degree of vertex a?
146. A graph has 6 vertices from which one has degree 2, two have degree 3 and three have
degree 4. How many edges does the graph have?
147. Prove that in every graph the number of vertices with odd degree must be even.
148. The degree sequence of a graph is a list which contains the degrees of its nodes in decreasing
order. For example, the degree sequence of the exercise 145 is 5, 3, 3, 2, 2, 1 indicating that there
is a vertex of degree 5 (a), two vertices of degree 3 (c and d), two vertices of degree 2 (b and e)
and a vertex of degree 1 (f ).
Is there a graph with 5 vertices for each one of the following sequences? If so, draw the graph.
If not, reason why it cannot be built.
(a) 3,3,3,3,2. That is the first vertex has degree 3, the second one has degree 3 and thus
successively until the fifth vertex which has degree 2.
(b) 5,4,3,2,2.
(c) 4,4,3,2,1.
(d) 4,4,3,3,3.
(e) 3,2,2,1,0.
149. Say if each of the following graphs is bipartite or not. Justify each answer.
a
e

(b) a

(a)

a
e

(c)

17

(d)

d
f

150. In each of the following cases, say if it is possible or not to build the graph specified. Justify
or prove your answer. If the answer is affirmative, draw an example of it.
(a) G has 9 edges and all of its vertices have degree 3,
(b) G has 10 edges, 3 vertices of degree 3 and the remaining of degree 2.

Graph coloring
You can find more exercises about this topic in [3] (section 8.8).
151. Let G be a graph, let k > 0, let x a node of degree smaller than k, and let G x the graph
obtained if we delete x and all the edges incident to x. Prove that G is k-colorable if and only
if G x is.
152. (')Find, justifying the answer, the chromatic number of the following graphs:

(a)

(b)

(c)

18

(d)

(e)

(f)
153. Suppose that a group of biologists decide to study a genetic feature which they suspect is
common in fish of the Amazons Basin. For this they will choose 7 different species of fish in the
zone and they want to fit out tanks for the fishes in a research centers ship. But some species are
incompatible with each other (for example a predator and its prey) and therefore they cannot be
in the same tank or water compartment. As a measure of precaution the biologists have decided
to avoid incompatible species being in the same compartment. They would also like to use the
minimum possible number of compartments.
The table of incompatibilities between species is the following:

Species
1
2
3
4
5
6
7

Incompatible species
2,4,5
1,3,4,5,6
2,4,5,7
1,2,3,5,6,7
1,2,3,4,6,7
2,4,5,7
3,4,5,6

Model this problem as a property on graphs and decide which is the minimum number of
compartments necessary.
154. We suppose that it is regulated that there are only 15 available frequencies for radio stations.
Naturally each radio station has to broadcast in one of these frequencies. We also suppose that
19

every pair of radio stations that are located less than 150 km apart cannot broadcast with the
same frequency since there are interferences. We would like to know how many different channels
would be necessary for six stations located at the distances shown in the following table:
1
1
2
3
4
5
6

2
85

3
4
5
6
175 200 50 100
125 175 100 160
100 200 250
210 220
100

Model this problem as a property on graphs and solve it.

155. (')We suppose that, in class, every pair of students are either friends or enemies. Suppose
that for every three different students x, y, z the following rules are fulfilled:
(1) If x and y are friends and y and z are friends then x and z are friends.
(2) If x and y are friends and y and z are enemies then x and z are enemies.
(3) If x and y are enemies and y and z are enemies then x and z are friends.
Show that the class can be divided in two sets A and B (one of the sets A or B can be empty)
such that for every pair of students x, y: x and y are friends if they are both in the same set and
enemies if they are in different sets. (Hint: This situation can be modeled by means of a graph
G in which the nodes are students and it has an edge between two students if these are enemies.
Then, it is only necessary to show that graph G is bipartite)
156. In the ceremony of coronation of the High Pirineus Prince a banquet is celebrated to which
Anna, Bea, Carles, David, Ester, Fernando, Gemma, H`ector, Ignasi and Joan attend. Some of
the guests have been enemies for many years and therefore we cannot place them in the same
table. Below it is shown who is enemy of who.
A
A
B
C
D
E
F

/ , / ,
/ , , ,
/ , ,
/ /
/

/
/
/
,
,
,

/
/
/
,
,
,
/

,
,
,
,
,
/
,
/

,
,
,
/
,
/
,
,
/

G
H
I
J

We want to know which is the minimum number of tables necessary at the banquet. Model this
problem using the concepts seen in class and find a solution. You can suppose that we have
tables of all sizes.
20

157. (')Let G1 = (V, E1 ) and G2 = (V, E2 ) be two graphs with the same set of nodes. The
union G1 G2 de G1 and G2 is the graph (V, E1 E2 ). That is, G1 G2 has the same vertices
as G1 (and therefore as G2 ) and the set of edges of G1 G2 is obtained joining the edges of E1
and E2 . Show that if the maximum degree of G1 and of G2 is 1 then G1 G2 is bipartite.
158. (') A graph G has width k if there exists an ordering x1 , x2 , . . . , xn of its vertices such
that every vertex is adjacent to at most k of the vertices which precede it in the ordering. Prove
that every graph of width k can be colored with k + 1 colors.
159. (')(') Let G be a connected graph of maximum degree k where there is a node with
degree smaller than k. Show that (G) k. (Hint: Thanks to the exercise 158 it is enough to
show that G has width k 1. To see that it has width k 1 we will build an ordering x1 , . . . , xn
of its vertices such that every vertex is adjacent to at most k of the vertices which precede it in
the ordering. We will try to build the ordering in reverse order. Which vertex could be xn ? and
xn1 ? and xn2 ?)

Connectivity in graphs. Directed Graphs.

160. The complement of a graph G = (V, E)s, which we will denote G, is the graph that has
the same vertices than G and contains an edge precisely when G does not contain it. Give each
of the following graphs complementary:
a
e

(a)

a
e

(b)

161. Draw all the subgraphs of the following graph:

c

b
a

162. Let G be the graph of the exercise 145. Below we will give a few vertices sequences. For
each of them you have to say if it is a walk, if it a closed walk, if it is a path, and if it is a cycle.
(a) a, b, c, d, f
(b) b, c, c, d
(c) a, b, c, a, d
21

(d) a, f, a, b, c, a
(e) a, b, c, d
(f) a, b, c, d, e, a
(g) a, b, a
(h) a
163. Let G be the graph of the exercise 145. Is G connected?
164. How many connected components does the following graph have? Give them.
f

e
a

g
i

165. (')Let G be a graph with n nodes. Prove that if every vertex of G has degree n/2 or
superior then G is connected. (Hint: try it by contradiction.)
166. (')Let G be a graph which has two nodes, called x and y, with odd degree and the rest
with even degree. Prove that there is a path which connects x with y.
167. Let G be a graph. A path x1 , . . . , xk of G is Hamiltonian if it contains all the vertices of
G. A cycle x1 , x2 , . . . , xk , x1 of G is Hamiltonian if x1 , . . . , xk is a Hamiltonian path. For each
of the following graphs, determine if it has a Hamiltonian cycle and, if it does, find it.
e

(a) a

b
m

b
h

22

c
j

(b)

m
e

b
j

(c)

m
e

b
h

i
n

(d)
168. Let G be following directed graph
d

Is G weakly connected? Is G strongly connected?

169. Let G = (V, E) and G0 = (V, E 0 ) be two graphs. We will say that G and G0 are isomorphic if
G0 can be obtained from G changing the names of the nodes. Formally, G and G0 are isomorphic
if there exists a bijective function f : V V 0 such that for every pair of vertices x, y of G,
{x, y} E if and only if {f (x), f (y)} E. Are the following graphs isomorphs? Justify your
answer.
1

b
c

f
4

170. In exercise 169 we have given the definition of isomorphism. Are the following graphs
isomorphic? Justify your answer.

23

6
a

b
c

f
3
1

4
e

171. How many different graphs there are with 4 nodes, modulo isomophism (that is, if we only
count once all the graphs which are isomorphic)?
172. Let G and H be two isomorphic graphs. Say if each of the following affirmations is true or
false:
(a) G and H sure have the same number of vertices.
(b) G i H sure have the same number of edges.
(c) G i H sure have the same degree sequence.
173. (')Prove that in every DAG there is a vertex with in-degree 0 and a vertex with out-degre
0.
174. A graph G is self complementary if G and its complementary, G, are isomorphic (you
can find the definition of complementary graph in the exercise 160). Is the following graph self
complementary? Justify your answer.

175. (')Prove the handshaking principle using induction. (Hint: Use induction in the number
of edges of the graph).
176. For every n 1, let Kn be the graph with n nodes where every pair of vertices are adjacent.
For example, K4 is the graph

How many edges does Kn have? Justify your answer.

177. In exercise 160 we have defined the complement of a graph. If a graph G has v vertices
and e edges, how many edges does its complement, G, have?
178. In class we have seen the Handshacking lemma for graphs. We would like to find a similar
result for directed graphs. That is, we would like an equation that relates the in-degrees and
out-degrees of the vertices with the total number of edges. Find such equation and prove it.
179. Let n 1. The n-dimensional hypercube, Dn , is the following graph:
24

 the vertices of Dn are the strings of n bits.

two vertices have an edge if and only if they differ in exactly 1 bit.
For example, the hypercube with 3 dimensions is the following:
110

111

100

101

010

011

000

001

(a) Prove that D2 and D3 have a Hamiltonian cycle. (You will find the definition of Hamiltonian cycle in the exercise 167).
(b) (')Prove, by induction, that Dn has a Hamiltonian cycle for every n 2. (Hint: Try to
see Dn as the graph obtained joining two copies of Dn1 and adding some edges connecting
them)
180. (')In exercise 174 we have seen the definition of self complementary graph (if you have
not done it before it is now a good moment to do it). Find a self complementary graph with 5
vertices.
181. (')Let Dn be the hypercube with n dimensions as it has been defined in the exercise 179.
Prove that for every n 1, Dn is bipartite.

Trees (rooted and unrooted)

You can find more exercises about this topic in [3] (sections 9.1-9.3).
182. Say if each of the following graphs is a tree or not.

(a)

(b)

25

(c)
183. Is there a tree with 5 vertices for each of the following degree sequences? If so, draw the
tree. If not, reason why it cannot be built.
(a) 2,2,2,1,0
(b) 3,3,2,1,1
(c) 3,2,1,1,1
184. Is there a graph without cycles with the same number of edges than vertices? Justify your
answer.
185. How many different trees with 4 nodes there are modulo isomorphism (that is, we will only
count once all the isomorphic trees)? Note: In exercise 169 we have defined what two graphs
being isomorphic means
186. Is it possible that a graph with more vertices than edges has cycles? Justify your answer.
187. Let T be a tree with n > 1 nodes and let d1 , . . . , dn be its degree sequence. Show that
dn 0 and that d1 + d2 + + dn = 2n 2.
188. (')A forest is a graph without any cycle. Note that the definition is like that of a tree but
we do not request the graph to be connected anymore. Therefore every tree is a forest but it is
not necessarily true that every forest is a tree. If G is a forest with n nodes and p connected
components, how many edges does G have?
189. (')Let G be a graph with n nodes. Show that if two of the following conditions are satisfied
then the third is satisfied too:
(a) G is connected.
(b) G does not have cycles.
(c) G has n 1 edges.
(Help: Prove it separately for each of the combinations of two conditions)
190. Let T be the following ordered binary tree.
a
c

b
e

d
h

g
j

(a) Which is the root of T ?

26

(b) Which is the parent of h?

(c) Which children does the vertex c have?
(d) Which are the siblings of the vertex g?
(e) Which are the internal nodes of T ?
(f) Which are the leaves of T ?
(g) Which are the ancestors of g?
(h) Which are descendants of b?
(i) Which is the depth of T ?
(j) List all the nodes of level 2.
191. Is there a 3-ary tree with 82 leaves and depth 4? Justify your answer.
h+1

192. (')Prove that every m-ary tree with depth h has at most mm11 vertices. (Help: Try to
show it in a similar way to the fact that every tree with depth h has at most mh leaves.)
193. Let T be the tree in exercise 190 which we consider to be rooted and ordered. Give the
order in which its nodes are visited according to each of the following tree traversal algorithms:
(a) Preorder.
(b) Inorder.
(c) Postorder.
194. (')Note that the set of rooted trees can be defined recursively as follows:
BASIC STEP: A single vertex r is a rooted tree. Its root is r.
RECURSIVE STEP: Suppose that T1 , . . . , Tn are rooted trees with roots r1 , . . . , rn respectively.
Then the graph formed by starting with a root r, which is a new node, and adding an edge from
r to each of the vertices r1 , . . . , rn is also a rooted tree.
(a) Give a recursive definition of the function, depth(T ), returning the depth of a rooted tree.
(b) Give a recursive definition of the function, leaves(T ), returning the total number of leaves
of a rooted tree.
(c) Give a recursive definition of the function, vertexs(T ), returning the total number of vertexs
of a rooted tree.
195. (')Let x and y be any two different vertices of a tree with n vertices. Show that deg(x) +
deg(y) n.
196. Let G be a connected graph that becomes non connected after removing any edge. Prove
that G is a tree.
197. (')Show that, in any graph, every vertex of odd degree is connected by a path to some
other vertex of odd degree.

27

198. (')Prove that in every binary tree with i internal vertices and f leaves
f i+1
199. A rooted m-ary tree is full if every internal vertex has exactly m children. Prove that if T
is a full m-ary tree with n vertices of which i are internal then
n=im+1
200. (') Let T be a binary ordered rooted tree such that when we visit its nodes in preorder
we obtain the sequence A, B, C, D, E, F, G, H, I, J and when we visit them in inorder we obtain
B, D, C, E, A, G, F, I, H, J. Find T .
201. (')Suppose that we start a chain of emails. Our message contains some instructions and
a list of names. When we start the chain, the list of names contains only our name. In the text
of the message we promise that whoever follows the instructions will have luck and health. The
instructions are:
1 If the list has 6 names then send 1 euro to the first name of the list.
2 Add your name at the end of the list.
3 If the list has more than 6 names then delete the first element of the list. (Note that, after
the deletion, there will be 6 names in the list)
4 Resend the message to 10 people who have not received it before.
If nobody breaks the chain and nobody receives the email more than once, how much money
does the each person who participates in the chain receive?
202. (')Let T be a binary rooted ordered tree such that when we visit its nodes in postorder
we obtain A, B, C, D, E, F, G, H, I, J and when we visit them in inorder we obtain the sequence
A, B, E, C, D, J, F, I, H, G. Find T .
203. Consider the set F of graphs defined recursively as follows
BASIC STEP: Any graph with a single vertex belongs to F
RECURSIVE STEP: Suppose that G is a graph in F. Then the graph formed by adding to G
a new node x and an edge (x, y) joining x with exactly one node y in G, belongs also to F.
The goal of this exercise is to show that F is precisely the set of trees. This task is divided
in two subtasks:
(a) Show that every graph in F is a tree. (Hint: Use, of course, structural induction).
(b) (')Show that every tree is a member of F. (Hint: Prove it by induction on the number
of vertices v. It can be helpful try to adapt the proof, seen in class, that every tree with v
nodes has v 1 edges)
204. Let T be a full binary tree with 93 nodes. How many internal nodes and leaves does it
have?
205. Prove that if T is a full m-ary tree with i internal vertices and f leaves then
f = i(m 1) + 1
(Hint: Use the result proved in exercise 199).
28

206. (')(')Exercise 195 was solved by a proof by contradiction. Give now a proof by structural
induction using the recursive definition in Exercise 203.
207. We want to build a full m-ary tree with 22 leaves. Which are the possible values for m?
208. Let G be a full 3-ary tree with 45 internal vertices. How many edges does it have?

Relations
You can find more exercises about this topic in [3] (sections 7.1,7.3, and 7.6).
209. Determine whether the relation R on the set of all integers is reflexive, symmetric, antisymmetic, and/or transitive, where (x, y) R if and only if
(a) x 6= y
(b) xy 1
(c) x = y + 1 or x = y 1
(d) x y (mod 7)
(e) x is a multiple of y
(f) x and y are both negative or both nonnegative
(g) x = y 2
(h) x y 2
210. Let R be a relation from a set A to a set B and S a relation from a set B to a set
C. The composite of R and S, denoted R S, is the relation consisting of all ordered pairs
(a, c) A C for which there is an element b B such that (a, b) R and (b, c) R.
Find R S where R the relation R = {(1, 1), (1, 4), (2, 3), (3, 1), (3, 4)} and S is the relation
S = {(1, 0), (2, 0), (3, 1), (3, 2), (4, 1)}.
211. Let R be a relation on a set A and let n be a positive integer. The power Rn is the relation
on A defined recursively as follows
R1 = R and Rn+1 = Rn R for n 1
Assume now that R is the relation on set {1, 2, 3, 4, 5} containing the ordered pairs
(1, 1),(1, 2),(1, 3),(2, 3),(2, 4),(3, 1), (3, 4), (3, 5), (4, 2), (4, 5), (5, 1), (5, 2), and (5, 4). Find
(a) R2
(b) R3
(c) R4
(d) R5
212. Let R be a relation from a set A to a set B. The inverse relation from B to A, denoted
R1 is the set of ordered pairs {(b, a) | (a, b) R}. The complementary relation, denoted R, is
the set of pairs {(a, b) A B | (a, b) 6 R}. Find R1 and R when R are the following relations
on the set of integers:
29

(a) R = {(a, b) | a < b}

(b) R = {(a, b) | a divides b}
213. Which of these relations on the set of all people are equivalence relations?
(a) {(a, b) | a and b are of the same age}
(b) {(a, b) | a and b have the same parents}
(c) {(a, b) | a and b share a common parent}
(d) {(a, b) | a and b have met}
(e) {(a, b) | a and b speak a common language}
214. Let R be the relation on the set of ordered pairs of positive integers such that ((a, b), (c, d))
R if and only if ad = bc. Show that R is an equivalence relation.
215. Let R be the equivalence class defined in exercise 214.
(a) Describe the equivalence class of (1, 2) with respect to R.
(b) Give an interpretation of the equivalence classes of R.
216. List the ordered pairs of the equivalence relations produced by these partitions of {a, b, c, d, e, f, g}.
(a) {a, b}, {c, d}, {e, f, g}
(b) {a},{b},{c,d},{e,f}, {g}
(c) {a, b, c, d}, {e, f, g}
217. (')Prove that a relation R on a set A is transitive if and only if Rn R for every positive
n.
218. (')Let R be a relation on A and let G be the digraph that represents A. Prove that for
every n 1 and every a, b R, (a, b) Rn if and only if there is a path from a to b in G of
length n. (Hint: prove it by induction on n)
219. Let R be a relation on a set A. We shall define the reflexive closure of R as the smallest
reflexive relation that contains R. Similarly, the symmetric closure of R is defined as the smallest
symmetric relation that contains R and the transitive closure of R is defined as the smallest
transitive relation that contains R. Let R be the relation on set {1, 2, 3, 4, 5} defined as R =
{(1, 1), (1, 2), (2, 1), (2, 3), (3, 4)}. Find:
(a) the reflexive closure of R
(b) the symmetric closure of R
(c) (')the transitive closure of R
220. List all the ordered pairs in the partial ordering that has the following Hasse diagrams
c

d
b
a

(a)
30

c
a

(b)

g
a

(c) b

221. Consider the poset with the following Hasse diagram

m

l
j

(a) Find the maximal elements.

(b) Find the minimal elements.
(c) Is there a greatest element?
(d) Is there a least element?
(e) Find all upper bounds of {a, b, c}
(f) Find the least upper bound of {a, b, c}, if it exists.
(g) Find all lower bounds of {f, g, h}.
(h) Find the greatest lower bound of {f, g, h}, if it exists.
222. Find a topological sort of the poset in Exercise 221
223. A poset is a lattice if every pair of elements has both a least upper bound and an upper
lower bound. Determine whether each the posets with the following Hasse diagrams are lattices.

31

g
f
d

(a) a
h
f

c
a

(b)

i
h
f

c
a

(c)

224. Let R be the relation on the set of people consisting of ordered pairs (a, b) where a is a
parent of b. Let S be a relation on the set of people consisting of the ordered pairs (a, b) where
a and b are siblings. What are S R and R S?
225. Let R be relation on a set. Show that R is symmetric if and only if R = R1 . (You will
find the definition of R1 in exercise 111)
226. (') Let R be a relation on a set A and let G be the digraph that represents A.
S
(a) Give an interpretation of the relation n1 Rn in terms of the graph G
S
(b) Show that n1 Rn is transitive.
227. Let R be a relation on a set A. Show that the reflexive closure of R is R {(a, a) | a R}
(Hint: According to the definition we will achieve our goal if we can show the following two facts
32

(a) R {(a, a) | a R} contains R and is reflexive, and (b) there is no any reflexive relation
containing R smaller than R {(a, a) | a R}.)
228. Let R be a relation on a set A. Show that the symmetric closure of R is R R1
S
229. (')Let R be a relation on a set A. Show that the transitive closure of R is n1 Rn (Hint:
Exercise 226 will be useful here)
230. Consider the poset ({3, 5, 9, 15, 24, 45}, |).
(a) Find the maximal elements.
(b) Find the minimal elements.
(c) Is there a greatest element?
(d) Is there a least element?
(e) Find all upper bounds of {3, 5}
(f) Find the least upper bound of {3, 5}, if it exists.
(g) Find all lower bounds of {15, 45}.
(h) Find the greatest lower bound of {15, 45}, if it exists.
231. Find a topological sort of the poset ({1, 2, 3, 6, 8, 12, 24, 36}, |)
232. (')Determine whether the following posets are lattices (Exercise 223 contains the definition
of lattice).
(a) (Z+ , |) where Z+ is the set of positive integers.
(b) ({1, 2, 3, 4, 5}, |).
(c) (P (S), ) where S is a set.

Counting
You can find more exercises about this topic in [3] (sections 4.1-4.5, and 6.5).
233. A multiple-choice test contains ten questions. There are four possible answers to each
question. How many ways a student can answer the questions
(a) if every question must be answered?
(b) if the student can leave answers blank?
234. Use a tree diagram to find the number of bit strings of lenght four with no three consecutive
0s.
235. How many positive integers of four digits
(a) are divisible by 9?
(b) are even?

33

(c) have distinct digits?

(d) are not divisible by 3?
(e) are divisible by 5 or 7?
(f) are not divisible by either 5 or 7?
(g) are divisible by 7 but not by 7?
(h) are divisible by 5 and 7?
(i) are divisible by 8 or 6?
236. 15 people participate in a literary contest where three prizes are awarded: the first one of
3000e, the second one of 2000e, and the third one of 1000e. In how many different ways can
the prizes be distributed? What if all the three prizes were of the same amount?
237. In a class with 12 students a committee of 5 people must be chosen. In how many different
ways can it be done?
238. How many words can be formed ordering the letters ABCDEFGH?
239. Find the expansion of (x + y)5
240. (')Prove that for every n 0:
 
 
 
 
n 0
n 1
n 2
n n
2 +
2 +
2 + +
2 = 3n
0
1
2
n
(Hint: use the Binomial Theorem)
241. 10 books must be placed on a shelf. Four of these books are of the same collection and,
for this reason, we want them to occupy the four positions at the right of the shelf. What is the
number of ways in which this can be done?
242. (')A group contains n men and n women where n > 0. How many ways can we place the
group members in a line so that the men and the women are in alternate positions.
243. A committee of 9 people must be constituted from a group made up by 15 men and 12
women. What is the number of different ways in which the committee can be selected if:
(a) it must have 4 men and 5 women.
(b) it must have at least 8 women
244. How many of the permutations of letters ABCDEF GH
(a) contain the chain ABC?
(b) contain the chain AB and the chain EF G?
245. How many strings of 10 bits contain:
(a) exactly four ones?
(b) up to four ones?
34

(c) an even number of ones?

246. A company keeps its 2701 products in three warehouses. Each warehouse has 5 enclosures,
each enclosure has 12 shelving units and each shelving unit has 5 shelves. Prove that there is
some shelf that contains at least 4 products.
247. (')For every n 0 we define Gn as the following directed graph:
For every 0 i n, 1 j n, Gn contains a node that we call xi,j .
For every 0 i < n, 1 j n, Gn contains a edge from xi,j to xi+1,j .
For every 0 i n, 1 j < n, Gn contains a edge of xi,j to xi,j+1 .
Below you can see how the graph G2 is
x2,0

x2,1

x2,2

x1,0

x1,1

x1,2

x0,0

x0,1

x0,2

Compute for every i, j how many different paths there are from node x0,0 to node xi,j .
248. How many different ways can a group of 8 men and 5 women be placed in a line so that
there are not two women in consecutive positions. Hint: Place the men first and consider how
to place women afterwards.
249. How many different graphs can be built where the set of nodes is {1, 2, . . . , n}? Justify
your answer.
250. (')Prove, without using the Binomial theorem, that for every n 0,
   
 
n
n
n
+
+
= 2n
0
1
n
(Hint: Show that both sides of the equality count the number of strings of n bits)
251. Prove that a party where there are at least two people, there are two people who know the
same number of people there.
252. (')How many of the permutations of the 26 letters of the alphabet contain any of the
words peix or gat.
253. (')Let (xi , yi ) i = 1, . . . , 5 be five points on the plane.
(a) Suppose that all points have integer coordinates (that is that xi and yi are integer for every
i = 1, . . . , 5) and consider the set of all the segments that join each pair of them. Show
that the middle point of some of these segments has aslo integer coordinates.
35

(b) Now the points do not need to have integer coordinates but we will suppose that 0 xi 2
and 0 yi
2 for every 1 i 5.
Show that there are two points such that their distance
is at most 2. (Hint: Note that 2 is the size of the diagonal of a square where each side
has size 1).
254. (')How many bit strings of length 10 contain either five consecutive 0s or five consecutive
1s?
255. How many bit strings contain exactly five 0s and 14 1s if every 0 must be immediately
followed by two 1s?
256. (')Show that among n + 1 positive integers not exceeding 2n there must be one of them
that divides one of the other. (Hint: Observe that every element a in the set can be expressed
as b c where b is a power of 2 and c is an odd number and use the pigeonhole principle)
257. How many words of 11 letters can be formed with the letters of the word MISSISSIPPI?
258. How many different outcomes we can obtain if we throw four identical dices.
259. How many different solutions does the equation x + y + z + t + u = 23 have where x, y, z, t, y
are non-negative integers.
260. We have 10 different candies which we want to distribute among Pep, Marta and Joan.
(a) What is the number of ways in which we can do it?
(b) What is the number of ways in which we can do it if Pep must receive two candies, Marta
five and Joan three.
261. A croissant shop has plain croissants, cherry croissants, chocolate croissants, almond croissants, apple croissants, and broccoli croissants. How many ways are there to choose
(a) a dozen croissants?
(b) three dozen croissants?
(c) two dozen croissants with at least two of each kind?
(d) two dozen croissants with no more than 2 broccoli croissants?
(e) two dozen croissants with at least five chocolate croissants and at least three almond
croissants?
(f) two dozen croissants with at least one plain croissant, at least two cherry croissants, at least
three chocolate croissants, at least one almond croissant, at least two apple croissants, and
no more than three broccoli croissants?
262. How many positive integers less than 1.000.000 have the sum of their digits equal to 19?
263. In the game popularly known as botifarra four players initially distribute among themselves the 48 different cards of the deck in equal parts.
(a) How many different ways are there two distribute the cards at the beginning of the game?
(b) How many different ways are there to distribute them if each player receives a king (in the
deck there are four kings)?
36

264. (') Consider the equation x + y + z + t + u = 23 where x, y, z, t, u are non-negative integers.

How many solutios are there such that
(a) x 1?
(b) x 2, y 1, and z 3?
(c) x 10?
265. How many integers in {1, . . . , 100} are odd or a perfect square?
266. A cash machines password is constituted by 4 figures between 0 and 9. Say how many
passwords there are:
(a) which have, at least, an even digit.
(b) which have, at least, a repeated digit.
(c) in which each digit is greater than the previous one.
(d) in which each digit is greater or equal than the previous one.
267. How many solutions does the inequality x+y+z 11 have where x, y and z are nonnegative
integers? (Hint: use a new auxiliary variable t such that x + y + z + t = 11).
268. (') Compute the number of solutions of the equation y1 + y2 + y3 = 12 if its variables take
integer values such that 1 y1 5, 2 y2 7 and 0 y3 9. (Note: Inspire yourself with
exercise 264 and use the inclusion-exclusion principle)
269. We enter a store which has 6 different types of ice cream. We want to buy 19 so that there
are at least 2 of each type. How many different ways can we do it?
270. (')How many words can be obtained by reordering the letters of ABRACADABRA if we
want all As to appear consecutively.
271. (') Suppose that we have k objects which we want to place in n different boxes. How
many ways can we do it:
(a) if the objects are different and every box cannot contain more than one object.
(b) if the objects are different and a box is allowed to have zero, one or more objects.
(c) if the objects are the same and every box cannot contain more than one object.
(d) if the objects are the same and a box is allowed to have zero, one or more objects.
(e) if the objects are different and we request the ith box to contain exactly ki objects, where
k1 , . . . , kn are nonnegative integers.
272. Four people play cards. Initially each player is given 5 cards. If the deck has 48 cards,
what is the total number of which in which the cards can be initially dist?
273. (')We have 12 different books which we want to place in 4 shelves. What is the number
of ways in which this can be done
(a) if the order in which they are placed within the same shelf is not relevant?

37

(b) if the order in which they are placed within the same shelf is relevant? (Hint: The number
that we are looking for is the same as the number of ways of ordering the n books and 3
identical dividers which we use to separate the books in each shelf).
274. How many of the permutations of 26 letters of the Catalans alphabet do not contain any
of the words peix, gat or ruc.
275. (')Prove that for every m, n, k 0:
    
  

   

m n
m
n
m
n
m n
m+n
+
+
+ +
=
0
k
1
k1
2
k2
k
0
k
(Hint: Show that both sides of the equality count the number of ways in which we can select a
committee of k people among a group of m men and n women)
276. (')We have 12 different books in a shelf and we want to choose 5 without choosing adjacent
ones. What is the number of ways in which this can be done? (Hint: Let a1 be the number
of books at the left of the first book chosen, a2 the number of books between the first and the
second books chosen, a3 the number of books between the second and the third books chosen
and this until arriving to a6 which is the number of books at the right of the fifth book chosen.
Compute in how many different ways we can choose a1 , a2 , . . . , a6 .)
277. (')Recall the definition of graph Gn in exercise 247 (Do not attempt to solve this exercise
without understanding well the solution of exercise 247)
(a) We suppose that n 10. How many paths are there from x0,0 to node x10,10 which do not
pass through node x3,4 .
(b) We suppose again that n 10. How many paths are there from x0,0 to node x10,10 which
do not pass through node x3,4 nor through node x8,7 .
278. In the final exam of discrete mathematics there are 6 questions which add up to 10 points.
The teachers want to decide how many points to assign to each question. How many ways are
there to do it if the value of each question has to be a positive integer.
279. Professor Bernat explains every year 3 jokes to his students. Sometimes he repeats jokes
from previous years but he has never explained the same 3 jokes in two different years. Knowing
that professor Bernat has been teaching for 25 years, how many jokes has he explained at least?
Justify your answer.

38

References
[1] K. Devlin, Introduction to Mathematical Thinking. 2012.
[2] M.R. Huth, M. D. Ryan, Logic in Computer Science. Modelling and reasonning about systems.
Cambridge University Press, 1st edition, 2002.
[3] K. H. Rosen, Discrete Mathematics and its Applications. Mc Graw Hill, 5th edition, 2003.
[4] D. J. Velleman, How to prove it. A Structured Approach. Cambridge University Press, 2nd
edition, 2006.
[5] E. Lehman, F. Leighton, A. Meyer, Mathematics for Computer Science. 2010. Downloadable
from http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/
6-042j-mathematics-for-computer-science-fall-2010/readings/MIT6 042JF10 notes.pdf
[6] J. Kleinberg, E. Tardos, Algorithm Design. Pearson Education, 1st edition, 2006.

39