加載中. ..
PDF
102年公務人員特種考試外交領事人員及外交行政人員
考試、102年公務人員特種考試法務部調查局調查人員
考試、102年公務人員特種考試國家安全局國家安全情
報人員考試、102年公務人員特種考試民航人員考試、
102年公務人員特種考試經濟部專利商標審查人員考試試題
代號：70370
考 試 別： 專利商標審查人員
等 別： 三等考試
類 科 組： 資訊工程
科 目： 離散數學
考試時間： 2小時 座號：
※注意：
禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
（請接背面）
全一張
（
正面
）
一、平面上有 n個環形，已知環形兩兩相交於相異兩點，並且任何三環形不會相交於一
點。這些環形將平面分割成為若干區域，如下圖所示，以 an來表示所分割成的區域
個數。我們觀察得到 a1=2, a2=4, a3=8 等。
試求出 a4，並說明 an=an−1+2(n−1)。（10 分）
直接求出 an的通式；或藉觀察 2=12−1+2, 4=22−2+2, 8=32−3+2，推測 an的通
式，並予以證明。（10 分）
a1=2 a2=4 a3=8
二、
說明在一個邊長為 1的正三角形裏，任選 5點，必有兩點相距不超過 1/2；任選
10 點，必有兩點相距不超過 1/3。（10 分）
若在邊長為 1的正三角形裏，任選 f(n)點，必有兩點相距小於或等於 1/n，試決
定滿足此一性質的最小正整數 f(n)的通式。（10 分）
三、自正整數集合{1,2,3,…,n}依序隨機選取 n次，每次每個元素被選取的機率一樣。
試求：
所得數列正好有 n個相異整數出現的機率。（10 分）
所得數列正好有 n−1個相異整數出現的機率。（10 分）
102年公務人員特種考試外交領事人員及外交行政人員
考試、102年公務人員特種考試法務部調查局調查人員
考試、102年公務人員特種考試國家安全局國家安全情
報人員考試、102年公務人員特種考試民航人員考試、
102年公務人員特種考試經濟部專利商標審查人員考試試題
代號：70370
考 試 別： 專利商標審查人員
等 別： 三等考試
類 科 組： 資訊工程
科 目： 離散數學
全一張
（
背面
）
四、
在下面三個集合之間，分別建立一一對應關係：
多重集合（multiset）{a1
∞,a2
∞,…,ak∞}（即每一元素 ai可不限次數出現）的所有r
個元素子集合；方程式 x1+x2+…+xk=r的非負整數解(x1,x2,…,xk)；及有 r個1和
k−1個∗的多重集合的所有重排（permutations）。（10 分）
試分別針對 x1≥0, x2≥0, …, xk≥0和x1≥a1,x2≥a2,…,xk≥ak兩種情況，求出方程式
x1+x2+…+xk=r的非負整數解(x1,x2,…,xk)的個數。（10 分）
五、若 Qn是一個以{(x1,x2,…,xn)|xi=0,1}為頂點集合，兩頂點(x1,x2,…,xn), (y1,y2,…,yn)
相鄰若且唯若{i|i≤n，xi,yi不相等}的元素個數為 1的圖形。
試分別畫出圖形 Q2,Q3，並在其上分別給出漢彌頓迴圈（Hamilton circuits）。
（10 分）
說明如何利用 Qn−1的漢彌頓迴圈，造出 Qn的漢彌頓迴圈。（10 分）