Discrete Mathematics教学习题（华南理工）Tutorial11-Answer.pdfVIP

Discrete Mathematics I (Semester 2, 2013-2014) Tutorial 11 - Answer Refer to Chapter 3.2, 3.4 Date: May-2014 1. Show that if there are 30 students in a class, then at least two have last names that begin with the same letter. Answer: According to Pigeonhole Principle, 30/26 = 2 2. There are 38 different time periods during which classes at a university can be scheduled. If there are 677 different classes, how many different rooms will be needed? Answer: N = 677 r = 38 677/38 = 18 3. Let n be a positive integer. Show that in any set of n consecutive integers there is exactly one divisible by n. Answer: Let a, a+1, …, a + n – 1 be the integers in the sequence The integers (a+i) mod n, i = 0,1,2,…,n-1 are distinct, because 0 (a+j) – (a+k) n whenever 0 k j n – 1 Because there are n possible values for (a+i) mod n and there are n different integers in the set, each of these values is taken on exactly once Therefore, (a+i) mod n will equal to 0 4. How many ordered pairs of integers (a, b) are needed to guarantee that there are two ordered pairs (a , b ) and (a , b ) such that a mod 5 = a mod 5 and b mod 5 = b mod 1 l 2 2 l 2 l 2 5? Answer: Discrete Mathematics I – Tutorial 11 1 Let us consider the set of all ordered pairs (a mod 5, b mod 5). For any integer n, n mod 5 = 0, 1, 2, 3 or 4 So, a mod 5 can take on 5 values and b mod 5 can also take 5 values. So, the total number of such ordered pairs possible is 5 *