Comments, hints, and some solutions for exam dat401 DM 020320

This is not a model solution!

1a Solution: 3 (not 5, which is the most popular wrong answer)

1b Note that the graph must be connected (less than one third got this one right).

1d The event ‘diam(G(n, p)) = 1’ is the same as the event ‘G(n, p) = K_{n}.’

1e Solution: 1 − p. Many students use a very long argument which involves counting the number of graphs with d(v_{1}, v_{2}) > 1. This is impressive but unnecessary: the distance is 1 if and only if the edge {v_{1}, v_{2}} is present, which happens (by definition) with probability p.

1f Solution: (1 − p^{2})^{n−3}.

1g Hint: p(diam(G(n, p)) = 2) = 1−p(diam(G(n, p)) = 1)−p(diam(G(n, p)) > 2). For the last expression use 1f and P (A ∪ B) ≤ P (A) + P (B).

2a There are 15. (Few students found them all).

2b Solution: Yes.

2c Solution: Yes.

2d The answer is yes. A ‘formal proof’ is an opportunity to show your familiarity with the language of maths — so please don’t write nonsense like ‘a ∧ b ∧ c ∈ T_{i}’ when you mean ‘{a, b, c} ⊆ T_{i}’. Note also that you proof needs to use the disjointness of the T_{i} somewhere, otherwise it’s incomplete.

2e Many students’ arguments would benefit from the phrase ‘by the Sum Rule’. Here’s the most popular argument (which is sufficient): “A partition of S places the elements into a number of subsets T_{1}, …, T_{k}; at least k ≥ 1 (in which case T_{1} = S) and at most k ≤ n (in which case T_{i} = {i}). By the Sum Rule we can count the total number of partitions of S (of any size) by for each k (1 ≤ k ≤ n) counting the number of ways to partition S into exactly k subsets, which is given by \left\{{n \atop k}\right\}.” Note that this answer is quite precise in explaining the bounds on the sum (k from 1 to n).

2f Hint: Consider the set into which ‘n + 1’ has been placed.

3a Should take 26 moves.

3b Solution: T_{n} = 3T_{n−1} + 2, T_{1} = 2. Don’t forget the T_{1} case!

3d Many students solve this by induction, which is really cute! The solution I had in mind simply counts the number of different legal arrangements (hint: place all discs on the pegs, starting with the largest) and notes that this number is 1 + T_{n}.