300699 Discrete Structures and Complexity, Spring 2011

Tutorial Week 2 (Solutions)

Starred questions introduce new material and / or are central for the learning outcomes of the unit. You are strongly advised to work through these questions. 1.* How many elements does the set {10, 11, . . . , 200} have? How many of them are (a) even? (b) odd? (c) in the range 5059? (d) even and in the range 5059? (e) even but not in the range 5059? (f) either even or in the range 5059? Solution: The set {10, 11, . . . , 200} has 200 10 + 1 = 191 elements. You can pair up each even element except 200 with its odd successor, giving 1911 = 95 pairs. This uses all odd 2 elements, so the number of odd elements is 95 and the number of even elements is 95 + 1 = 96. The number of elements in {10, 12, . . . , 200} which are in the range 5059 is 10. The number which are even and in the range 5059 is 5; so the number which are even but not in the range 5059 is 96 5 = 91. The number which are either even or in the range 5059 is (number which are even) + (number in range 5059) (number even and in range 5059) which is 96 + 10 5 = 101. 2. In a class of 90 students, 37 play the guitar, 26 can speak Chinese, and 10 can do both. How many can either play the guitar or speak Chinese? Solution: By the inclusion-exclusion principle, the number that can do at least one is (number can speak Chinese) + (number can play guitar) (number can do both) that is, 37 + 26 10 or 53. 3. Julia Rabbit, Tony Mallard, and Bozo the Clown recently made statements about climate policy. A survey showed that 25% of people thought that Rabbit was telling the truth, 22% of people thought that Mallard was telling the truth, and 54% thought that Bozo was telling the truth. If 21% thought Rabbit and Bozo were telling the truth, 17% thought Mallard and Bozo were telling the truth, 14% thought all three were telling the truth, and 60% thought at least one was telling the truth, how many thought that both Rabbit and Mallard were telling the truth? Solution: Let R be the set of people who thought Rabbit was telling the truth, M the set who thought Mallard was telling the truth, and B the set who thought Bozo was telling the truth. Let U be the set of all people interviewed. The set of all people who thought Rabbit and Mallard were telling the truth is R M , so the percentage is |RM | . Then |U | |R M B| = |R| + |M | + |B| |R M | |R B| |M B| + |R M B| |R M B| |R| |M | |B| |R M | |R B| |M B| |R M B| = + + + |U | |U | |U | |U | |U | |U | |U | |U | |R M | 60% = 25% + 22% + 54% 21% 17% + 14% |U | |R M | = 17% |U | (We should check that this solution makes sense: Indeed, |RM|B| = 14% 17% = |U should be!) So 17% thought that Rabbit and Mallard were both telling the truth. 4.
|RM | |U | ,

as it

You are about to build a new computer. Given a choice of 4 mainboards, 2 CPUs, 2 types of RAM, and 3 hard disks, how many dierent systems could you build? Solution: This is a four-step process (k = 4), with 4 choices for the rst step, 2 for the second step, 2 for the third step, and 3 for the last, so altogether there are 4 2 2 3 = 48 possibilities. 1

5.

(i) (ii) (iii) (iv) (v)

In how many ways can the letters of the word ALGORITHM be arranged in a row? In how many ways can this be done if the letters A and L must remain together, in that order? In how many ways can this be done if the AL must come at the beginning? In how many ways can three letters of ALGORITHM be selected and written in a row? If the letters of the word ALGORITHM are written in random order, what is the probability that the AL remain together in that order?

Solution: (i) (ii) (iii) (iv) (v) 6.* (i) (ii) (iii) There are 9 letters, all dierent, giving 9! = 362880 ways. You may as well treat AL as a single letter, so this time there are 8! = 40320 ways. We may as well forget about the AL altogether, and just reorder the remaining letters GORITHM. There are 7 of these, so there are 7! = 5040 ways. Nine possibilities for the rst letter, eight for the second, and seven for the third, giving 9 8 7 = 504 altogether. (This is also P (9, 3).) This is
8! 9!

