�

Lunds Universitet

Datavetenskapliga institutionen

DAT 401 – DM

Prov på delkurs Diskret Matematik

20 mars 2002 kl 8–13 Gasque

Tillåtna hjälpmedel: Litteratur, egna anteckningar

Tentamen består av 3 uppgifter, varje uppgift kan ge 10 poäng. Deluppgifternas poäng anges inom [hakparenteser]. Observera att poänggivningen inte nödvändigtvis avspeglar deluppgiftens svårhetsgrad. Uppgifterna kan besvaras på svenska eller engelska.

Behandla högst en uppgift per papper (det går bra att behandla deluppgifter på samma papper). Skriv bara på ena sidan och markera varje sida med dina initialer. Skriv läsligt.

▶ a)[0] Hur många uppgifter får man behandla per papper? ▶ b)[0] Får man skriva på baksidan?

Det går bra att referera till kursboken av Rosen eller Husfeldts anteckningar. Referenser måste ha formen [R: något] eller [H: något], där något är ett avsnittsnummer, en kodbit, en räknad uppgift, etc. Skriv till exempel “genom att använda Lemma [R:7.4]”.

Exercise 1 (Graphs, Probability)

All graphs G = (V, E) in this exercise are undirected.

The distance d(u, v) between two vertices in a connected graph is the length of the shortest path between the vertices. For example, in both graphs below, the distance between u and v is 4.

G_{1} = ∘ ∘ ∘ ∘v ∘ ∘u G_{2} = ∘ ∘ ∘ ∘v ∘ ∘u ∘

It is important to note that although G_{2} does contain a path of length 6 from u to v, this does not mean that their distance is 6: The shortest path from u to v is still length 4.

The diameter diam(G) of a graph is the longest distance between any pair of vertices; in symbols,

diam(G) = max_{u,v∈V} d(u, v).

We have diam(G_{1}) = diam(G_{2}) = 4, but diam(G_{3}) = 5 for the graph below:

G_{3} = ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘

because there is a pair of vertices at distance 5.

▶ a)[1] Find the diameter of G_{4} = ∘ ∘ ∘ ∘ ∘ ∘ .

▶ b)[1] Draw a graph with 4 vertices and diameter 1. ▶ c)[1] How many edges are there in a graph with n vertices and diameter 1?

The remaining questions study the diameter of a random graph. Let G(n, p) denote a random graph on n vertices with edge probability p. The vertices are numbered v_{1}, …, v_{n}.

▶ d)[1] Find the probability that a random graph has diameter 1. In symbols, find p(diam(G(n, p)) = 1).

In the remaining questions you may fix p = \frac{1}{2} if that makes it easier for you.

▶ e)[1] Find the probability that the distance between v_{1} and v_{2} in a random graph

is greater than 1. In symbols, find p(d(v_{1}, v_{2}) > 1). ▶ f)[3] Find the probability that the distance between v_{1} and v_{2} in a random graph

is greater than 2. In symbols, find p(d(v_{1}, v_{2}) > 2). Hint: Consider, for each other vertex v_{i}, the probability of a path v_{1}v_{i}v_{2}.

▶ g)[2] Bound the probability that the diameter of a random graph is not 2. In symbols, show that p(diam(G(n, p)) ≠ 2) is small. Use your answer to the previous question for this.

The conclusion is that a random graph has diameter 2 with high probability. In other words, and more dramatically: almost every graph has diameter 2.

Exercise 2 (Combinatorics, Sets, and Relations)

Let S = {1, …, n}. A partition of S is a collection of disjoint, nonempty subsets T_{1}, …, T_{k} ⊆ S whose union is T. In symbols,

T_{i} ≠ ∅ for 1 ≤ i ≤ k; T_{i} ∩ T_{j} = ∅ for i ≠ j; ⋃_{i=1}^{k} T_{i} = S.

Here is a partition of S for n = 6:

T_{1} = {1, 4}, T_{2} = {2, 3, 5}, T_{3} = {6}.

We don’t care about the numbering of the sets T_{i}, so the partition above is the same as the following:

