Exam 1 Math 205 Fall 1998



Exam 3 Math/ECE 276 Winter 2016

Name: ___________________ This is a closed book exam. You may use the formula sheet handed out with the exam. Show all work and explain any reasoning which is not clear from the computations. Turn in this exam along with your answers. However, don't write your answers on the exam itself; leave them on the pages with your work. Also turn in the formulas; put them on the formula pile.

1. (11 points) Consider the sequence an, where a1 = , a2 = ( , a3 = ( ( , … ,

an = (  ( (…( . Give a recursive formula for an.

2. (18 points) You have to test six new software products that your department is considering for adoption. In how many different orders can you test them if

i. You don’t test LogicLab first, and

ii. You test the C++ compiler immediately before or after CircuitSim?

This is just one problem where i. and ii. must hold simultaneously.

3. (18 points) Design Point, Inc has 20 engineers with the following backgrounds

i. 4 are UM grads with degrees in ME.

ii. 7 are UM grads with degrees in ECE.

iii. 5 are MSU grads with degrees in ME.

iv. 4 are MSU grads with degrees in ECE.

In how many ways can you select a 5 person design group that has at least one UM grad and at least one MSU grad and at least one ME and at least one ECE?. Hint: Subtract the bad ones from the total. Then add back in the ones you subtracted twice.

4. (17 points ) Consider words made from the letters a, b, and c. Let Sn be the number of n letter words made from these 3 letters which don't contain two consecutive a's. (For example, abaca is a five letter word which meets this condition but baacb is not.) Find a recurrence relation for Sn. Find S1, S2, S3, and S4. Explain your reasoning. Hint: Consider separately those which start with an a and those which don't start with an a.

5. (18 points) Find the general solution of the recurrence relation an = 6an-1 - 8an-2 + 3.

6. a. (3 points) Define what it means for a relation in general to be transitive. Use the symbol ( for the relation, i.e. a ( b means a is related to b, and a b means a is not related to b.

b. (15 points) Consider the following relation, (, where the objects being related are positive integers. a ( b if a > b2. For example, 5 ( 2 since 5 > 22 = 4, but 5 3 since 5 32. Is this relation transitive? If so, show why. If not, find a counter-example. Begin by translating the general definition of transitive in your answer to part a into the context of this particular relation.

Solutions

1. an =

2. First count the number where the C++ compiler comes right before CircuitSim. Then we can treat the C++ compiler and CircuitSim as one unit. Then we have five items (since C++ and CircuitSim are one unit). (4 pts) We need to count the number of ways to put them in order with the restriction that LogicLab is not first. There are 4 choices for the first. Having made that choice there are 4 choice for the 2nd. Having chosen the first two, there are 3 choices for the 3rd. Then 2 choices for the 4th and 1 choice for the last. So there are 4(4(3(2(1 = 4(4! = 96 ways if C++ is right before CircuitSim. (6 + 6 pts) There are an equal number where C++ is right after CircuitSim. So the total is 2(96 = 192 ways. (4 pts)

3. The total number of 5 person design groups is . (6 pts) We need to subtract the "bad' ones. One group of bad ones are the ones that are all UM grads. There are of these. Another is the ones that are all MSU grads, There are of these. There are that are all ME grads and that are all ECE grads. (4 pts) Subtracting these four groups gives - 2( - 2(. (3 pts) However, we have subtracted some twice, namely the ones that are all ECE majors from UM and the ones that are all ME majors from MSU. There are groups that are all ECE majors from UM and = 1 that are all ME majors from MSU. (3 pts) We have to add these two groups back in giving - 2( - 2( + + 1 = 15,504 - 2(462 - 2(126 + 21 + 1 = 14,350. (2 pts)

4. If the word starts with an a then the next letter could be b or c and the remaining n-2 letters can be any which don't have two consecutive a's. There are Sn-2 of these that begin with ab and Sn-2 that begin with ac. So there are 2Sn-2 words that start with an a. If the word starts with a b then the remaining n-1 letters can be any that don't have two consecutive a's. There are Sn-1 of these. The same if it starts with a c. So there are 2Sn-1 words that don't start with an a. So Sn = 2Sn-1 + 2Sn-2. (13 pts) Furthermore S1 = 3 since the three one letter words that don't have two consecutive a's are a, b and c. Also S2 = 8 since the eight two letter words that don't have two consecutive a's are ab, ac, ba, bb, bc, ca, cb and cc. Using the recurrence relation one has S3 = 2S2 + 2S1 = (2)(8) + (2)(3) = 22 and S4 = 2S3 + 2S2 = (2)(22) + (2)(8) = 60. (4 pts)

5. First solve the homogeneous equation bn = 6bn-1 – 8bn-2. Try bn = rn. Plug in to get rn - 6rn-1 + 8 = 0 or r2 - 6r + 8 = 0 or (r-2)(r-4) = 0. So r = 2 and r = 4 are solutions of the characteristic equation and bn = 2n and bn = 4n are solutions to the homogeneous equation. So the general solution to the homogeneous equation is bn = A2n + B4n for any constants A and B. (8 pts) Now find a particular solution. Since the inhomogeneous part is a constant, we try to find a particular solution that is a constant, i.e. we try an = K where K is to be determined by substituting into the equation. Doing this we obtain K = 6K – 8K + 3 or 3K = 3 or K = 1. So an = 1 is a particular solution. (7 pts) The general solution is the sum of a particular solution and the general solution of the equation: an = 1 + A2n + B4n. (3 pts)

6. a. A relation ( is transitive if whenever a ( b and b ( c this implies a ( c.

b. If we translate the definition of transitive into the relation given, then we want to know if a > b2 and b > c2 implies a > c2. (6 pts) Note that since b is a positive integer one has b2 ( b. So a > b2 implies a > b. This coupled with b > c2 implies a > c2 which shows that the this relation is transitive. (9 pts)

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download