Discrete Mathematics, Summer 2002

 

Quiz #3

 

Problem 1.

 

Let A = {m Ξ Z | m = 3i + 2 for some integer i}, B = {p Ξ Z | p = 3j – 1 for some integer j}. Is it true that A equals to B?

 

Solution.

 

Yes, A equals to B. Just notice that if one takes j to be i + 1, then both sets are the same due to the fact that 3 * j – 1 = 3 * (i + 1) – 1 = 3 * i + 2

 

Problem 2.

 

Determine whether the following statement is true: for all sets A, B and C, if A Λ B and B Λ C, then A Λ C

 

Solution.

 

The statement is false. Let A = {1}, B = {2}, C = {1, 3}. Then the premises are true, but the conclusion is false.

 

Problem 3.

 

Show that for all sets A and B: (A Θ B) – B = A – B

 

Solution.

 

First we need to show that if x is in (A Θ B) – B then x is in A – B. If x is in (A Θ B) – B, then x is not in B and x is in (A Θ B). Since x is not in B, it means that x is in A. So we have x is in A and x is not in B. Hence we got the desired result that x is in A – B.

 

Second we need to show that if x is in A – B then x is in (A Θ B) – B. Since x is in A – B, we get that x is in A and x is not in B. Thus, x is in (A Θ B) and x is not in B. Thus, we conclude that x is in (A Θ B) – B.

 

Problem 4.

 

In how many ways can the letters of the word ALGORITHM be arranged in a row if the letters GOR must remain together (in order) as a unit?

 

Solution.

 

The word ALGORITHM has 9 letters. Due to the fact that 3 of them, namely GOR, are treated as an atomic unit, we have 7 letters in effect. This means that the number of different words is 7!

 

Problem 5.

 

How many integers from 1 to 1000 are neither multiples of 4 nor multiples of 11?

 

Solution.

 

At first we will compute the number of integers, which are either multiples of 4 or multiples of 11. To do so we will use inclusion/exclusion formula. First, we need to compute the number of integers from 1 to 1000, which are multiples of 4: there are 250 of those. Second, we need to compute the number of integers from 1 to 1000, which are multiples of 11: there are 90 of those. Third, we need to compute the number of integers, which are multiples of both 4 and 11 or in other words multiples of 44: there are 22 of those. The inclusion/exclusion formula tells us that the number of integers which are either multiples of 4 or multiples of 11 is 250 + 90 – 22 = 318. Thus, the number of integers which are neither multiples of 4 not multiples of 11 is 1000 – 318 = 682.

 

Problem 6.

 

Suppose that three computer boards in a production run of forty are defective. A sample of four is selected. What is the probability that the chosen sample has at least one defective board?

 

Solution.

 

The total number of different ways to select a sample is C(40, 4). The total number of different ways to select four computer boards so that none of them is defected is C(37, 4). Thus, the desired probability is: 1 – C(37, 4) / C(40, 4)

 

Problem 7.

 

A store sells 30 kinds of balloons.

 

a)      How many different combinations of 24 balloons can be chosen?

b)      What is the probability that a combination of 60 balloons chosen at random will contain at least one balloon of each kind?

 

Solution.

 

a)      We just need to apply a formula for an unordered selection with repetition: in our case n = 30 and r = 24, thus we get C(53, 24)

b)      The total number of ways to select 60 balloons without restrictions is C(89, 60). To find the number of ways to select 60 balloons in such a way that we have each kind of balloon at least once is the same as to find the number of integer solutions of the following equation: x1 + x2 + … + x30 = 60 so that each xi > 0. We introduce new variables yi = xi – 1. Now we have the following equation: y1 + y2 + … + y30 = 30 and each yi is just non-negative. The number of integral solutions of this equation is C(59, 30). Thus the probability is C(59, 30) / C(89, 60)

 

Problem 8.

 

Show that: C(2, 2) + C(3, 2) + … + C(n, 2) = C(n + 1, 3)

 

Solution.

 

We will use mathematical induction.

 

Base case: n = 2, left side is C(2, 2) = 1, right side is C(3, 3) = 1

Assumption: C(2, 2) + C(3, 2) + … + C(n, 2) = C(n + 1, 3)

We need to show that C(2, 2) + C(3, 2) + … + C(n, 2) + C(n + 1, 2) = C(n + 2, 3)

 

C(2, 2) + C(3, 2) + … + C(n, 2) + C(n + 1, 2) = C(n + 1, 3) + C(n + 1, 2). Using Pascal’s formula we get C(n + 2, 3) as desired.

 

Problem 9.

 

Find the coefficient of term a5b7 in the expanded expression of (a – 2b)12

 

Solution.

 

The value of the coefficient is: C(12, 5) * (-2)7 = -128 * C(12, 5)

 

Problem 10.

 

Find Hamming distance of two bit strings: 00110 and 10111

 

Solution.

 

Hamming distance between two bit strings is the number of differences, which is 2.

 

Problem 11.

 

Design a finite state automata that accepts all strings of 0’s and 1’s that have even number of 1’s.

 

Solution.

 

Just introduce two states: s1 and s2. s1 is an initial state and it is also an accepting state. When in state s1 or s2, the input symbol 0 makes you loop and remain in the same state. When you are in state s1 and get symbol 1, then this moves you to state s2 and similarly, when you are in a state s2 and get symbol 1, then this moves you to state s1.

 

Problem 12.

 

If f: R ΰ R and g: R ΰ R and f and g are both one-to-one. Is (f + g) one-to-one?

 

Solution.

 

No. Let f(x) = x and g(x) = -x. Obviously, f and g are one to one. However, f + g is always 0, which is not one-to-one.

 

Problem 13.

 

How many integers from 100 through 999 must you pick to ensure that at least two of them have a digit in common? Numbers 256 and 530 have the common digit 5.

 

Solution.

 

One needs to pick 10 integers. This is the case because there are 9 integers that do not have any digits in common: 111, 222, 333, 444, …, 999. However, any 10th integer to be picked up would have a digit in common.

 

Problem 14.

 

Find composition of the function f(x) = (x + 1) / (x – 1) with itself.

 

Solution.

 

f(f(x)) = (f(x) + 1) / (f(x) – 1) = ((x + 1) / (x – 1) + 1) / ((x + 1) / (x – 1) – 1) = 2x / 2 = x

 

Problem 15.

 

Provide a bijective function that maps a set of positive integers to a set of non-negative integers.

 

Solution.

 

F(x) = x – 1