[試題] 100下 陳健輝 離散數學 期中考1
課程名稱︰離散數學
課程性質︰資訊系選修
課程教師︰陳健輝
開課學院：電資學院
開課系所︰資訊系
考試日期（年月日）︰2012/4/2
考試時限（分鐘）：120
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
Examination #1
(範圍：Combinatorics)
(For each problem, please provide computation details, not only the answer.)
1.Two cases of soft drinks, 21 bottles of one type and 21 of another, are
distributed among four surveyors who are conducting taste tests. In how many
ways can the 42 bottles be distributed so that each surveyor gets at least
two bottles of each type?
(10%)
2.A ship carries 40 flags, 10 each of red, white, blue and black. Eight of
these flags are placed on a vertical pole in order to communicate a signal
to other ships. How many of these signals use an even number of blue and an
odd number of black flags? (10%)
3.Let a_n te the number of ordered rooted binary trees on n vertices.
(1) Find a recurrence relation for a_n. (5%)
(2) Is the recurrence relation of (1) linear of non-linear? Why? (3%)
(3) Is the recurrence relation of (1) homogeneous or non-homogeneous? Why?
(2%)
4.Jeremy Lin decides to purchase an apartment in New York, and so he considers
taking out a loan of $300,000. If the loan is to be paid back with 20 years
and the interest rate per year is 2%, then what payment must he make at the
end of each year? Please round off the yearly payment to the nearest whole
number(四捨五入取整數值), using the approximation of (1 + 0.02)^{-20}≒0.673
(10%)
5.The homogeneous solution (i.e., {a_n}^h) to a_n + 4a_{n-1} + 4a_{n-2} = f(n),
n≧2, is c_1(-2)^n + c_2n(-2)^n. What are the forms of particular solutions
(i.e. {a_n}^p) for the following f(n):
(1) 7; (2) n^2+1; (3) 9(-2)^n; (4) 6n(-2)^n; (5) n^2(-2)^n ? (2% each)
(For this problem, you are required to provide the answers only, not the
details.)
6.Solve a_n - 2a_{n-1} = 4^{n-1}, n≧1, a_0 = 1, by the method of generating
function. (10%)
7.At an 11-week conference in mathematics, Sharon met six of her friends from
college. During the conference she met each friend at lunch 30 times, every
pair of them 14 times, every trio eight times, every foursome four times,
each set of five once, but never all six at once. If she had lunch every day
during the 77 days of the conference, how many days she had lunch alone?
(10%)
8.Explain why the number of partitions of n into m summands is equal to the
number of partitions of n into summands with m being the largest summand.
(10%)
9.Consider the Hanoi tower problem. Let A_n be the minimal number of disk moves
required to transfer n disks from peg 1 to peg 3. Explain why
a_n = 2a_{n-1} + 1. (10%)
A.Please provide a combinatorial proof, not an inductive proof, for the
principle of inclusion and exclusion, i.e. the number of elements in a set
that satisfy none of conditions c_1, c_2, ..., c_t is equal to
___ ___ ___
N(c_1 c_2 ... c_t) = N - ΣN(c_i) + ΣΣN(c_i c_j) - ΣΣΣN(c_i c_j c_k)
1≦i≦t 1≦i<j≦t 1≦i<j<k≦t
+ ... + (-1)^t N(c_1 c_2 ... c_t). (10%)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.217.34.144
※ 編輯: suhorng 來自: 61.217.34.144 (04/02 19:37)
推
04/02 21:42, , 1F
04/02 21:42, 1F
→
04/02 22:33, , 2F
04/02 22:33, 2F
→
04/04 20:52, , 3F
04/04 20:52, 3F