lvy>試卷(2022/01/21)

# 101 年 - 101 國立中山大學_碩士班招生考試_資工系：離散數學#105909

【非選題】
1.

1. Assume that a sequence of numbers is deined by x0 = 0, x1 = 1, and ＞ 1. Find the generating function for the sequence, and then find an explicit expression for .

【非選題】
2.2. Solve the following recurrence equation for T(n), n ＞ 0. if n =1 T(n)=(2(In/2])+logn, ifn＞1. 10,

【非選題】
3.3. Assume that, for any two people : and y, a is a friend of y if and only if y is a friend of x. Show that, in any group of two or more people, there are always two people with exactly the same number of friends inside the group.

【非選題】
4.

4. Let G be a simple graph. A path of G is a sequence of distinct vertices v0,v1, Uh such that and are adjacent for each i = 1,2,..., k. The length of the path v0, v1 , ..., is k. The degree of a vertex is the number of edges incident to that vertex. Show that if the minimum degree of G is greater than or equal to k, then G has a path whose length is at least k.

【非選題】
5.

5. A lattice path from (x0, y0) to in the ay plane is defined as a sequence of points (x0, y0), (x1,y1), , such that each and each, ± 1,i =1,2, n - 1. How many lattices paths are there from (0,1) to (10,3)? How many of them do not touch or cross the t axis?

【非選題】
6.

6. Fibonacci numbers are delined as f0 = 0, f1= 1 and for n ＞ 1. Show that is even, for every positive integer k.

【非選題】
7.
7. Let S = {1,2,... ,n}.

【題組】(a) Prove that if n is even then any n/2 + 1 subset of S contains two numbers whose sum is n + 1.

【非選題】
8.【題組】(b) In general, determine the value k such that any k subset of S contains two numbers whose sum is n + 1.

### 懸賞詳解

#### 國二自然上第三次

2.加熱一塊25℃、質量50克的鐵塊（比熱0.113卡 ／公克．℃），使其溫度上升至65 ℃，則此 鐵塊需要吸收多少的熱量？ (A) 3250卡 (B)2000卡 (C) 226卡 (D) 113�...