Discrete Mathematics Exam Questions 1998

SECTION 1

1. (a) How many arrangements of the letters A, C, D, G, I, O, P, T contain at least one of the words CAT, DOG and PIG?

(b) Solve the following recurrences:

(i) a_{0} = 0, a_{1} = 1, a_{n} = 2a_{n−1} + 15a_{n−2} for n ≥ 2, (ii) a_{0} = 0, a_{1} = 1, a_{2} = 6, a_{n} = a_{n−1} + 5a_{n−2} + 3a_{n−3} for n ≥ 3.

(c) Find the general solutions of the following congruence, or show that no solution exists: 1227x ≡ 1143 (mod 1998).

2. (a) Suppose that

\frac{1 + X + X^{2}}{(1 − 2X)^{3}} = ∑_{n=0}^{∞} a_{n}X^{n} = a_{0} + a_{1}X + a_{2}X^{2} + · · · .

Find a general formula for the a_{n}.

(b) Let σ = (2 3 4)(5 6 7)(8 9 10) and τ = (1 10)(2 9)(3 8)(4 7)(5 6) be elements of S_{10}. Compute σ^{−1}, σ^{2} στ, τσ and στσ^{−1} and find the order and sign of each.

(c) Find the n-vertex trees with the following Prüfer codes:

(i) (2, 8, 8, 1, 8, 3) where n = 8; (ii) (10, 1, 10, 9, 1, 2, 9, 2) where n = 10.

SECTION 2

3. (a) Bridge is a game played with a standard pack of 52 cards (4 suits and 13 values). A hand contains 13 cards. How many bridge hands contain at least three cards in each suit? How many bridge hands contain four cards in each of two suits, three cards in a third suit and two cards in the last suit? [Give answers both exactly, in terms of binomial coefficients, and numerically to 4 significant figures.]

(b) How many anagrams are there of the word EMENDED? How many of them start with D? How many end in E? How many neither start with D nor end in E?

(c) Show that the sum

S_{n} = 1 − \binom{n}{2} + \binom{n}{4} − \binom{n}{6} + ⋯

is the real part of (1 + i)^{n}. Show that S_{n} = 0 if n ≡ 2 (mod 4) while S_{n} = (−4)^{n/4} if n is a multiple of 4.

4. (a) Show by induction that

∑_{j=1}^{n}(2j − 1)^{3} = 1^{3} + 3^{3} + 5^{3} + ⋯ + (2n − 1)^{3} = 2n^{4} − n^{2}.

(b) Recall the Fibonacci numbers are defined by the recurrence: F_{1} = F_{2} = 1 and F_{n} = F_{n−1} + F_{n−2} for n ≥ 3 . Show that

\frac{X}{1 − X − X^{2}} = ∑_{n=1}^{∞} F_{n}X^{n} = F_{1}X + F_{2}X^{2} + F_{3}X^{3} + · · · .

Find an explicit formula for F_{n}.

(c) The Lucas numbers are defined by L_{1} = 1, L_{2} = 3 and L_{n} = L_{n−1} + L_{n−2} for n ≥ 3. Find an explicit formula for L_{n} and deduce that F_{2n} = F_{n}L_{n} and 5F_{n}^{2} = L_{2n} − 2(−1)^{n}.

5. (a) Show that a number A with digits a_{r−1}a_{r−2} ⋯ a_{2}a_{1}a_{0} (so that A = a_{0} + 10a_{1} + 100a_{2} + ⋯ + 10^{r−1}a_{r−1}) is divisible by 9 if and only if the sum of its digits is divisible by 9. Also show that A is divisible by 11 if and only if a_{0} − a_{1} + a_{2} − ⋯ + (−1)^{r−1}a_{r} is divisible by 11.

(b) Find the least positive number a with 9^{999} ≡ a (mod 17).

(c) Complete the following Latin square:

\begin{matrix}A & B & C & D & E & F \\ B & D & E & F & C & A \\ C & A & F & E & D & B \\ D & F & A \\ E \\ F \end{matrix} .

Find a pair of orthogonal Latin squares of order 7.

6. (a) You take a pack with an even number 2m of cards, and perform the following shuffle: split the pack into two equal halves, then interleave the halves so that the top card of the lower half becomes thenew top card, the top card of the upper half is now second from the top, the second card in the lower half is now third, and so on. For instance if m = 6 and the cards were labelled 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 and 12 from the top, then the new ordering is 7, 1, 8, 2, 9, 3, 10, 4, 11, 5, 12, 6. How many of these shuffles does one need to restore the original order when

(i) m = 10? (ii) m = 12?

(b) Explain why each permutation is a product of transpositions. Express (1 4 8 2 7)(3 6 5) and (1 3 10)(2 4 7 9)(5 6 8) as products of transpositions.

(c) How many permutations in S_{10} have one 3-cycle, three 2-cycles and one 1-cycle? How many permutations in S_{10} have order 3?