Homework answers / question archive / COM00013C Section A: Counting 1 (10 marks) A tennis team consists of six women to play in pairs

COM00013C Section A: Counting 1 (10 marks) A tennis team consists of six women to play in pairs

Math

Share With

---

COM00013C

Section A: Counting

1 (10 marks)

A tennis team consists of six women to play in pairs.

(i) [2 marks] How many different ways are there of making one pair from the tennis team?

(ii) [2 marks] The team has to play another team of six women who also have to play in pairs.

What is the total number of ways of selecting one pair from each team to compete against each other?

(iii) [2 marks] Suppose now that tennis teams are mixed and that each team must have three men and three women. A pair must be formed using one man and one women. How many different ways are there of forming one pair from one mixed team?

(iv) [2 marks] How many different ways are there of forming a full mixed team, where three mixed pairs are formed from a team of six players?

(v) [2 marks] Compare your answers in parts (i) and (iii) above and give an explanation for their relative magnitudes.

2 (7 marks)

Consider the set of 8-bit binary numbers. We define three subsets of these numbers as follows:

• set A: those that start with 10

• set B: those that end with 001

• set C: those that have a 1 in the third most significant bit

(i) [1 mark] What is the cardinality of each of these three sets of numbers?

(ii) [1 mark] What is the cardinality of each pairwise set intersection?

(iii) [1 mark] What is the cardinality of the three-way set intersection?

(iv) [3 marks] What is the cardinality of the union of the three sets, A, B, C? Show your

working.

(v) [1 mark] Briefly state what the cardinality of the union of the three sets represents.

Page 3 of 13 Turn over.

Section B: Discrete probability

3 (8 marks)

A fair coin is flipped ten times.

(i) [2 marks] What is the probability that exactly five heads were obtained?

(ii) [2 marks] Suppose that a head occurred for the first time on the second flip, what is the

probability that a head occurred for the fifth time on the last flip?

(iii) [2 marks] Again, suppose that a head occurred for the first time on the second flip, what is

the probability that at least five heads were flipped?

(iv) [2 marks] Comment on the relative magnitude of your answers in parts (i) to (iii) above.

4 (7 marks)

In a gambling game, a single fair die is thrown, which has equal probability of falling on each

member of the set of numbers {1, 2, 3, 4, 5, 6}. Adrian pays Ben £1 if the die falls on one of

the three smallest numbers and £2 if the die falls of a 4 or a 5. However, Ben pays Adrian £10

if the die lands on a 6. Let the random variable X represent the amount that Adrian gains in

the game.

(i) [2 marks] Find the expected value of X, denoted E(X).

(ii) [2 marks] Find the variance of X, denoted var(X).

(iii) [2 marks] Find the expected value and the variance of the random variable Y , where Y

represents the amount that Ben gains in the game.

(iv) [1 mark] Comment on the values obtained for variable Y in comparison to those obtained

for variable X.

Page 4 of 13

Module Code

COM00013C

Section C: Graphs

5 (9 marks)

This question refers to the graph in Figure 1.

6

4 5

1 2 3

Figure 1: A graph

(i) [1 mark] What is the order of the graph, and the size of the graph?

(ii) [1 mark] Write down the degree sequence of the graph.

(iii) [2 marks] Write down the last row of the distance matrix for the graph with the same row

and column ordering as the graph’s numerical vertex labels.

(iv) [1 mark] What is the diameter of the graph?

(v) [3 marks] How many cycles does the graph have where 3 distinct vertices are visited? (In

your answer treat cycles that use the same edges, but in a different order, as distinct cycles.)

(vi) [1 mark] Provide an example of a Hamiltonian cycle in the graph.

Page 5 of 13 Turn over.

6 (9 marks)

This question refers to the graph in Figure 2, which is the same as Figure 1 but repeated on this

page for convenience.

6

4 5

1 2 3

Figure 2: A graph (repeated)

(i) [3 marks] Sketch two subgraphs of the graph in Figure 2, one should be of order 4 and the

other should be of order 5.

(ii) [3 marks] How many cliques can be formed from the graph in Figure 2? List the vertex set

for each of these cliques.

(iii) [3 marks] Suppose that we wish to remove a minimal number of edges from the graph such

that the graph becomes a tree with root node 6 and leaf nodes 1, 2 and 3. How many edges do

we need to remove? Provide two solutions and in each case list the removed edges as vertex

pairs.

Page 6 of 13

Module Code

COM00013C

Section D: Propositional and Predicate Logic.

7 (10 marks)

(i) [6 marks] Prove the following equivalence is valid, using suitable transformations.

(p , q) ? (p ^ q) _ (¬p ^ ¬q)

(ii) [4 marks] Express the exclusive-or (xor) connective over the two variables p and q, with

only ¬ and _. Show the steps involved.

8 (10 marks)

(i) [5 marks]

Given that the variables p, q, r have the following meanings:

p : Lobster is nice to eat.

q : I want to eat lobster.

r : It is fashionable to eat lobster

And given the following sentences:

If it is fashionable to eat lobster, then if I want to eat lobster, then lobster is nice to eat.

Lobster is not nice to eat.

Therefore, either I don’t want to eat lobster, or it is not fashionable to eat it.

(a) [2 marks] Write the sentences as an argument with p, q and r.

(b) [3 marks] Determine if the argument is valid. Provide an explanation for your answer.

(ii) [5 marks]

Given that the variables p, q, r have the following meanings:

