課程名稱︰離散數學 課程性質︰系必修 課程教師︰林永松 開課學院：管理學院 開課系所︰資管系 考試日期（年月日）︰06/21 考試時限（分鐘）：180分 是否需發放獎勵金：是 （如未明確表示，則不予發放） 試題 : Discrete Mathematics Final Exam 1.Use the Principle of Induction to prove that any integer amount of postare from 18 cents or more can be made from an infinite supply of 4-cent and 7-cent stamps. 2.Let a1=2, a2=9, and an=2a(n-1)+3a(n-2) for n≧3. Show that an≦3^n for all positive integer n. (註：1、2、n、(n-1)、(n-2)為下標) 3.In the questions below give a recursive definition with initial condition(s) (a) an = 2 ^1/(2n) ←2的2n分之一次方 (註：an的n為下標) (b) S = {0.1, 0.01, 0.001, 0.0001, ......} 4.In the questions below nine people (Ann, Ben, Cal, Dot, Ed, Fran, Gail, Hal and Ida) are in a room. Five of them stand in a row for a picture. (a) In how may ways can this be done if Hal or Ida (but not both) are in the picture? 1;36(b) In how may ways can this be done if Ann and Ben are in the picture, but not standing next to each other? 5.Show that if five points are picked on or in the interior of a square of side length 2, then there are at least two of these points no farther than √2 apart. 6.Let S1,S2,S3...,S101 be 101 bit strings of length at most 9. Prove that there exist two strings, Si and Sj, where i≠j, that contain the same number of 0s and the same number of 1s. (For example, strings 001001 and 10100 contain the same number of 0s and the same number of 1s.) 7.Please answer the following questions: (a) Find the number of solutions to x+y+z=32, where x,y, and z are nonnegative integers. (b) Answer Part(a), but assume that x≧7 and y≧15. 8.Please answer the following questions: (a) List all positive integers m and n such that K(m,n) has a Hamilton circuit. (b) List all positive integers m and n such that K(m,n) has a Hamilton path but no Hamilton circuit. 9.Prove or disprove that these two graphs are isomorphic. １ ╱│╲ ╱ │ ╲ ●─────● ２──┼──３ ∕ ╲ ╱ ﹨ │ │ │ ∕ ╲ ╱ ﹨ │ │ │ ●─── ╳ ───● ４──┼──５ ﹨ ╱ ╲ ∕ ╲ │ ／ ﹨ ╱ ╲ ∕ ╲│／ ●─────● ６ 10.Suppose you have a graph G with vertices V1,V2,...,V17. Explain how you use the adjacency matrix A to find (a) The number of paths from V5 to V3 of length 12. (b) The length of a shortest path from V5 to V3. --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.242.6