109 中山資工所數學考點分析

題型與配分

科目名稱「離散數學」【資工系碩士班甲組】，題號 434004，考試時間 100 分鐘，「不可以」使用計算機（問答申論題），全卷試題僅 1 頁、9 題、100 分。

「沒有詳細步驟就不給分」（卷首明訂），不可以使用計算機。

逐題考點

• 第 1 題（12%）｜相同球放入相異容器（10 顆相同綠球放進 5 個相異容器）
• (a) 6%：每個容器都不能空 → C(10−1, 5−1) = C(9,4)
• (b) 6%：第三個容器必須放偶數顆 → 用生成函數 (1/(1−x))⁴ × (1/(1−x²)) 取 x¹⁰ 的係數
• 第 2 題（10%）｜奇數平方和的整除性：a、b 皆為正奇數，證明 2 | (a²+b²) 但 4 ∤ (a²+b²)。把 a = 2m+1、b = 2n+1 代入得 a²+b² = 4(m²+m+n²+n)+2
• 第 3 題（12%）｜封閉二元運算的計數（|A| = 7）
• (a) 6%：f : A×A → A 共有幾個 → 7⁴⁹
• (b) 6%：其中可交換的有幾個 → 只需決定上三角 + 對角線共 C(7,2)+7 = 28 個位置 → 7²⁸
• 第 4 題（10%）｜鴿籠原理（姓名縮寫）：禮堂有 900 個座位，至少要坐滿幾個才保證有兩人的姓名首字母相同。鴿籠數是 26×26 = 676，所以答案是 677
• 第 5 題（10%）｜有上下界的分配：3600 個相同信封以 25 個為一包分給五個學生團體，每組至少 150、最多 1000。先換單位成「144 包、每組至少 6 包最多 40 包」，再用排容原理
• 第 6 題（12%）｜整數分割的生成函數
• (a) 6%：每個被加數出現偶數次 → ∏ 1/(1−x^{2k})
• (b) 6%：每個被加數本身是偶數 → ∏ 1/(1−x^{2k})（兩者的生成函數相同——這正是題目想讓你發現的Glaisher 型對偶）
• 第 7 題（10%）｜由兩項反推公比：a_n+1 − d·a_n = 0 是等比數列，已知兩項的值反推 d。要注意兩項的下標差距，再開對應次方根
• 第 8 題（12%）｜完全二分圖 K_m,n
• (a) 6%：頂點數 m+n、邊數 mn
• (b) 6%：若 K_m,12 有 72 條邊，則 12m = 72 ⇒ m = 6
• 第 9 題（12%）｜同餘保持 gcd：證明 a ≡ b (mod n) ⇒ gcd(a,n) = gcd(b,n)。做法是證明「a 與 n 的公因數集合」等於「b 與 n 的公因數集合」——由 n | (a−b) 得 d | a ⟺ d | b

這份考卷的難點

1. 第 5 題的雙邊界分配是全卷最繁的一題：先把 25 個一包換算單位、再設變數平移下界、最後用排容原理扣掉超過上界的情況。三個步驟任一出錯就全錯。
2. 第 6 題兩小題的生成函數長得一樣，很多人會以為自己算錯。這其實是分割理論中的經典對偶結果，要敢寫出「兩者相同」並說明理由。
3. 第 3(b) 的可交換運算計數要看出「可交換 ⟺ 運算表對稱 ⟺ 只需決定上三角與對角線」，直接數出 28 個自由位置。
4. 第 9 題是純證明題，佔 12 分。要寫出「d | a 且 d | n ⟺ d | b 且 d | n」的雙向論證，不能只說「顯然成立」。

準備建議

• 第 9 題的 gcd 同餘證明在 112 年第 8 題原封不動重出（連題目文字都一樣），這 12 分等於送分
• 「有上下界的分配」在 113 年第 8 題重出（2800 本書、每包 50 本、五組、至少 200 最多 600），解法完全相同
• 生成函數是中山的第一主力：109（分割）、110（整數解）、112（卷積）、113（遞迴）、114（偶數個 beef）每年都有
• Grimaldi 課本的第 1 章（計數）與第 9 章（生成函數）要讀熟——中山幾乎所有計數題都出自這兩章
• 鴿籠原理的「鴿籠數」要算對：109 是 26² = 676、108 是子集和的範圍、111 是同一題型的變體