課程名稱︰組合學一
課程性質︰數學系選修（數學所必修）
課程教師︰張鎮華
開課學院：理學院
開課系所︰數學系（所）
考試日期（年月日）︰2014年11月14日
考試時限（分鐘）：8:00 ~ 13:00
是否需發放獎勵金：是
（如未明確表示，則不予發放）
Those with * are for extra credits. It is suggested only to work on them after
you finish the unmarked questions and still have extra time.
1. Recall that a Steiner system S(l,m,n), where l<m<n, is a pair (X,B) with
|X|=n and B is a family of some m-subsets of X satisfying the condition
that every l-subset of X is in exactly one member of B.
(1) Prove that if there is a Steiner system S(2,4,n), then n=1,4 (mod 12).
(2) Construct Steiner system S(2,4,13).
*(3) Consturct Steiner system S(2,4,n) for infinitely many n.
2. Recall that a family F of subsets of a set X is intersecting if A,B∈F,
imply A∩B≠{}.
(1) Prove that if F is an intersecting family of subsets of [n], then
|F|≦2^(n-1).
(2) Denote a_n the number of intersecting families of subsets of [n] with
exactly 2^(n-1) subsets. Determine a_n for 1≦n≦5. Justify your answer.
*(3) Prove that if n=2m then a_n≧2^m.
3. (1) Let (A_1,A_2,...,A_n) be a family of subsets of [n] such that the
incidence matrix of the family is invertible. Prove that this family
has an SDR.
(2) Give a necessary and sufficeint condition for a family (A_1,A_2,...A_n)
to have exactly one SDR.
4. The number f(n) of steps required to solve the "Chinese rings puzzle" with n
rings satifies f(1)=1 and f(n+1)= 2f(n), if n is odd; 2f(n)+1, if n is even.
(1) Prove that f(n+2) = f(n+1) + 2f(n) + 1.
(2) Find a formula for f(n).
5. You need to justify your answers in the following questions.
(1) Find the number of subsets of [n] of size divisible by 2.
(2) Find n=4 mod8, find the number of subsets of [n] of size divisible by 4.
*(3) Find the number of subsets of [n] of size divisible by 3.