p : Cars are fast.

q : I want to drive cars.

r : Cars are expensive

And given the following sentences:

If cars are fast, then I want to drive cars.

If I want to drive cars, then cars are expensive.

Cars are fast.

Therefore, cars are expensive.

Page 7 of 13 Continued.

(a) [2 marks] Write the sentences as arguments with p, q and r.

(b) [3 marks] Determine the validity of the argument and provide an explanation.

Page 8 of 13

Module Code

COM00013C

Section E: Sets and Inductive Arguments.

9 (10 marks)

(i) [2 marks] Let P represent a set containing the first ten Fibonacci numbers, such that:

P = {0,1,1,2,3,5,8,13,21,34},

Show, by giving a counterexample, that the following statement is false.

8p 2 P, p2  p!

(ii) [3 marks] The predicate ‘divisible(x, y)’ evaluates to TRUE when x is divisible by y and is

FALSE otherwise. Consider the following statement

8n 2 Z+, divisible(5n  1, 4)

where Z+ are the positive integers. Prove the validity of this statement using induction.

(iii) [3 marks] Given three sets A, B and C, a proof that (A \ B \ C) ? (A [ B [ C) is given

below, using a translated proposition with the predicates x 2 A, x 2 B and x 2 C.

Study the proof and state clearly the algebraic laws used at each step labelled STEP-A, STEP-B

and STEP-C.

x 2 A ^ x 2 B ^ x 2 C ) x 2 A _ x 2 B _ x 2 C

? translating ) to ¬, _

¬(x 2 A ^ x 2 B ^ x 2 C) _ x 2 A _ x 2 B _ x 2 C

? STEP-A

¬((x 2 A ^ x 2 B) ^ x 2 C) _ x 2 A _ x 2 B _ x 2 C

? by de Morgan’s law

(¬(x 2 A ^ x 2 B) _ x /2 C) _ x 2 A _ x 2 B _ x 2 C

? STEP-B

(x /2 A _ x /2 B) _ x /2 C) _ x 2 A _ x 2 B _ x 2 C

? as _ is commutative and associative

(x /2 A _ x 2 A) _ (x /2 B _ x 2 B) _ (x /2 C _ x 2 C)

? STEP-C

T _ T _ T

? by definition of _

T

Page 9 of 13 Continued.

(iv) [2 marks] If the set A = {BIKE, CAR} and the set

S = {T RAIN, BOAT, P LANE, SKAT EBOARD, GLIDER, BUS} then.

(a) [1 mark] List all the members of the power-set of A.

(b) [1 mark] Give a partition PS of S such that #PS (the cardinality of PS) is equal to 3

and each element of PS contains at least two elements.

Page 10 of 13

Module Code

COM00013C

Section F: Functions and Relations.

10 (15 marks)

(i) [5 marks] Consider the relations P : P erms ! Bool, and Q : P erms ! Bool, given that

P erms = {(F, F),(F, T),(T,F),(T,T)} and Bool = {F, T}.

The relations P and Q are represented by the adjacency matrices Pm and Qm respectively, as

given below, and where successive rows represent pairs appearing in the same sequence as

given in the definition for P erms above, and the left and right columns of each matrix

represent the elements F and T of Bool respectively.

Pm =

2

6

6

4

0 1

0 1

0 1

1 0

3

7

7

5

, Qm =

2

6

6

4

0 1

1 0

1 0

0 1

3

7

7

5

(a) [2 marks] Express P and Q as sets of ordered pairs.

(b) [2 marks] Draw the digraphs for P and Q.

(c) [1 mark] Identify the relations P and Q as their equivalent logical connectives.

(ii) [6 marks] Two sets are defined as follows:

A = {HOT, COLD}

S = {AMERICA, EUROP E, ARCT IC, AF RICA, ANT ARCT IC}

Let R be a relation from A to S defined by the matrix MR as follows:

MR =

? 11010

11001

where the successive rows are elements from A occurring in the same order as given in its set

definition, and the columns are elements from S also occurring in the same order as given in

its set definition.

(a) [2 marks] Define R as a set of ordered pairs and draw the corresponding digraph.

(b) [1 mark] Use the digraph to explain if R is a function or not.

Page 11 of 13 Continued.

(c) [1 mark] Use the digraph to explain if R is an injection or not.

(d) [1 mark] Use the digraph to explain if R is a total function or not.

(e) [1 mark] Use the digraph to explain if R is surjective or not.

(iii) [4 marks] Let G be the > (greater than) relation, and L the < (less than) relation, on the

set A = {3, 5, 7, 8, 9}. Use the adjacency matrices of the two relations (G and L) to show that,

G [ L is equivalent to the 6= (not equal to) relation.

Page 12 of 13

Module Code

COM00013C

Section G: Ordering and Equivalence.

11 (5 marks)

Let R be the relation R : A $ A , on the set A = {3, 5, 7, 8, 9}, such that

R = {(a1, a2)|a1 2 A, a2 2 A, a1 + 2 ? a2}

(i) [2 marks] Determine and draw the digraph of the relation R.

(ii) [2 marks] Draw the subgraph of the digraph from part (i), which represents its transitive

reduction. (This is a subgraph with the fewest possible arcs/edges, that maintains the original

graph’s reachability i.e. for any pair of vertices in the original graph, where a path exists

between them, a path should also exist in the subgraph).

(iii) [1 mark] Why is it that we cannot use a Hasse diagram to represent the relation R ?