MA2011 Discrete maths

Graded problem sheet 4

General Instructions

This assessment should be submitted online, via LearnJCU, before 5pm on Thursday 11 April.

See LearnJCU for submission information and general instructions.

There is a choice of questions so follow the instructions given carefully

There are a total of 50 (+2 bonus) marks available for this assignment.

1.  Complete questions worth 50 (or 52) marks

2.  Complete questions worth at least 10 marks from each section

3.  You must choose at least 3 questions worth 10 (or 12) marks

4.  In Part I, you may complete either question 1 or question 2 but not both

All questions are adapted from Tutorial sheets 7,8,9.  Part I, question 5 has been modified relative to an earlier version. This version was published on Thursday 4 April.

You may discuss this  assessment as much as you wish, but everyone must submit their own, individual and original work for grading.

You may hand write or type your work.  You are strongly encouraged to use LaTeX for typed work.  Please note that formatting errors can (and do) occur with MS Word.  You may adapt the .tex file of this question sheet for your work.  Post your questions in the Padlet if you would like help with particular aspects of LaTex code.

• You are expected to show all necessary working.  No marks are awarded for answers without justification or explanation, even if they are correct.

• I may ask you for more explanation of your submitted answers.  This is first and foremost to support you in developing your learning.

• Make sure you set out your answers clearly and methodically.  While marks are not awarded for neatness, you may be penalised for poorly written or extremely untidy work.

Part I

Complete questions in Part I worth a minimum of 10 and maximum of 30 marks according to the general instructions above.

You may complete either question 1 or question 2 but not both.

Questions

1. Total:  5 marks (From Rosen, Section 2.4, exercise 6)

Consider the sequence 1; 1; 3; 3; 5; 5; 7; 7; 9; 9; . . . of positive odd integers, where each integer is listed twice.  Give both a recursive and non recursive definition for this sequence.

2. Total:  5 marks (Modified from Rosen, Section 2.4, exercise 8)

Find two diferent sequences that begin with the terms 3,5,7, . . . .

Give a recursive definition for one sequence and a non-recursive definition for the other.

3. Total:  5 marks (Adapted from MA2211 exam, 2022)

Use the fact that x2 + x -2 = (x + 2)(x -1) to find a non-recursive definition for the recursively defined sequence

t(1) = 0;

t(2) = 2;

t(n) + t(n - 1) - 2t(n - 2) = 0

(Hint: first find a general solution for the second-order linear recurrence relation

t(n) + t(n - 1) - 2t(n - 2) = 0)

4. Total:  10 marks

There are three types of bee:

• Queens are fertile females

• workers are infertile females

• drones are fertile males

If eggs are fertilised then queens and workers are produced.  Otherwise, unfertilised eggs result in drones.  So, a drone has one parent  (the queen) and queens and workers have two parents (queen and drone).

(a)  Draw the family tree of a drone.                                                                                   (2 marks)

(b)  Let A(n) be the number of ancestors of the drone back n generations.  Find a recursive definition of the sequence A(n).  Explain your answer.

(Hint:  let Q(n) be the number of queens, and D(n) be the number of drones, back n generations.  So, A(n) = Q(n) + D(n).  Can you describe Q(n) and D(n)?)        (8 marks)

5. Total:  10 marks (Based on Rosen, Section 5.5.  This question has been modified.)

Use a loop invariant to prove that the following program segment, for computing the nth triangular number 1 + 2 + · · · + n is correct for all n ≥ 1

tri:  =  0

i:=  1

while  i<= n

tri  :  =  tri  +  i

i  :  =  i  +1

6. Total:  10 marks

Let F be the Fibonacci sequence 1,1,2,3,5,8,13, . . . defined recursively by

F (1) = F (2) = 1;  F (n) = F (n - 1) + F (n - 2) for all n > 2.                    (1)

(a)  Use equation (1) to show that F (6) - 1 = F (1) + F (2) + F (3) + F (4)                (3 marks)

(b)  Show, by induction or otherwise, that, for all n ≥ 1

F (1) + F (2) + · · · + F (n) = F (n + 2) - 1

(7 marks)

Part II

Complete questions in Part II worth a minimum of 10 and maximum of 30 marks according to the general instructions above.

Questions

1. Total:  5 marks (From MA2211, Assignment 2 2022)

A friend and I are tossing a coin to win marbles:  One of us tosses the coin n times, and each time it lands heads up that player gets one marble.

(a)  What is the probability that I win 6 marbles from 8 throws?                              (3 marks)

(b)  How many marbles am I most likely to have won after 8 throws?                        (2 marks)

2. Total:  5 marks

(a)  List the primes less than 8                                                                                               (1 mark)

(b)  Use part (a) to find the number of primes less than 50.

(Hint: How can you use Inclusion/Exclusion?  See also Rosen 8.6.3)

(4 marks)

3. Total:  5 marks (Modified from Hammack, Section 3.4 ex.  12) You deal 7 cards of of a 52-card deck and line them up in a row.

(a)  What is the total number of possible lineups?                                                             (1 mark)

(b)  How many possible lineups are there in which no card is a club?                         (3 marks)

(c)  How many lineups contain at least one club?                                                               (1 mark)

4. Total:  5 marks

