MAS1003 Discrete Mathematics CA test: Tuesday 23rd November 1999, 9.05–9.55 am

Please attempt all questions

1. A group of students play a card game 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) three-two-one: three cards in one suit, two in a second suit, one in a third suit (and none in the fourth), for example: A♠ Q♠ 5♠ 7♢ 5♢ J♣; (ii) flat: two cards in each of two distinct suits, one card in each of the two remaining suits, for example: 7♠ J♡ 9♡ 10♢ 3♢ K♣. (NB there are \binom{52}{6} = 20358520 hands altogether.)

[10,10]

Solution (i) There are 4 ways of choosing the one suit to receive 3 cards and \binom{13}{3} ways of selecting the three values in that suit. After these have been

chosen there are 3 ways of choosing the one suit to receive 2 cards and \binom{13}{2} ways of selecting the two values in that suit. Again, after these have been chosen there are 2 ways of choosing the one suit to receive 1 card and 13 ways of selecting its value. Therefore there are

4\binom{13}{3} × 3\binom{13}{2} × 2 × 13 = 6960096

hands of this form. [10] (ii) There are \binom{4}{2} ways of choosing the two suits to receive 2 cards and \binom{13}{2} ways of selecting the two values in each of those suits. After these have been chosen there are 13 ways of choosing the value of the card in each of the remaining two suits, Therefore there are

\binom{4}{2}\binom{13}{2}^{2} × 13^{2} = 6169176

hands of this form. [10]

2. How many anagrams has the word MILLENNIUM? How many of them contain at least one of the words ILL and LINE?

[8,12]

Solution The word MILLENNIUM has 10 letters: 2 Ms, 2 Is, 2Ls, 1 E, 2Ns and 1 U. Thus it has

\frac{10!}{2!2!2!1!2!1!} = 22680

anagrams. [8]

Those anagrams of MILLENNIUM containing ILL are arrangements of the 8 blocks: ILL, M, E, N, N, I, U and M. There is 1 ILL, 2 Ms, 1 E, 2 Ns, 1 I and 1 U, and so there are

\frac{8!}{1!2!1!2!1!1!} = 10080

anagrams of MILLENNIUM containing ILL.

Those anagrams of MILLENNIUM containing LINE are arrangements of the 7 blocks: LINE, M, I, L, N, U and M. There is 1 LINE, 2 Ms, 1 I, 1 L, 1 N and 1 U, and so there are

\frac{7!}{1!2!1!1!1!1!} = 2520

anagrams of MILLENNIUM containing ILL.

Those anagrams of MILLENNIUM containing both ILL and LINE are arrangements of the 5 blocks: ILLINE, M, N, U and M. There is 1 ILLINE, 2 Ms, 1 N, and 1 U, and so there are

\frac{5!}{1!2!1!1!} = 60

anagrams of MILLENNIUM containing ILL.

By the sieve principle there are

10080 + 2520 − 60 = 12540

anagrams of MILLENNIUM containing at least one of ILL or LINE. [12]

3. (i) Find the least positive integer a with 11^{1999} ≡ a (mod 19). (ii) Find the least positive integer b with 7^{100} ≡ b (mod 29).

[10,10]

Solution (i) We have

11^{2} = 121 ≡ 7 (mod 19)

and

11^{3} ≡ 7 × 11 = 77 ≡ 1 (mod 19).

It follows that

11^{1999} = 11^{3×666+1} = (11^{3})^{666} × 11 ≡ 11 (mod 19)

and so we have a = 11. [10] (ii) We have

7^{2} = 49 ≡ 20 (mod 29),
7^{3} ≡ 20 × 7 = 140 ≡ 24 (mod 29),
7^{4} ≡ 24 × 7 = 168 ≡ 23 (mod 29),
7^{5} ≡ 23 × 7 = 161 ≡ 16 (mod 29),
7^{6} ≡ 16 × 7 = 112 ≡ 25 (mod 29)

and

7^{7} ≡ 25 × 7 = 175 ≡ 1 (mod 29).

Hence

7^{100} = 7^{7×14+2} = (7^{7})^{14} × 7^{2} ≡ 7^{2} ≡ 20 (mod 49)

and so we have b = 20. [10]

4. Solve the following recurrences:

(i) a_{0} = 1, a_{1} = 2, a_{n} = 7a_{n−1} − 12a_{n−2} for n ≥ 2; (ii) a_{0} = 1, a_{1} = 2, a_{n} = 4a_{n−1} − a_{n−2} for n ≥ 2.

[10,10]

Solution (i) The auxiliary equation is X^{2} − 7X + 12 = 0 which has roots 3 and 4. These are distinct, so the solution has the form a_{n} = r3^{n} + s4^{n}. We have

1 = a_{0} = r + s  (1)

and

2 = a_{1} = 3r + 4s.  (2)

Subtracting 3 times (1) from (2) gives s = −1, and from (1) we see that r − 1 = 1 or r = 2. Hence a_{n} = 2(3^{n}) − 4^{n}. [10] (ii) The auxiliary equation is X^{2} − 4X + 1 = 0 which has roots 2 + \sqrt{3}, and 2 − \sqrt{3}. These are distinct, so the solution has the form a_{n} = r(2 + \sqrt{3})^{n} + s(2 − \sqrt{3})^{n}. We have

1 = a_{0} = r + s  (1)

and

2 = a_{1} = (2 + \sqrt{3})r + (2 − \sqrt{3})s.  (2)

We subtract 2 − \sqrt{3} times (1) from (2) to give

2 − (2 − \sqrt{3}) = (2 + \sqrt{3})r − (2 − \sqrt{3})r

or

\sqrt{3} = (2\sqrt{3})r.

Hence r = 1/2, and from (1), s = 1 − r = 1/2 also, and so

a_{n} = \frac{1}{2} [(2 + \sqrt{3})^{n} + (2 − \sqrt{3})^{n}] .

[10]

5. Suppose that the k-digit positive integer A has digits a_{k−1}, a_{k−2}, …, a_{1}, a_{0} as read from left to right. Show that A is divisible by 11 if and only if a_{0} − a_{1} + a_{2} − a_{3} + ⋯ + (−1)^{k−1}a_{k−1} is divisible by 11.

[20]

Solution We have

A = a_{0} + 10a_{1} + 10^{2}a_{2} + 10^{3}a_{3} + ⋯ + 10^{k−1}a_{k−1}.

Note that 10 ≡ −1 (mod 11). By repeatedly multiplying this congruence by itself we get 10^{2} ≡ (−1)^{2} = 1 (mod 11), 10^{3} ≡ (−1)^{3} = −1 (mod 11) and in general 10^{r} ≡ (−1)^{r} (mod 11). Hence

A ≡ a_{0} − a_{1} + a_{2} − a_{3} + ⋯ + (−1)^{k−1}a_{k−1} (mod 11).

It follows that A is divisible by 11, i.e., A ≡ 0 (mod 11), if and only if a_{0} − a_{1} + a_{2} − a_{3} + ⋯ + (−1)^{k−1}a_{k−1} ≡ 0 (mod 11), i.e., a_{0} − a_{1} + a_{2} − a_{3} + ⋯ + (−1)^{k−1}a_{k−1} is divisible by 11. [20]

RJC 26/11/199