T_{1} = {2, 5, 3}, T_{2} = {6}, T_{3} = {4, 1}.

Here are the 5 possible partitions for n = 3:

T_{1} = {1}, T_{2} = {2}, T_{3} = {3}. T_{1} = {1, 2, 3}.
T_{1} = {1}, T_{2} = {2, 3}.  T_{1} = {2}, T_{2} = {1, 3}.  T_{1} = {3}, T_{2} = {1, 2}.

▶ a)[1] Find all partitions for n = 4.

Given a partition T_{1}, …, T_{k} of S define the relation R: S×S where (x, y) ∈ R if and only if x and y belong to the same subset. In symbols:

(x, y) ∈ R if and only if ∃i: x ∈ T_{i} ∧ y ∈ T_{i}.

▶ b)[1] Is R symmetric? If yes, write ‘yes’. If no, give a (small) counterexample. ▶ c)[1] Is R reflexive? If yes, write ‘yes’. If no, give a (small) counterexample. ▶ d)[2] Is R transitive? If yes, give a short formal proof. If no, give a (small)

counterexample.

Let B(n) denote the number of partitions of S for given n (these are called Bell numbers after Eric Temple Bell^{1}). For example, we showed B(3) = 5 above.

The number \left\{{n \atop k}\right\} is defined (for 1 ≤ k ≤ n) to be the number of ways to partition \{1, …, n\} into exactly k sets (for example, \left\{{3 \atop 2}\right\} = 3).

▶ e)[2] Give a (short) combinatorial argument for

B(n) = ∑_{k=1}^{n} \left\{{n \atop k}\right\}.

▶ f)[3] Give an argument for the following recurrence (don’t try to solve it!).

B(n + 1) = ∑_{i=0}^{n} \binom{n}{i}B(i).

You can either give a combinatorial argument (recommended), or give an algebraic proof based on the previous question. In that case, you probably want to use

\left\{{n + 1 \atop i + 1}\right\} = ∑_{k=0}^{n} \binom{n}{k}\left\{{k \atop i}\right\},

B(0) = 1, and \left\{{n \atop k}\right\} = 0 for k > n or k = 0 (you don’t need to prove these things).

1Who wrote science fiction under the pseudonym John Taine

Exercise 3 (Recurrences)

Consider a variation of the Towers of Hanoi puzzle, which we will call Tired Hanoi. In Tired Hanoi we want to move all discs from peg 1 to peg 3, but we forbid moving a disc directly from peg 1 to peg 3 or from peg 3 to peg 1. In other words, all moves must involve peg 2. (Imagine the monks are very tired and cannot move the discs over long distances.)

Consider for example the first eight moves in the case with n = 3 discs, all starting on peg 1. (We use the notation (i → j) for moving the top disc of peg i to the top of peg j.)

\begin{aligned}& (1 → 2) & (2 → 3) & (1 → 2) & (3 → 2) \\ (2 → 1) & (2 → 3) & (1 → 2) & (2 → 3) & ⋯ \end{aligned}

In the standard version of Towers of Hanoi (where the moves (1 → 3) and (3 → 1) are allowed), the same arrangement can be reached with only three moves:

(1 → 2)  (1 → 3)  (2 → 3)

Evidently, Tired Hanoi takes more time than standard Hanoi. Also please note that Tired Hanoi requires the discs to end on peg 3; while standard Hanoi may end on peg 2 or peg 3.

▶ a)[1] Finish the example for n = 3. Use the (i → j) notation instead of drawing lots of pretty pictures. State the total number of moves (including the first eight moves from the example).

▶ b)[4] Find a recurrence relation for T_{n}, the number of moves needed to solve the

Tired Hanoi problem with n discs. ▶ c)[3] Solve the recurrence you found in the previous question. If you didn’t solve

the previous question, solve D_{1} = 3, D_{n} = 3 + 3D_{n−1} instead. ▶ d)[2] [Cute but not really hard:] Show that every legal arrangement of the n discs

on the 3 pegs is encountered during the solution of Tired Hanoi.