Question

A) What is the minimum and maximum number of zeros in a 4-bit string? Use roster notation and find the range of f.

(The first elements in the range is f(0,0,0,0) = 0)

B) For the functions below, indicate whether the function is: Onto ,One-to-one ,Bijection.

i) f: Z → Z, f(x) = 5x - 4

ii) f: Z → Z, f(x) = 5x - 4

C) Start with the number n = 54527. Divide n by 5 and round the result down to an integer. Keep repeating the division and rounding step until the resulting number is less than 5. How many divisions are performed? You can use a calculator for this problem, but you should not have to actually perform all of the divisions. Provide an integer answer.

D) Start with the number n = 32844. Divide n by 7 and round the result down to an integer. Keep repeating the division and rounding step until the resulting number is less than 7. How many divisions are performed? Provide an integer answer.

This is the discerete structures problem.

This is the discerete structures problem.

Answer 1

A) Minimum number of zeros occur when all the inputs are 1 and maximum number of zeros occur when all the inputs are 0. Since there are 4 inputs here, there can be at most 4, at least 0 zeros.

B)

i)Given  , we shall find whether it is one to one and onto. To check weather is one to one, consider and such that . We shall prove that

Add 4 and divide by 5 on both sides, then

, which proves that is one to one.

In order to prove that is onto, consider

Add 4 and divide by 5 on both sides, then

In other words, .

We can also see that is also one to one. By which we can conclude that is onto as well.

Since is both one to one and onto, we can conclude that is an bijection.

ii) same

C) We can treat this as converting 54527 to base 5. Number of digits (0-4) required to represent it in base-5 notation - 1 is the number of divisions.

Consider and . Since is between them, it requires 7 digits to get represented in base-5 form. So, actual number of divisions would be 6.

D) Similar to the previous one

Consider and . Since is between them, it requires 6 digits to get represented in base-7 form. So, actual number of divisions would be 5.