Discrete Structures Questionnaire

Give an example of each of the statements below using the sets indicated (and power sets) to show that the statement is either True or False, and briefly explain.

Let A; B and C be sets and E be the empty set.

a) If A belongs to B and B belongs to C, then A belongs to C.

b) If A belongs to B and B belongs to C, then it is impossible that A belongs to C.

c) If A belongs to B, then it is impossible for A to be contained in B.

d) If (A U B) = (A U C) and (A ^ B) = (A ^ c), then B = C

2.

10 points

How many ways are there to choose a password of length 20 that contains only lowercase letters or digits and that has exactly three a’s and at least one b?

3.
10 points
When using the inclusion/exclusion method to find the size of the union of five sets, you need to subtract the size of the triple intersections. Indicate if this is true or false, and give the reason why.

4.

10 points

Ten passengers take an airport shuttle which has a route including 5 hotels, and each passenger gets off the shuttle at their own hotel. The driver records how many passengers leave the shuttle at each hotel. How many possibilities exist

5.
10 points

How many different words can be formed by permuting the letters in the word MOROCCO?

6.
20 points
Ten honors students, each from a different high school in a county are lined up in two rows of five for a photo. How many arrangements are possible if:

(a) Students from school A and School B cannot be in the same row;

(b) Students from school A and School C cannot be in the same row;

(c) Students from School D and School B cannot be in the same row;

(d) Students from School D and School C cannot be in the same row.

7.
10 points
How many ways are there to arrange 20 books on a bookcase with 3 shelves? Assume that the books are distinguishable, and that the order of the books on each shelf does matter.

8.
10 points
In organizing groups to work on homework together every student is asked to fill out a form listing all other students who they would be willing to work with. If there are 251 students in the class and each student lists exactly 168 other students who they might be willing to work with . For any two students in the class, if student A puts student B on their list, then students B will also have student A on their list. Using the Pidgeon Hole show that there must be some group of four students who are work with one another.

9.
20 points
How many ways are there to arrange a deck of 52 cards so that for each suit, all cards of that suit are together? Recall that there are 13 ranks of cards (from Ace to King), and 4 suits (spades, hearts, diamonds, and clubs).

10.
10 points
If you have 8 boxes labelled 1 through 8 and 16 indistinguishable red balls. How many ways are there to put the balls into boxes if:

(a) No odd box can be empty;

(b) Odd boxes must have an odd number of balls and even boxes must have an even number of balls.

11.
20 points
If there is $20,000 to be invested among 4 possible options. Each investment must be an integral of $1,000 and there are minimal investments that are required for each option of $2,000 for option 1, $2,000 for option 2, $3,000 for option 3, and $4,000 for option 4.

How many different investment strategies are available if:

(a) an investment is made in each option;

(b) investments must be made in at least 3 of the 4 options?

12.
10 points
How many ways are there to arrange the letters a,b,c,d,e,f so that a is not directly followed by b or c? For example, abdefc and acdefb are both invalid, but adbcef is valid.

13.
10 points
Using the Pidgeonhole principle show that in every set of 100 integers there exist two whose difference is a multiple of 37.