= 1. 9

How many dierent 8-digit telephone numbers are there if the rst digit cannot be zero? How many of these have no repeated digits? How many 8-digit telephone numbers have at least one repeated digit?

Solution: (i) (ii) (iii) 7.* First choose the rst digit (9 possibilities), then the second (10 possibilities), then the third (10 possibilities), and so on. This gives 9 107 = 90000000 numbers altogether. First choose the rst (9 possibilities), then the second (now only 9 possibilities), then the third (8 possibilities), and so on. This gives 9 9 8 7 6 5 4 3 = 1632960. 90000000 1632960 = 88367040.

Assume a wireless network is secured with a WPA2-PSK encryption using a random pre-shared key of length 8 consisting of only lowercase letters (a-z). (i) (ii) Estimate how long a brute-force attack (that is, trying all possible keys until the right one is found) would take on a computer which can test 10 000 keys per second. If the speed of computers increased by a factor of 1000, how long would the key have to be chosen to give at least the same level of security against a brute-force attack?

Solution: (i) There are 26 lowercase letters, so 268 = 208 827 064 576 possible keys. On average, half of these, that is 104 413 532 288, would have to be tested before the right key is found; this would take approximately 1.044 107 s, that is, about 120.8 days. We have to increase the number of possible keys by at least a factor of 1000. Since log26 1000 2.12, we need to increase the key length by at least 3 characters.

(ii)

8.

Gandalf, Frodo, Sam, Merry, and Pippin go out to dinner. (i) (ii) (iii) In how many ways can they be arranged around a circular table? Three of them are to be chosen for an important task. In how many ways can this be done? The ve need to choose from among them a Ringbearer, a Faithful Servant, and a Wise Counsellor. In how many ways can this be done? 2

Solution: (i) First have Gandalf sit down (it doesnt matter where). Then choose someone to be on his right (4 possibilities), then someone to be on that persons right (3 possibilities), then someone to be on that persons right (2 possibilities), then the last person must be on Gandalfs left. So altogether there are 4 3 2 = 24 ways. This is an unordered choice, so the answer is
5 3

(ii) (iii)

= 10.

First choose a Ringbearer (5 ways), then a Faithful Servant (4 ways), then a Wise Counsellor (3 ways). Thus there are 5 4 3 = 60 ways altogether. (This is an ordered choice, since we care who is the Ringbearer, and so on.)

9.

A club consists of 10 men and 15 women. (i) (ii) (iii) (iv) How many ways can a committee of four people be selected? How many ways can it be done with at most one man? How many ways can it be done if the number of men and women must be equal? How many ways can it be done if there must be at least one man and at least one woman?

Solution: (i) (ii) (iii) (iv)

= 12650

The number of ways with no men is 15 = 1365; the number of ways with exactly one man 4 is 15 10 = 4550, so the number of ways with at most one man is 1365 + 4550 = 5915. 3 1 We must choose 2 women ( 4725 ways.
15 2

= 105 ways) and 2 men (

10 2

= 45 ways) giving 105 45 =

The number of men must be one, two or three. With one man, there are 4550 ways (by (ii)). With two men there are 4725 ways (by (iii)). With three men there are 15 10 = 3 1 15 120 = 1800 ways. Thus altogether there are 4550 + 4725 + 1800 = 11075. Alternatively, the number of ways with no men is 1365. The number of ways with no women is 10 = 210, so the number with at least one man and at least one woman is 4 12650 1365 210 = 11075. On the other hand, you cannot argue as follows: There must be at least one man and one woman, so lets get them out of the way rst. There are 10 ways to choose the man and 15 ways to choose the woman. Now there are 9 men and 14 women left, and we must choose any two of these 23. There are 253 ways to do this, giving 10 15 253 = 37950 ways altogether. As you can see, this gives a dierent answer. What is wrong with the reasoning?

