课程名称︰离散数学 课程性质︰系必修 课程教师︰林永松 开课学院：管理学院 开课系所︰资管系 考试日期（年月日）︰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