MAN 240 : Diskret matematik

Tentamen 230803

Lösningar

F.1 (i) Fix k ≥ 3. We first compute the number of 7-digit decimals containing exactly k 9:s. If the first digit is not a 9, then the number of possibilities is

( \begin{matrix}6 \\ k \end{matrix} ) · 8 · 9^{6−k},

since there are ( \begin{matrix}6 \\ k \end{matrix} ) possibilities for the positions of the 9:s, 8 options for

the first digit and 9 for each of the remaining 6 − k digits.

Similarly, if the first digit is a 9, then the number of possibilities is

( \begin{matrix}6 \\ k − 1 \end{matrix} ) · 9^{7−k}.

Summing over k, we thus find that the total number of 7-digit decimals containing at least three 9:s is

∑_{k=3}^{7} ( \begin{matrix}6 \\ k \end{matrix} ) · 8 · 9^{6−k} + ( \begin{matrix}6 \\ k − 1 \end{matrix} ) · 9^{7−k}.

This works out as 241065, though you weren’t expected to compute this number.

Note : An alternative approach is to compute the number of 7-digit decimals containing at most two 9:s and subtract this from 9 · 10^{6}.

(ii) The answer is 8!/3!, which is most easily explained as follows : there are 8! possible orderings of the 8 countries. Among all these orderings, each of the 3! ‘suborderings’ of Denmark, Italy and Liechtenstein appears equally often.

F.2 (i) The graph has Hamilton cycles, for example

s → a → d → h → t → i → e → b → f → g → c → s.

(ii) χ(G^{∗}) ≥ 3 since G^{∗} contains a triangle (exactly one triangle in fact, namely Δhit). On the other hand, if we apply the greedy algorithm to the nodes ordered as s, a, b, c, d, e, f, g, h, i, t then we get a 3-coloring, namely (the colors are 1, 2, 3)

s 1 f 2
a 2 g 1
b 1 h 2
c 2 i 1
d 1 t 3
e 2

Hence χ(G^{∗}) = 3.

(iii) Use BFS, starting, say, from the vertex s, to build up the following sequence of edges in a MST :

{s, c}, {c, g}, {f, g}, {f, i}, {i, h},
{d, h}, {b, f}, {a, b}, {i, t}, {b, e}.

The total weight of this tree is 13 + 4 + 8 + 5 + 3 + 5 + 6 + 4 + 7 + 8 = 63. Note that it is the unique spanning tree of this weight.

(iv) Apply Dijkstra’s algorithm to build up the following tree

Step Choice of edge Labelling
1  sc  c := 13
2  sa  a := 14
3  cg  g := 17
4  ab  b := 18
5  ad  d := 22
6  bf  f := 24
7  be  e := 26
8  dh  h := 27
9  gt  t := 29

Hence the shortest path from s to t is s → c → g → t and has length 29. Note that this is the only path from s to t of length 29.

(v) Starting with the null flow f ≡ 0, one can find the following sequence of f-augmenting paths from s to t (these are not the only choices, of course) :

s − a − d − e − i − t, ϵ = 7,
s − c − b − f − g − t, ϵ = 6,
s − c − g − t, ϵ = 4,
s − c − b − e − i − h − t, ϵ = 3,
s − a − b − e − d − h − t, ϵ = 4,
s − a − d − h − t, ϵ = 1.

This yields the following maximal flow with |f| = 25

Edge Flow Edge Flow Edge Flow
(s, a) 12 (b, f) 6 (f, g) 6
(s, c) 13 (c, g) 4 (i, h) 3
(a, b) 4 (d, e) 3 (h, t) 8
(c, b) 9 (d, h) 5 (i, t) 7
(a, d) 8  (e, i) 10 (g, t) 10
(b, e) 7  (f, i)  0

The corresponding minimal cut is S = {s, a}, T = rest of them. Its’ capacity is given by

c(S, T) = c(a, d) + c(a, b) + c(s, c) = 8 + 4 + 13 = 25, v.s.v..

F.3 Theorem 10.4 (resp. 17.4) in old (resp. new) Biggs.

F.4 The optimal bound is χ(G) ≤ 3. If G is a triangle, then the bound χ(G) = 3 is attained. On the other hand, χ cannot be greater than 3. For, since G is connected, it has a spanning tree T. Being a tree, we have χ(T) = 2. Also, T has n vertices and n − 1 edges, so G consists of T plus a single edge. We can now 3-color G as follows : first, 2-color T. Let {x, y} be the extra edge in G. If vertices x and y get different colors in the 2-coloring of T, then this is also a 2-coloring of G. Otherwise, change the color of y say to the 3rd color available, and thus obtain a 3-coloring of G.

F.5 Theorem 18.3 (resp. 25.3) in old (resp. new) Biggs.

F.6 Let

F (x) = ∑_{n=0}^{∞} u_{n}x^{n}

denote the generating function of the sequence (u_{n}). Let’s rock !

(1 − 3x − 4x^{2})F (x) = (u_{0} + u_{1}x) − 3(u_{0}x) + ∑_{n=2}^{∞}(u_{n} − 3u_{n−1} − 4u_{n−2})x^{n}

= (2 + 3x) − 3(2x) + ∑_{n=2}^{∞} 2^{n}x^{n}

= 2 − 3x + \frac{4x^{2}}{1 − 2x}

= \frac{10x^{2} − 7x + 2}{1 − 2x}.

Since

1 − 3x − 4x^{2} = (1 + x)(1 − 4x),

we conclude that

F (x) = \frac{10x^{2} − 7x + 2}{(1 + x)(1 − 4x)(1 − 2x)}.

We seek a partial fraction decomposition

\frac{10x^{2} − 7x + 2}{(1 + x)(1 − 4x)(1 − 2x)} = \frac{A}{1 + x} + \frac{B}{1 − 4x} + \frac{C}{1 − 2x}.  (1)

Clearing denominators, we have 10x^{2} − 7x + 2 = A(1 − 4x)(1 − 2x) + B(1 + x)(1 − 2x) + C(1 + x)(1 − 4x). Gathering coefficients, we get the following system of linear equations to solve

( \begin{matrix}8 & −2 & −4 \\ 6 & 1 & 3 \\ 1 & 1 & 1 \end{matrix} ) ( \begin{matrix}A \\ B \\ C \end{matrix} ) = ( \begin{matrix}10 \\ −7 \\ 2 \end{matrix} ) .

After the usual Gauβ elimination and back substitution (I omit the details), we get the solution

A = \frac{19}{15}, B = \frac{7}{5}, C = −\frac{2}{3}.

Substituting into (1) and using the relation

\frac{1}{1 − t} = ∑_{n=0}^{∞} t^{n},

we conclude that

F (x) = \frac{19}{15} ∑_{n=0}^{∞}(−1)^{n}x^{n} + \frac{7}{5} ∑_{n=0}^{∞} 4^{n}x^{n} − \frac{2}{3} ∑_{n=0}^{∞} 2^{n}x^{n}.

It follows that

u_{n} = \frac{19}{15} · (−1)^{n} + \frac{7}{5} · 4^{n} − \frac{2}{3} · 2^{n}.