=========================preview======================
(COMP170)Midterm1_2009s_review.pdf
Back to COMP170 Login to download
======================================================
COMP170 (Spring 2009)
Midterm 1 Review
Twelve points are marked on a circle. How many distinct convex polygons of three or more sides can be drawn using some or all of the 12 points as vertices?
Any subset of the 12 points with three or more members can be made into exactly one convex polygon.
Count the number of such subsets.
12
Since the number of k-element subsets is k , the total number of subsets is equal to
12122
12 1212
= .
k kk
k=3 k=0 k=0
2
12
212 .
=
k
k=0
= 4096 . 1 . 12 . 66 = 4017.
Any subset of the 12 points with three or more members can be made into exactly one convex polygon.
Count the number of such subsets.
12
Since the number of k-element subsets is k , the total number of subsets is equal to
12122
12 1212
= .
k kk
k=3 k=0 k=0
2
12
212 .
=
k
k=0
= 4096 . 1 . 12 . 66 = 4017.
Any subset of the 12 points with three or more members can be made into exactly one convex polygon.
Count the number of such subsets.
12
Since the number of k-element subsets is k , the total number of subsets is equal to
12122
12 1212
= .
k kk
k=3 k=0 k=0
2
12
212 .
=
k
k=0
= 4096 . 1 . 12 . 66 = 4017.
Let A = {a1, a2,..., ak } and B = {b1, b2,..., bk.2} be two nonempty sets where k > 3 is a positive integer. We de.ne surjective functions from A to B. How many such functions can be de.ned?
A surjective function from A to B:
It maps 3 elements in A to the same element in B and the remaining (k . 3) elements in A to the remaining (k . 3) elements in B.
k
Choosing the triple:
Mapping the (k . 2) groups in A to B:(k . 2)!
3
It maps 2 elements in A to the same element in B, another 2 elements in A to a di.erent element in B, and the remaining (k . 4)
elements in A to the remaining (k . 4) elements in B.
1 kk.2
Choosing two pairs:
22 2
Mapping the (k . 2) groups in A to B:(k . 2)!
By the sum principle, the total number of surjective functions is
.. ... . ...... ..
k 1 kk . 2 k 1 kk . 2
(k .2)!+ (k .2)!= + (k .2)!
3 222 3222 A surjective function from A to B:
It maps 3 elements in A to the same element in B and the remaining (k . 3) elements in A to the remaining (k . 3) elements in B.
k
Choosing the triple:
Mapping the (k . 2) groups in A to B:(k . 2)!
3
It maps 2 elements in A to the same element in B, another 2 elements in A to a di.erent element in B, and the remaining (k . 4)
elements in A to the remaining (k . 4) elements in B.
1 kk.2
Choosing two pairs:
22 2
Mapping the (k . 2) groups in A to B:(k . 2)!
By the sum principle, the total number of surjective functions is
.. ... . ...... ..
k 1 kk . 2 k 1 kk . 2
(k .2)!+ (k .2)!= + (k .2)!
3 222 3222 A surjective function from A to B:
It maps 3 elements in A to the same element in B and the remaining (k . 3) elements in A to the remain