課程名稱︰離散數學
課程性質︰資工系選修
課程教師︰陳健輝
開課學院：電資
開課系所︰資工系
考試日期（年月日）︰107/04/11
考試時限（分鐘）：兩小時
試題 :
Solutions to Examination #1 (範圍：Counting Techniques)
(題目6可直接列答，其他題目務必詳列計算過程或詳述理由)
1. Find the general solution for a_n+2 - 6a_n+1 + 9a_n = 3(2^n) + 7(3^n), where
n ≧ 0. (10%)
2. At a 12-week conference, Sharon met seven of her friends. During the
conference she met each friend at lunch 32 times, every pair of them 14
times, every foursome four times, each set of five twice, and each set of
six once, but never all seven at once. If she had lunch every day during
the 84 days of the conference, how many days did she have lunch alone?
(10%)
3. There are up to 4^10 + p ×3^9 + q ×2^8 + r 10-digit telephone numbers,
where only the digits 1, 3, 5 and 7 are used and each digit appears at least
twice or not at all. Find p+q+r. (10%)
4. There are p ×C(w, a) + q ×C(w, b) + r ×C(w, c) ways to distribute 120
identical envelopes among four students so that each gets at least 5, but no
more than 40, envelopes. Find w, p*q*r, and a+b+c. (10%)
5. Suppose you plan to take out a loan of 100,000 dollars with interest rate
2% per year and pay it back in 20 years. Then there will be a Constant pay-
ment P = α*(β - (1.02)^-20)^-1 you must make at the end of each year. Wh-
at are α and β? (10%)
6. Consider the problem of Hanoi towers with n = 4. Let D1, D2, D3, D4 denote
the four disks from top to bottem and P1, P2, P3 denote peg 1, peg 2, peg3,
respectively. The following procedure, with some steps omitted, can transf-
er D1, D2, D3, D4 from P1 to P3, where "Dk : Pi -> Pj" means "move Dk from
Pi to Pj". Please complete the procedure by providing the details of the
omitted steps. (10%)
(1) D1 : P1 -> P2; (9) D1 : P2 -> P3;
(2) D2 : P1 -> P3; (10) D2 : P2 -> P1;
(3) D1 : P2 -> P3; (11) (omitted)
(4) D3 : P1 -> P2; (12) D3 : P2 -> P3;
(5) (omitted) (13) D1 : P1 -> P2;
(6) (omitted) (14) D2 : P1 -> P3;
(7) (omitted) (15) D1 : P2 -> P3;
(8) (omitted)
7. For n ≧ 0, evenly distributed 2n points on the circumference of a circle,
and label these points cyclically with 1, 2,..., 2n. Let a_n be the number
of ways to connect these 2n points into n chords so that none of them inte-
rsect. The case for n = 3 is shown in the following figure.
https://i.imgur.com/GsAhQfb.jpg
Explain why a_n = a_0 ×a_n-1 + a_1 ×a_n-2 + a_2 ×a_n-3 + ... +
a_n-2 ×a_1 + a_n-1 ×a_0 holds. (10%)
8. For n ≧ 1, let a_n be the number of ways to write n as an ordered sum of
positive integers, where each summand is at least 2. For example, a_5 = 3
because 5 = 5 = 2 + 3 = 3 + 2. Find a recurrence relation for a_n and exp-
lain your answer. (10%)
9. Suppose n = p ×q ×r, where p, q, r are three prime numbers. Show that the
number of integers m with 1 ≦ m ≦ n and gcd(m, n) = 1 is equal to
n ×(1-1/p) ×(1-1/q) ×(1-1/r). (10%)
10.Show that there are -C(-8, 37) ways to select seven nonconsecutive integers
from {1, 2,..., 50}. (10%)