課程名稱︰離散數學
課程性質︰電機系二選一必修
課程教師︰郭斯彥
開課學院：電資學院
開課系所︰電機系
考試日期（年月日）︰110.06.21
考試時限（分鐘）：110
試題 :
1. (10 points, 1 point each) Answer T(True) or F(False) for each of the follow-
ing:
(a) There exist integers x and y such that 21x + 54y = 3/
(b) Let m be a positive integer, and a_1,...,a_n be integers. If m divides
a_1a_2...a_m, then m divides a_i for some i.
(c) Rolling a total of 8 when three dice are rolled is less likely than when t-
wo dice are rolled.
(d) The next largest permutation of 234651 is 235146.
(e) If a is an integer and m is a positive integer, then a^{m-1} ≡ 1(mod m).
(f) Recursive algorithm is always more efficient than its iterative counterpart
(g) 1 + 10 + 100 + .. + 10^{1000} = 10^{1001} - 1.
(h) Let I_n denote the number of injective functions from {1,2,...,n} to
{1,2,...,55}. If m \geq n then it must be the case that I_m \geq I_n.
(i) In a group of five people, where each two are either friends or enemies, t-
ere must be either three mutual friends, or three mutual enemies.
(j) If the set of prime numbers that divide x is the same as the set of prime
numbers that divide y, then x = y.
2. Short answers (14 points, 2 points each)
(a) Suppose k \geq 1 and (x_1,...,x_k) is a randomly chosen k-permutation of
{1,...,n} (i.e., an ordered arrangement of k distinct elements, chosen uni-
formly from all such arrangements). What is the probability that it is a s-
trictly increasing sequence, i.e., x_1 < x_2 < ... < x_k.
(b) A palindrome is a string whose reversal is identical to the string. How ma-
ny bit strings of length n are palindromes?
(c) The parliament of an unnamed country has 57 members from the Workers Party
and 72 from the Fat Cats Party. How many ways are there to select an 11
member committee, including a chairperson, if the chairperson must be a
member of the majority party, and the other 10 members must be evenly split
between the two parties? Express the answer as a formula for the number. Y-
ou do not need to evaluate the formula.
(d) How many strings of length 9 over the alphabet {a, b, c, d} have either ex-
actly three b's or exactly five c's?
(e) What is the number of ways to place n distinguishable balls into k disting-
uishable bins where no two balls are placed in the same bin? You may assume
that n \leq k.
(f) What is the number of ways to divide d dollar bills among p people? Assume
dollar bills are indistinguishable and people are distinguishable.
(g) How many solutions does x_1 + ... + x_k = n have if each x_i (1 \leq i \leq
k) must be a positive integer (at least 1)?
3. (4 points, 2 points each) A binary relation R on set A is an equivalence re-
lation if R is reflexive, symmetric and transitive. A binary relation R on set
A is circular iff for all a, b, c \in A (if aRb and bRc then cRa). Prove the f-
ollowing statements.
(a) If R is reflexive and circular then R is an equivalence relation.
(b) If R is an equivalence relation then R is circular.
4. (15 points, 3 points each) Calculate the following:
(a) How many distinct functions f : {1, 2, 3, 4, 5} -> {1, 2, 3} are there, fr-
om the set {1, 2, 3, 4, 5} to the set {1, 2, 3}, whose range is a set of s-
ize exactly 2?
(b) How many surjective functions from a set with 10 elements to a set with 6
elements are there? (Hint: count how many non-surjective functions there
are.)
(c) Let n be an integer. How many different integers are there in the following
set:
{n, \floor*{\frac{2n+1}{2}}, n+1/2, \ceil*{\frac{2n-1}{2}} ?
(d) Calculate the remainder (-56)^{2016} mod 13.
(e) Find x mod100 for the following:
17x + 57 ≡ 22 (mod 100).
5. (6 points, 3 points each) Recursive definition and function
(a) Give a recursive definition of the set of positive integers not divisible
by 5.
(b) Give the function that reverses a string (Hint: a string of length greater
than 0 can be represented as xy where x is the first symbol of the string
and y is the rest of the string.
For example, for string abcd, we have x = a and y = bcd.)
6. (6 points, 3 points each)
https://imgur.com/AObKaly
(a) Let n = 22, and e = 3. What is the decryption key, "d" ? Briefly explain/
justify your answer.
(b) Explain why one can find the decryption key in part (a), but in general ha-
ving only“n”and“e”won't let you easily find the decryption key for“re-
al-world" instances of RSA.
7. (4 points) Use induction to prove the following (you must use induction, any
other proof technique will get zero points).
f_1 + ... + f_n = f_{n-2} - 1 for all n \geq 1, where f_n is the n-th Fibon-
acci number.
8. (6 points, 3 points each) Given the information
10^{44460} ≡ 32287 mod 44461
10^{50850} ≡ 1 mod 50851
(a) What can you conclude about whether 44461 is a prime or composite number
, and why? (you must give reasons to get full credit).
(b) What can you conclude about whether 50851 is a prime or composite number
, and why? (you must give reasons to get full credit).
9. (4 points) Find the number of permutations of the 26 English letters that do not contain
not contain any of the strings RUN, WALK, or SWIM in consecutive positions.
(Hint: inclusion-exclusion principle)
10. (9 points) The following questions are independent of each other.
(a) Find the general solution to the recurrence a_n = 8a_{n-1} - 16a_{n-2}
(3 points)
(b) Find the general solution to the recurrence a_n = 8a_{n-1} + 9a_{n-2}
(3 points)
(c) Find a particular solution to the recurrence a_n = 8a_{n-1} + 9a_{n-2}
+ 16n (3 points)
11. (6 points, 2 points each)
(a) Find a recurrence relation for the number of ways to climb n stairs if the
the person climbing the stairs can take one stair or two stairs at a time.
Explain your answer.
(b) What are the initial conditions?
(c) How many ways can this person climb 11 stairs?
12. (4 points) Use Bezout's theorem to prove that if a is relatively prime both
to b and to c, then a is relatively prime to bc.
That is: gcd(a, b) = gcd(a, c) = 1 -> gcd(a, bc) = 1.
13. (8 points, 4 points each)
(a) Suppose p is a prime number other than 2 (so p is odd). Show that for
every integer a not divisible by p, if the congruence
x^2 ≡ a (mod p) has a solution, then a^{(p-1)/2} ≡ 1 (mod p).
(b) Suppose that the prime number p in part (a) has the form p = 4k + 3, w-
here k is an integer. Show that if a^{(p-1)/2} ≡ 1 (mod p), then
x ≡ a^{k+1} (mod p) is a solution of the congruence in part (a).
14. (4 points) Pigeonhole principle
There are 51 houses on a street. Each house has an address between 1000 and
1099, inclusive. Show that at least two houses have addresses that are consecu-
tive integers.