106 年 - 106 國立中山大學_碩士班招生考試_資工系(甲組)：離散數學#105791-阿摩線上測驗
106 年 - 106 國立中山大學_碩士班招生考試_資工系(甲組)：離散數學#105791
1. Let x1, x2, , be a sequence of n integers. A consecutive subsequence of x1,x2,... ., is a subsequence for some i, j, 1 ≤ i ≤ j ≤n. Show that for any k, I k n, there is a consecutive subsequence whose sum is divisible by k.
2. Assume that a sequence of numbers is deined by x0 = 0, x1 = 1, and = ＞ 1. Find generating function for the sequence, and then find an explicit expression for un.
There are 7 problems in this test. No calculators are allowed. Write down detailed steps for
the solution to each problem. Otherwise, no credits for that problem will be given.
4. A bipartite graph is a graph whose vertices can be partitioned into two subsets X and Y so that each edge has one end in X and the other end in Y: A cycle of G is a sequence of vertices u0, u1, ..., such that each vertex is distinct, except ,and ； are adjacent for each i = 1,2,. ,I. The length of the cycle is l. A k-cube is a graph whose vertices are binary strings of length k, for some integer k ＞ 0.Two vertices are adjacent if and only if they differ in exactly one bit.
6. Fibonacci numbers are deined as f0 = 0, f1= 1 and for n ＞.1. Show that is even, for every positive integer k. .
(a) Show that if'n is prime, then n divides for every i, 1 ≤i＜n.