MAS1003 Discrete Mathematics CA test: Tuesday 24th November 1998, 9.05–9.55 am

Please attempt all questions

1. A group of students play an unorthodox form of Poker where each player is dealt a hand of six cards from a standard pack (4 suits and 13 values). How many hands are there of each of the following types?

(i) two threes: three cards in each of two different values, for example: 3♠ 3♡ 3♣ J♠ J♢ J♣; (ii) three pairs: two cards in each of three different values, for example: 4♠ 4♣ 10♠ 10♢ K♣ K♠; (iii) all different: all six cards have different values, for example: 2♡ 3♣ 8♠ 9♢ Q♡ A♠. (NB there are \binom{52}{6} = 20358520 hands altogether.)

[12 marks]

2. Prove, by induction on n, that

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

for all integers n ≥ 1.

[10 marks]

3. (i) Find the least positive integer a with 7^{99} ≡ a (mod 15); (ii) Find the least positive integer b with 9^{101} ≡ b (mod 17).

[8 marks]

4. Solve the following recurrences:

(i) a_{0} = 1, a_{1} = 11, a_{n} = a_{n−1} + 12a_{n−2} for n ≥ 2; (ii) a_{0} = 1, a_{1} = 1, a_{n} = 2a_{n−1} − 10a_{n−2} for n ≥ 2.

[10 marks]

5. Show that a positive integer A is divisible by 9 if and only if the sum of its (base-ten) digits is divisible by 9.

[10 marks]

[Total marks: 50]

Examiner: Dr Robin Chapman