The binomial theorem states that, for all n ≥ 1 and all real numbers a and b,

where 

(a) Use the binomial theorem to find the coefficient of a3 b4  in the expansion of (2a — 3b)7 .     (3 marks)

(b) (From MA2211, Assignment 2 2022) Use the binomial theorem to show that, for all n,

(Remark: It is interesting to think about the relationship between (ii) and the subsets of a finite set A with jAj = n.)                   (1+ 1 marks)

5. Total:  10 marks

Show that, in any group of 6 people, there are either 3 that all know each other, or 3 who are mutual strangers. (Assume that, if A knows B, then B also knows A.)

6. Total:  10 marks (Modified from Rosen, Section 6.2, Exercise 12)

For 1 ≤ i ≤ 5, let (xi ; yi ) be points in the cartesian plane with integer coordinates.

(a) How many lines would there be if you joined each pair of points by a straight line?       (2 marks)

(b) Let (xi,j ; yi,j ) denote the midpoint of the line from (xi ; yi ) to (xj ; yj ) (for i ≠ j).  Show that at least one of the points (xi,j ; yi,j ) has integer coefficients.                     (8 marks)

7. Total:  10 marks

A bag contains 5 red counters, 3 blue counters, 2 yellow, 2 green and 1 black counter.

(a)  What is the probablility that 3 counters selected from the bag without looking are all the same colour?                                   (5 marks)

(b)  If I select four counters from the bag without looking, how many diferent combinations are possible?

(Here all that matters is the combination of colours,  not how many ways there are of getting that combination of colours.)      (5 marks)

Part III

Complete questions in Part III worth a minimum of 10 and maximum of 30 (+2 bonus) marks according to the general instructions above.

1. Total:  5 marks

(a)  For each of the following graphs, find its complement.                                           (2 marks)

(b)  Give the adjacency matrix of graph (iii) and the adjacency matrix of its complement.   (2 marks)

(c)  How can you read the degrees of the vertices from the adjacency matrix?          (1 marks)

2. Total:  5 marks

(a)  Draw a simple bipartite graph whose complement is also bipartite.                     (3 marks)

(b)  W~hy are there no simple bipartite graphs G with five or more vertices whose complement G is also bipartite?                                                     (2 marks)

3. Total:  5 marks

A graph with n vertices U1 ; . . . ; Un  is called an n-cycle (or cycle of length n) if each vertex has degree 2 and there are edges between U1  and U2 , U2  and U3 ,  ...  Un  and U1

Show that a cycle with 6 vertices is bipartite, but that a cycle with 5 vertices is not.

4. Total:  5 marks

For each of the following graphs, use Euler’s theorem to determine whether an Euler circuit or Euler path exists. If one exists, find it.  If no such path exists, explain why not.

5. Total:  5 marks

(a)  For which values of n does the complete simple graph Kn  have a Euler path?   (3 marks)

(b)  How many Hamiltonian cycles does a complete graph on n nodes have?             (2 marks)

6. Total:  5 marks

Use Dijkstra’s algorithm (Activity 9.2 and Rosen, 10.6.2) to find the shorted route from A to B in the following graph. How many routes of this length are there?

7. Total:  10 marks

The degree of a vertex v of a directed graph is the pair  (in(v); out(v)) of natural numbers where in(v) is the number of edges directed towards (into) v and out(v) is the number of edges directed out of v.

(a)  Explain why for any finite directed graph with vertex set V and edge set E ,

(2 marks)

(b)  Six friends (A, B,C,D,E,F) have a squash league.

If no match can end in a draw, is it possible that in the last quarter

• A won 3 matches and lost 6

• B won 4 matches and lost 2

• C lost all their 5 matches

• D won 6 matches and lost 1

• E won 5 matches and lost 3

• F won 3 matches and lost 3                                                                                    (2 marks)

(c)  For each friend X in the league, let jXj denote the number of matches that X won minus the number of matches that X lost.

Explain why it is not possible that jAj ; jB j and j Cj are odd, but j Dj ; jE j and j Fj are even. (Hint: What is jAj + j Bj + j Cj + j Dj + jE j + j Fj ?)                                                 (2 marks)

(d)  For any finite directed graph G with vertex set V and any vertex v ∈ V , let

|v| = in(v) — out(v)

Explain/prove that,

(4 marks)

8. Total:  10 marks

Prove that a simple finite graph is bipartite if and only if it does not contain any odd cycles of length greater than or equal to 3.

9. Total:  10 + 2 bonus marks

A knight’s tour is a series of knight’s moves on a chessboard such that each square is visited exactly once.

(a)  The problem of finding a knight’s tour on an n × m chessboard is a problem of finding a Hamiltonian path on a certain simple graph with mn nodes.

Draw this graph for a board that is 3 squares high and 4 squares wide.             (2 marks)

(b)  Find a knight’s tour { that begins in the top-left square and ends in the bottom right square { on a board that is 4 squares wide and 3 squares high.

(Hint: For the graph you drew in part (a), notice the degrees of the vertices corresponding to corner squares and squares in the middle row.  )                                                   (3 marks)

(c)  Use your answer to b) to prove, by mathematical induction, that for all n ≥ 1, there is a knight’s tour on any board that is 3 squares high and 4n squares wide.

(5 + 2 bonus marks)