10.*

Dont believe something just because you read it in a book. Example 12 in 7.3.3 of Discrete Mathematics for Computer Science by Haggard, Schlipf and Whitesides counts the valid passwords of length 6 formed according to the following rules: Allowed characters are the 26 uppercase letters (A-Z), the 26 lowercase letters (a-z), the 10 digits (0-9), and 22 special characters; overall this makes 84 possible symbols. The password must contain at least 2 letters (a-z, A-Z). The password must contain at least 1 symbol which is a digit or a special character.

The authors argue, incorrectly: Temporarily assume that the required letters in the password occur as the rst two symbols of the password, and that the required [digit or] special character occurs as the last symbol. [. . . ] We will nd that these restrictions add a factor of 60 to the count. and count the number of passwords as (# Passwords) = 60 (# Possible at position 1) (# Possible at position 6) = 60 52 52 84 84 84 32 = 3 077 129 502 720 The factor 60 is later (in 7.12.4) derived as the number of possibilities for the positions of the two required letters and the required digit or special character: 6 62 = 15 4 = 60. 2 1 (i) (ii) Show that their result cannot be correct. Explain the mistake in their argument.

Solution: (i) The number of strings of length 6 which can be formed from 84 symbols without any restrictions is 846 = 351 298 031 616 < 3 077 129 502 720, so there cannot be 3 077 129 502 720 valid passwords of length 6. It is not true that one can x the positions of the required symbols and make up for that by multiplying with the number of possibilities for xing the positions. As the results suggest, their method is heavily over-counting valid passwords. For example, the password a a a a a 1 is counted 10 times: once for letters in positions 1 & 2, once for letters in positions 1 & 3, and so on. By the way: the valid passwords are not over-counted by a constant factor, so it is not easy to control this and x their approach. If you want to know how to count these passwords correctly, check the Learning Guide; one of the sample questions contains this counting problem.

(ii)

11.*

Permutations of multisets A multiset is an unordered collection of objects, in which each object can occur more than once. The number of times an element x occurs is called the multiplicity of x. Counting permutations of a multiset requires a little bit of extra care, as we shall see. As an example, count in how many ways the letters of the word SEE can be arranged: There are only 3 possibilities: SEE, ESE, EES. Note that this is not the number of permutations of a set with 3 elements, that is, 3! = 3 2 1 = 6. The reason is obvious: Swapping the two identical letters doesnt give a new word. (i) Prove that the number of permutations of a multiset which has k dierent types of elements with the multiplicities n1 , . . . , nk is (n1 + + nk )! n1 ! n 2 ! nk ! Hint: Think about how the rearrangements of the letters SEE are related to those of the letters SEe and think about how this can be generalised. (ii) (iii) In how many ways can the letters of the word PARRAMATTA be rearranged? In how many ways can the letters of the word COONABARABRAN be rearranged?

Solution: (i) The permutations can be counted using the same idea as the one we used in the lecture for counting unordered selections: Imagine making all objects of the same type distinguishable, for example by colouring them. Then, one has n1 + + nk dierent objects which can be arranged in (n1 + + nk )! ways. 4

However, any two rearrangements which only dier by permutations of objects of the same type among themselves actually are the same; we have over-counted. By how much? Well, there are n1 ! ways of permuting the objects of type 1 among themselves, n2 ! ways of permuting the objects of type 2 among themselves, and so on. By the multiplication principle, there are n1 !n2 ! nk ! of permuting objects of the same type among themselves, so we have over-counted by that factor. ++n Hence, the number of permutations of the multiset is (n11!n2 !nk )! as claimed. n k! (ii) There are 10 letters altogether, with 4 As, 2 Rs, and 2 Ts, so there are 10! = 37800 4! 2! 2! arrangements. (iii) Thirteen letters, with 2 Os, 2 Ns, 4 As, 2 Bs, and 2 Rs, giving 13! = 16216200 4! 2! 2! 2! 2! arrangements. 12.* Combinations with repetitions In how many ways can n identical objects be distributed into k buckets? Hint: The possibilities for n = 2 and k = 3 can be represented as follows: | | || | | || || | |

Solution: As the hint suggests, distributing n identical objects onto k buckets is equivalent to inserting k 1 separator tokens into a string containing n identical objects. The string with the separator tokens inserted has length n + k 1, and the only question is, which k 1 of these n + k 1 positions contain separators. The possibilities for this are easily counted: it is an unordered selection. Hence, the number of possibilities is n+k1 k1 = n+k1 n = (n + k 1)! n! (k 1)!

13.*

[harder, just for fun] In the lecture you have seen the algorithm RepeatedSquaring for computing the power ab of two positive integers a and b, which is given on the right. Prove that the algorithm is correct, that is, that for any legal input a, b N the algorithm halts with output ab . Hint: A positive integer b can be written uniquely in the form b = bi 2i + bi1 2i1 + + b1 21 + b0 20
Input: a, b N Output: ab 1: r := 1; d := a; e := b 2: while e > 0 do 3: if e is odd then 4: r := r d 5: e := e div 2; d := d2 6: return r

with bi1 , . . . , b0 {0, 1} and bi = 1. The string bi bi1 b1 b0 is called the binary representation of b.

Solution: Consider the binary representation bi bi1 b1 b0 of the input b. We show that after k passes through the loop (k = 0, 1, . . . ), we have r = abk1 2
k1 +b k2 ++b 21 +b 20 1 0 k2 2

()

and that the algorithm terminates after exactly i + 1 passes through the loop. (Note that this in particular shows that the output is ab , since bi 2i + bi1 2i1 + + b1 21 + b0 20 = b.) The variable e is initialised to b (line 1) and divided by 2 in every pass through the loop (line 5). Division by 2 simply means to delete the last bit of the binary representation and shift the remaining bits one position to the right. Hence after k passes through the loop (k = 0, 1, . . . ), the binary representation of e is bi bi1 bk+1 bk . (Line 5 has been executed k times, so the last k bits have been deleted and the remaining bits have been shifted by k positions to the right.) This shows in particular that e = 0 if and only if k > i. (Recall that bi = 1.) Hence the while loop terminates when k = i + 1 (that is, after exactly i + 1 passes) as claimed. The variable d is initialised to a and squared in every pass through the loop (line 5). Hence after k 2 2 k passes through the loop (k = 0, 1, . . . ), we have d = a2 = a2 . Before the rst pass through the loop (that is, after k = 0 passes), we have r = 1 = a0 , so equation () holds. Now assume that equation () holds after k passes and consider the (k + 1)-st pass. Since the binary representation of e is bi bi1 bk+1 bk , e is odd if and only if bk = 1. We distinguish the cases e even (that is, bk = 0) and e odd (that is, bk = 1): If e is even, then r is not modied, that is, after the (k + 1)-st pass we have, since bk = 0, r = abk1 2
k1 +b k2 ++b 21 +b 20 1 0 k2 2

= abk 2

k +b

k1 +b k2 ++b 21 +b 20 1 0 k1 2 k2 2

If e is odd, then r is multiplied by a2 , that is, after the (k + 1)-st pass we have, since bk = 1, r = a2 abk1 2
k k1 +b k2 2 k2 ++b 21 +b 20 1 0

= abk 2

k +b

k1 2

k1 +b

k2 ++b 21 +b 20 1 0 k2 2

Since in either case, equation () holds after the (k + 1)-st pass, and since e is either even or odd, we can conclude that equation () holds after the (k + 1)-st pass. Since we know that equation () holds after 0 passes, we then can conclude that it holds after 1 pass, then further that it holds after 2 passes, and so on, and were done. (This is called a proof by induction.) You will hear more about logic, valid arguments and proofs in the Logic module.