math vic

Exam #2: Solution

5.1 Prove by mathematical induction that 1 1 1 1

... 1 2 4 2 2

n n      (5 points)

1 1

1 1 1

2 2  

Assume 1 1

1 1 1 1 ... 1

2 4 2 2 n n 

    

Then 1 1 1

1 1 1 1 1 1 1 2 1 2 1 1 ... 1 1 1 1

2 4 2 2 2 2 2 2 2 2 2 2 n n n n n n n n n  

               

QED

5.2 Using strong induction, prove that for every 8n  , 3 5n a b    for some nonnegative integers a and b. (5 points)

8 1 3 1b   

9 3 3 0 5   

10 0 3 2 5   

Assume for all k n where 10k  that 3 5k a b    for some nonnegative

integers a and b.

Specifically, for 3k n  , let a and b be such that 3 3 5n a b     .

Then  1 3 5 3 5n a b a b         where 1a a  

QED

A3/3.1 Describe a non-recursive algorithm that takes a list of positive integers 1 2 , ,...,

n a a a and finds the largest even

number on the list. Write your answer in pseudo-code or any well-known procedural language like Python, Java, C++,

….

You may assume that you have a function “even” built in to your language. “even” will return TRUE for even numbers

and FALSE for odd numbers.

You may also assume that there will be at least one even number on the list. (5 points)

E.g. For the list 1 2 3 4 5 , , , ,a a a a a = 2, 3, 6, 5, 4 your program should return 6.

procedure Largest_Even ( 1 2 , ,..., :

n a a a positive integers)

largest_even = 0

for i = 1 to n

if i

a is even and i

a  largest_even

index = i

largest_even = i

a

return index

8.3 (7.3) Write a recursive algorithm to solve the same problem as above. (5 points)

You may assume that you have all of the primitive functions for lists: (first(L), rest(L), …)

procedure Largest_Even (L: list of integers)

if L is empty return 0

else if first(L) is even and first(L) > Largest_Even(rest(L))

return first(L)

else

return Largest_Even(rest(L))

8.3.3 Consider the procedure T given below.

procedure T (n: positive integer)

if n < 2 return 1

else for i = 1 to 5

x = x + 1

return        4 4 4n n nT T T          

Let ( )f n be the number of additions in the procedure for an input of n and note that ( )f n satisfies a recurrence relation

of the form     dncbnfanf  / .

a) Determine the values of a, b, c, and d. (4 points)

3a  4b  5c  0d 

b) Apply The Master Theorem (given below) to T to determine its complexity. (1 points)

Master Theorem

Given     dncbnfanf  / , then

)(nf is

 

 

 log log

b

d d

d d

a d

n if a b

n n if a b

n if a b







   

 



Since d

a b , the complexity is  4log 3n

6.5 a) How many ways to rearrange the letters AARDVARK ? 8!

3!2! (2 points)

b) A donut store has 100 different types of donuts. You want to buy 1,000 donuts.

i) How many different ways can you do this? 1099

99

     

(4 points)

ii) How many different ways can you do this if you need at least 5 of each type? 599

99

     

(5 points)

8.5 80 workers were interviewed for an electrical, painting or plumbing position. Every worker knew at least one skill.

45 workers knew electrical, 45 knew how to paint and 50 knew plumbing. 15 workers knew all three skills.

How many workers knew exactly two skills? (5 points)

         

     

     

# # # # # # # #

80 = 45 + 45 + 50 # # # 15

# # # 75

A B C A B C A B A C B C A B C

A B A C B C

A B A C B C

             

      

     

6.1/6.3 Emmy has 5 different fingernail polish colors (red, orange, yellow, green, blue) and wants to paint the nails on her

left hand. Red, orange and yellow are considered warm colors. Green and blue are considered cold colors. (2.5 points each)

a) How many different ways can she paint her first three nails? 3

5

b) How many ways can she paint her first three nails if she uses a different color for each one? 5 4 3 

c) How many ways can she paint all of her nails if the first three nails must be a warm color and the last two must be a

cold color? She is allowed to repeat as many colors as she wants. 3 2

3 2

d) Same question as c), except she is not allowed to repeat any color? 3 2 1 2 1   

7.1 A Discrete Math quiz has 10 True/False questions. An unprepared student guesses for each problem and has 50%

change of getting the problem right. (10 points)

a) What is the probability that the student gets all 10 questions correct? 10

1

2

b) What is the probability that the student gets exactly one question correct? 10

10

1

2

     

c) What is the probability that the student gets exactly 7 questions correct? 10

10

7

2

     

6.2 A certain class has 100 students. Recall that there are seven days in a week and 12 months in a year.

a) Find the largest number that can be used to fill in the blank to make a true statement. (2.5 points)

There are at least 15 students born on the same day of the week.

b) Find the largest number that can be used to fill in the blank to make a true statement. (2.5 points)

There are at least 9 students born in the same month.

6.4 (5.4) Prove that n m n n k

m k k m k

           

      (5 points)

Story: The left hand side is the number of ways of picking a committee of size

m and then an executive subcommittee of size k from n different students.

The right hand side is the number of ways to pick the executive committee of

size k from the n students, then fill out remaining m k committee members |

from the remaining n k students.

Proof from the definition:

       

 

 

          

! ! !

! ! ! ! ! ! !

!! !

! ! ! ! !! !

n m n m n

m k m n m m k k n m m k k

n n k n kn n

k m k n k k k m k n mm k n k m k

       

     

       

        