CSI 210 - Discrete Structures - Fall 2009
Sample Problems - Half-hour Exams IIa and IIb
Note: These are individual sample QUESTIONS; they do *not* form,
collectively, a sample EXAM. So this is a study aid for you, but
it is not an old exam, nor does it represent an exam, per se.
Exams IIa and IIb will cover material from Sections 2.4, 3.2-5,
3.8, 1.5-7, 4.1-3, and 5.1-3.
These sections are represented by slide sets 8-17 in the class notes
available from the class web pages.
Note: To post these questions in a timely manner requires guessing
just how many sections/slides will be covered. Naturally, if it turns
out that some of this material is not covered, then Exams IIa and IIb
will not include questions on that uncovered material.
Questions 1-4. Fill in the blanks. Brief explanations are desirable.
1. The number of integers in the range 1-100 which are divisible
by 11 = ___________________.
2. The value of gcd (-45; 75) = ___________________.
10
3. The value of SUM (2r - 1) = ___________________.
r=3
4. The number of zero entries in the 4 x 4 identity matrix = ________.
q
5. Consider the function f(n) = (n + 2) , where q is a positive
integer. Give a good estimate of the growth rate of f ; in other
words, determine a function g such that g is simple and does not grow
unnecessarily fast, and show that f(n) = O(g(n)).
(Recall that f(n) = O(g(n)) iff there is a constant k and
non-negative integer n0 such that for all n >= n0, f(n) <= (k)g(n).)
6. Suppose we have an m x n matrix A = [a(ij)] in which every element
is the same, i.e., aij = K, 1 <= i <= m, 1 <= j <= n. Suppose that
n x p matrix B has the property that the elements in each of
its columns sum to zero.
What will be the m x p matrix product C=AB? Why?
7. Show that if a iscon b(mod m), and if c iscon d(mod m),
then (a-c) iscon (b-d)(mod m).
where "iscon" means "is congruent to"
8. Show that at least one of the numbers a_1, a_2, ... a_n
is greater than or equal to the average of these numbers.
9. Show the details for the following inference:
Premises: s, ((p \/ q) --> r), ((~p /\ ~q) --> ~s)
Conclusion: r
10. Let A, B and C be finite sets.
Use induction on |(A intersect B)| to prove that
|(A union B)| = |A| + |B| - |(A intersect B)|.
11. Prove by induction that
n
SUM (i^3) = (n(n+1)/2)^2, for all n >= 1
i=1
12. Prove by induction that if h > -1, then
(1+nh) <= (1+h)^n, for all n >= 0.
13. The letters A, B, C, D and E are used to form strings of length 3.
a) How many of these strings begin with A, if repetitions
are NOT allowed?
b) How many of these strings contain A, if repetitions
are NOT allowed?
14. There are 10 questions in an examination.
A student has to answer a total of 7 questions, choosing
at least 3 from the first 5 questions.
How many different choices are possible ?
15. Ten delegates (one from each country) are to be seated in a row.
How many different seating arrangements are possible if the
French and English delegates are to be seated next to each other and
the US and Russian delegates are not to be seated next to each other ?
-=*+#%|%#+*=-=*+#%|%#+*=-=*+#%|%#+*=-
-=*+#%|%#+*=-=*+#%|%#+*=-=*+#%|%#+*=-
-=*+#%| |%#+*=-
-=*+#%| ANSWERS BELOW |%#+*=-
-=*+#%| |%#+*=-
-=*+#%|%#+*=-=*+#%|%#+*=-=*+#%|%#+*=-
-=*+#%|%#+*=-=*+#%|%#+*=-=*+#%|%#+*=-
Solutions to Practice Problems - IIa & IIb
Question 1:
floor(100/11) = 9
__________________________________________________________________________
Question 2:
75 = -45*(-1) + 30
-45 = 30*1 + 15
30 = 15*2 + 0
gcd(15,0) = 15 = gcd(-45,75)
__________________________________________________________________________
Question 3:
10 10 10 10
SUM (2r - 1) = SUM (2r) - SUM (1) = (2)SUM (r) - 8 =
r=3 r=3 r=3 r=3
= 2[((10 * 11)=2) - (1 + 2)] - 8
= 2*(55-3) - 8 = 104-8 = 96
__________________________________________________________________________
Question 4:
4*4-4 = 12
__________________________________________________________________________
Question 5:
q q q-1 q o
f(n) = (n+2) = n + (2q)n + ... + (2 )n
q q-1 q o
= Ao n + A1 n + ... + A n
I.e., f can be written as a polynomial of degree q.
Let Amax be the largest coefficient. Clearly
q
f(n) <= g(n) = (q)(Amax)n , for all n > 0.
Choosing n0 = 1 and k = (q)Amax, obviously, f(n) = O(g(n))
__________________________________________________________________________
Question 6:
C will be a matrix of all zeros.
n n
cij = SUM a(ir) b(rj) = K SUM b(rj) = (K)(0) = 0
r=1 r=1
__________________________________________________________________________
Question 7:
Show that if a iscon b(mod m), and if c iscon d(mod m),
then (a-c) iscon (b-d)(mod m).
By def., m | (a-b), thus (a-b) = (k1)m
By def., m | (c-d), thus (c-d) = (k2)m
So, (a-b) - (c-d) = (k1-k2)m
a - b - c + d = (k1-k2)m
a - c - b + d = (k1-k2)m
(a-c) - (b-d) = (k1-k2)m
Since (k1-k2) is an integer, m | (a-c) - (b-d)
Thus by def., (a-c) iscon (b-d)(mod m)
Question 8: Let a_r = max({a_1, a_2, ..., a_n}.
Therefore, a_r >= a_i, for 1 <= i <= n.
If we add up these n inequalities, we get
n a_r >= a_1 + a_2 + ... + a_n, or
a_r >= (a_1 + a_2 + ... + a_n) / n
Thus, a_r is greater than or equal to the average of the n numbers.
Question 9:
(1) s (premise)
(2) (p \/ q) --> r (premise)
(3) (~p /\ ~q) --> ~s (premise)
(4) s --> ~(~p /\ ~q) (Contrapositive of (3) and dbl. neg.)
(5) s --> (p \/ q) (DeMorgan's Law on (4) and dbl. neg.)
(6) p \/ q (Modus ponens -- (1),(5))
(7) r (Modus ponens -- (6),(2))
Question 10: To prove: |(A union B)| = |A| + |B| - |(A intersect B)|.
by induction on |A intersect B|.
Basis: |(A intersect B)| = 0.
Thus A and B are DISJOINT and in this case, by
the rule of sum we know that |A union B| = |A| + |B|.
Induction step:
Assume that k >= 0 and that the result is true
for any pair of sets X and Y, with |(X intersect Y)| = k.
Consider any pair of sets A and B with |(A intersect B)| = k+1.
Since k+1 >= 1, we must have (A intersect B) <> emptyset.
Therefore, we can find an element x in (A intersect B).
Let A' = A - {x} and B' = B - {x}$.
Clearly,
|(A' union B')| = |(A union B)| - 1(1)
|A'| = |A| - 1(2)
|B'| = |B| - 1 (e5)(3)
|(A' intersect B')| = |(A intersect B)| - 1(4)
Since |(A' intersect B')| = (k+1)-1, we can apply the inductive
hypothesis to A' and to B' to get
|(A' union B')| = |A'| + |B'| - |(A' intersect B')|(5)
Using the set of equations (1-4) in (5), we
see that |(A union B)| = |A| + |B| - |(A intersect B)|
even when |(A intersect B)| = k+1.
The result therefore follows by the principle of induction.
Question 11:
BASIS: n = 1
Verification left to the student.
INDUCTION STEP:
Assume the result for n = k;
k
that is, assume that SUM (i^3) = (k(k+1)/2)^2 (1)
i=1
We will prove that the result is also true for n = k+1.
k+1
that is, assume that SUM (i^3) = ((k+1)(k+2)/2)^2}
i=1
k+1 k
SUM (i^3) = SUM (i^3) + (k+1)^3
i=1 i=1
= (k(k+1)/2)^2 + (k+1)^3 from (1)
= (k+1)^2 (k^2/4 + k+1)
= (k+1)^2 (k^2+4k+4)/4
= (k+1)^2(k+2)^2/4
= ((k+1)(k+2)/2)^2
Now, the required result follows by the principle of induction.
Question 12: Proof by induction on n.
BASIS: n = 0.
Then, 1+nh = 1 and (1+h)^n = (1+h)^0.
Since h > -1, (1+h) <> 0 and so (1+h)^0 = 1.
(Recall that 0^0 is an ill-defined quantity).
Thus the basis is verified.
INDUCTION STEP:
Assume that the result is true for n = k.
That is, assume that, for some k >= 0,
1+kh <= (1+h)^k (1)
We will prove that the result is also true for n = k+1.
That is,
1+(k+1)h <= (1+h)^(k+1)
(1+h)^(k+1) = (1+h)^k (1+h)
>= (1+kh)(1+h) from (1)
= 1+kh+h+kh^2
= 1+(k+1)h+kh^2
Since k >= 0, and h^2 >= 0 (h is a real number),
it follows that kh^2 >= 0, and so
1+(k+1)h <= (1+h)^(k+1).
The required result then follows by the principle of induction.
Question 13:
a) If the string begins with A and repetitions are not allowed,
then the first position can be filled in only one way, the
second in 4 ways and the third in 3 ways.
Thus the total no. of strings = 1 x 4 x 3 = 12.
b) The total number of strings of length 3, not allowing
repetitions = 5 x 4 x 3 = 60.
Of these, the number that don't contain A = 4 x 3 x 2 = 24.
Therefore, the number that contain A = 60-24 = 36.
Question 14:
From the first 5 questions, the student may choose 3, 4 or 5
questions.
The student can choose 3 out of the first 5 and 4 out of the
remaining 5 in C(5,3) x C(5,4) = 50 ways.
The student can choose 4 out of the first 5 and 3 out of the
remaining 5 in C(5,4) x C(5,3) = 50 ways.
The student can choose 5 out of the first 5 and 2 out of the
remaining 5 in C(5,5) x C(5,2) = 10 ways.
Thus, total = 50 + 50 + 10 = 110$.
Question 15:
Let us first find the number (N_1) of arrangements in which
the French and the English delegates are together.
To do that, treat them as 1 delegate.
Thus we have a total of 9 delegates and the number of arrangements
is 9!.
But the French and the English delegates may be arranged in 2! ways.
Therefore, N_1 = 9! x 2!.
Let us now find the number (N_2) of arrangements in which
the French and the English delegates are together AND
the US and the Russian delegates ARE TOGETHER.
To do that, treat the English and the French delegates as 1 delegate
and the US and the Russian delegates as 1 delegate.
Thus we have 8 delegates and they can be arranged in 8! ways.
However, the French and the English delegates can be permuted
in 2! ways and the US and the Russian delegates can be
permuted in 2! ways.
Therefore, N_2 = 8! x 2! x 2!.
Therefore, the number of arrangements in which the French and the
English delegates are together while the US and Russian delegates
are not together is = N_1 - N_2 = 564,480.