Hi, I need help on questions 1, 2 and 3 on the attached document. I would like to get a thorough explanation on how each of the answer was obtained, thanks.

CMPUT 272 Winter 2016

Assignment 5

Due Thurs Apr 7 at 9:15AM in your seminar section?s drop box across from CSC 145
This is the mandatory assignment cover sheet;
without it, your work will not be marked.

Submitting student:

Seminar section: (circle):

Monday J1/EJ1

Tuesday J2/EJ2

Thursday J3/EJ3

Collaborating classmates:

Other collaborators:

References other than the textbooks and handouts:

Your mark:
1

2
/8

3
/8

4
/8

5
/8

6
/4

7
/8

/12

Total
/56

Even though collaboration is allowed, you must always write your solutions alone and in your own
words, and properly acknowledge the sources that you used and the people with whom you worked.
Your professor reserves the right to give you an oral and/or written exam to determine how well
you understand what you have submitted. This may impact your mark.

CMPUT 272 Winter 2016

Assignment 5

Due Thurs Apr 7 9:15AM

1. (Epp 7.3.25) Prove or give a counterexample: If f : X ? Y and g : Y ? X are functions
such that g ? f = IX and f ? g = IY , then f and g are both one-to-one and onto and g = f ?1 .
2. (Epp 8.3.27) De?ne a relation R on Z as follows: For all m, n ? Z, m R n ? 4 | (m2 ? n2 ).
Prove that R is an equivalence relation. Describe the distinct equivalence classes of R and
justify your answer.
3. (Epp 8.5.34) Suppose that R is a partial order relation on a set A and that B is a subset of A.
The restriction of R to B is de?ned as {(x, y)|x ? B, y ? B, and (x, y) ? R}. In other words,
two elements of B are related by the restriction of R to B if and only if they are related by
R. Prove that the restriction of R to B is a partial order relation on B.
4. (Epp 9.2.33) Six people attend the theatre together and sit in a row with exactly six seats.
There is an aisle on each end of the row.
(a) How many ways can they be seated together in the row?
(b) Suppose one of the six is a doctor who must sit on the aisle in case she is paged. How
many ways can the people be seated together in the row with the doctor in an aisle seat?
(c) Suppose the six people consist of three married couples and each couple wants to sit
together with the husband on the left. How many ways can the six be seated together
in the row?
5. In how many ways can a family of four (mother, father, and two children) be seated at a
round table, with eight other people, so that the parents are seated next to each other with
one child beside each parent? (Two seatings are considered the same if one can be rotated to
look like the other).
6. (Epp 9.4.38) Observe that the sequence 12, 15, 8, 13, 7, 18, 19, 11, 14, 10 has three increasing
subsequences of length four: 12, 15, 18, 19 and 12, 13, 18, 19 and 8, 13, 18, 19. It also
has one decreasing subsequence of length four: 15, 13, 11, 10. Show that in any sequence
a1 , a2 , . . . an2 +1 of n2 + 1 distinct real numbers, there must be a subsequence of length n + 1
that is either strictly increasing or strictly decreasing. Hint: Use proof by contradiction and
the pigeonhole principle. For each 1 ? k ? n2 + 1, de?ne ik to be the maximum length of
an increasing subsequence starting at ak , and dk to be the maximum length of a decreasing
sequence starting at ak . What happens if (ik , dk ) = (i , d ) for some k and with k = ?
7. A computer programming team has 15 members.
(a) How many ways can a group of eight be chosen to work on a project?
(b) Suppose nine team members are women and six are men.
i. How many groups of eight can be chosen that contain four women and four men?
ii. How many groups of eight can be chosen that contain at least one man?
iii. How many groups of eight can be chosen that contain at most three women?
(c) Suppose two team members refuse to work together on projects. How many groups of
eight can be chosen to work on a project?
(d) Suppose two team members insist on either working together or not at all on projects.
How many groups of eight can be chosen to work on a project?