MAN 240 : Diskret matematik

Tentamen 040603

Lösningar

F.1 (i) First choose the three positions for the zeroes ⇒ ( \begin{matrix}16 \\ 3 \end{matrix} ) choices.

Next choose the four positions for the ones ⇒ ( \begin{matrix}13 \\ 4 \end{matrix} ) choices.

Now you have 9 positions left, and each can be filled with any one of the 8 digits from 2 − 9. Thus, by the multiplication principle, there are 8^{9} choices for these remaining positions.

A final application of the multiplication principle then implies that the total number of possible credit card numbers is

( \begin{matrix}16 \\ 3 \end{matrix} ) · ( \begin{matrix}13 \\ 4 \end{matrix} ) · 8^{9}.

(ii) Subtract from n! the number of permutations which move at most two numbers. For i = 0, 1, 2 let A_{i} denote the number of permutations which move exactly i numbers. Then

A_{0} = 1 (the identity permutation)

A_{1} = 0 (can’t move just one number)

A_{2} = ( \begin{matrix}n \\ 2 \end{matrix} ) (choose a pair of nos. to interchange).

Hence, the answer is n! − 1 − ( \begin{matrix}n \\ 2 \end{matrix} ).

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

A → B → E → H → K → I → J → G → F → C → D → A.

(ii) χ(G^{∗}) ≥ 3 since G^{∗} contains many triangles. On the other hand, if we apply the greedy algorithm to the nodes ordered alphabetically, then we get a 3-coloring, namely (the colors are 1, 2, 3)

A 1 G 1
B 2 H 2
C 3 I 3
D 2 J 2
E 1 K 1
F 2

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

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

{A, D}, {A, B}, {B, E}, {E, C}, {C, F },
{C, G}, {G, J}, {J, I}, {I, K}, {I, H} (or {J, H}).

The total weight of this tree is 1 + 2 + 1 + 5 + 1 + 2 + 1 + 1 + 2 + 7 = 23.

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

Step Choice of edge Labelling
1  AD  D := 1
2  AB  B := 2
3  BE  E := 3
4  AC/DC  C := 8
5  CF  F := 9
6  DG/CG  G := 10
7  EH  H := 11
8  GJ  J := 11
9  JI/EI  I := 12
10  IK  K := 14

Hence the shortest path from A to K has length 14. Depending on the choices you made in Steps 4,6,8, there are four possibilities for the shortest path, namely

A → B → E → I → K,
A → D → G → J → I → K,
A → D → C → G → J → I → K,
A → C → G → J → I → K.

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

A − C − E − H − K, ϵ = 5,
A − B − E − H − K, ϵ = 1,
A − C − G − I − K, ϵ = 2,
A − C − F − E − H − K, ϵ = 1,
A − D − G − J − K, ϵ = 1.

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

Edge Flow Edge Flow Edge Flow
(A, B) 1  (C, G)  2  (G, I)  2
(A, C) 8 (D, G) 1  (G, J)  1
(A, D) 1  (F, E)  0  (I, H)  1
(C, B) 0 (G, F) 0  (J, I)  0
(D, C) 0 (E, H) 6 (H, K) 7
(B, E) 1  (E, I)  0  (I, K)  2
(C, E) 5  (F, I)  1  (J, K)  1
(C, F) 1

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

c(S, T) = c(B, E) + c(A, C) + c(A, D) = 1 + 8 + 1 = 10, v.s.v..

F.3 This is Mantel’s Theorem. See my extra lecture notes for Day 9.

F.4 To simplify notation, if v is a vertex of the graph G, let G\v denote the graph obtained by deleting v and all edges through it.

Now since G is connected it has a spanning tree T. Being a tree, T has at least 2 leaves (see exercise 8.5.2 in Biggs). Let v be a leaf of T. Then T \v is still connected and is a spanning tree for G\v, which implies that G\v is also connected.

F.5 Everything is contained in my extra lecture notes for Day 5.

F.6 Let

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

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

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

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

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

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

Since

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

we conclude that

F (x) = \frac{60x^{2} − 29x + 4}{(1 + x)(1 − 5x)(1 − 3x)}.

We seek a partial fraction decomposition

\frac{60x^{2} − 29x + 4}{(1 + x)(1 − 5x)(1 − 3x)} = \frac{A}{1 + x} + \frac{B}{1 − 5x} + \frac{C}{1 − 3x}.  (1)

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

( \begin{matrix}15 & −3 & −5 \\ −8 & −2 & −4 \\ 1 & 1 & 1 \end{matrix} ) ( \begin{matrix}A \\ B \\ C \end{matrix} ) = ( \begin{matrix}60 \\ −29 \\ 4 \end{matrix} ) .

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

A = \frac{31}{8}, B = \frac{5}{4}, C = −\frac{9}{8}.

Substituting into (1) and using the relation

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

we conclude that

F (x) = \frac{31}{8} ∑_{n=0}^{∞}(−1)^{n}x^{n} + \frac{5}{4} ∑_{n=0}^{∞} 5^{n}x^{n} − \frac{9}{8} ∑_{n=0}^{∞} 3^{n}x^{n}.

After a little tidying up, it follows that

u_{n} = \frac{1}{8} (31 · (−1)^{n} + 2 · 5^{n+1} − 3^{n+2}) .