Discrete Mathematics

Test File

Summer 2005

Exam #1

1.) Let our "universe" be U={a, b, c, d, e, f, g, h, i, j, k}. Let A={a, b, c, d}, B={a, e, i}, and C={a, b, e, i}. Evaluate each of the following.

a.) Evaluate (AC) B.

b.) Evaluate (AB)^CC.

c.) Evaluate (B C) \ A.

d.) Do A, B and C form a partition of U? Why or why not?

2.) Let A = {a, b, c} and B = {3, 4}. Write out all elements of A x B.

3.) Using A from #2, find Ã(A) (power set of A).

4.) Prove that (A È B) Ç C = (A Ç C) È (B Ç C).

5.) Disprove the following statement by giving a counterexample.

The difference of any two odd integers is odd.

6.) Prove that the difference of the squares of any two odd numbers is even.

7.) Use the contrapositive to prove the following.

Suppose n is a positive integer. If 7n + 4 is even, then n is even.

8.) Construct a truth table to verify that:

~(P Ù Q) Ù ~Q = ~Q

9.) Construct a truth table for:

~(P Ú Q) Þ ~Q

10.) Do not actually do the proof but explain what you would need to do in order to prove the following:

The integer a is a multiple of 3 if and only if a can be written as a sum of three consecutive integers.

Exam #2

1.) Prove the following.

There exists a unique additive identity for the real numbers.

2.) Prove the following.

The sum of a rational number and an irrational number is irrational.

3.) Prove the following.

Let m be a positive integer. Prove that there exists a positive integer, k, such that (m - n)² > m² for all n > k.

4.) Prove the following.

For every natural number, n, .

5.) Prove the following.

For every natural number, n, (n!)² < (n²)!.

6.) If 12 eggs are each to be dyed a single solid color and five colors are available, what can you say about the number of eggs of the same color?

7.) Coins are randomly removed from a piggy bank containing 12 pennies, eight nickels, ten dimes, and three quarters. How many coins must be removed to guarantee:

a.) three pennies?

b.) three coins of the same kind?

c.) three quarters?

d.) a pair of pennies and a pair of dimes?

e.) a pair of one type coin and a pair of another type coin?

8.) Prove the following:

Any three integers contain a pair whose sum is even.

9.) Fifty ping-pong balls, numbered from 1 to 50, are placed in a vat. How many must be drawn to ensure a pair whose sum is 50? (Be sure to show all of your work.)

10.) Consider the real number 0.123456789101112131415161718192021... whose digits to the right of the decimal are formed by writing the natural numbers in order. Prove that this number is irrational.

Exam #3

1.) Use the Euclidean algorithm to find the gcd(203, 91). Show your work. You must use this method to receive credit.

2.) Use prime factorization to find the following for 670824 and 858000. Show your work. [Note: 670824 = 2³ x 3² x 7¹ x 11³ and 858000 = 2⁴ x 3¹ x 5³ x 11¹ x 13¹.]

a.) gcd(670824, 858000)

b.) lcm(670824, 858000)

3.) Use the continued fraction method to find the gcd(203, 91).

4.) Determine whether or not 1870 and 5187 are relatively prime. You may use whatever method you want but be sure to show all work.

5.) Find the prime factorization of 4158000.

6.) Prove the following.

If a, b and c are a Pythagorean triple, then at least one of a, b and c is even.

7.) Find the number of efficient paths from A to B.

A
	B

8.) Prove that there are infinitely many primes.

9.) For each integer, n, below, determine whether or not n | 112233445566. Be sure to show all necessary work.

a.) 2 b.) 3 c.) 5 d.) 6

e.) 7 f.) 8 g.) 10 h.) 11

i.) 42

10.) Does 784637716923335095479473677900958302012794430558004314112 divide 10²⁰⁰? Be sure to give a good reason for your answer. [Note that 784637716923335095479473677900958302012794430558004314112 = 2¹⁸⁹.]

11.) For n, a natural number, prove that is also a natural number.

Exam #4

1.) One of the items on Olive Garden's menu is the Sampler Italiano. From calamari, stuffed mushrooms, fried zucchini, chicken fingers, fried mozzarella or toasted meat ravioli you can choose any three for $8.25 or any two for $7.25. How many different Sampler Italianos are possible?

2.) Olive Garden's on-line menu lists nine appetizers, three salads, two soups, 163 possible pizza appetizers, 34 types of entrées, 18 non-alcoholic beverages and six types of desserts. If you order one of each kind of item, how many different meals could you order?

3.) What is the coefficient of the term containing x³ in the expansion of (2x + 3y)²³?

4.) a.) Five children order one small soft drink each from a stand that offers seven

kinds of soft drinks. How many outcomes are possible?

b.) To save time, the chaperone decides to order some selection of five small

soft drinks from the seven kinds available, without consulting the children or deciding who will get which drink. How many ways may the chaperone place the order?

5.) If you are dealt five cards from a standard deck of cards, what is the probability you will end up with three cards from one suit and two from another?

6.) An integer, n, between 100 and 999 inclusive is selected at random. If n = 100d₂ + 10d₁ + d₀ has digits d₂, d₁, and d₀, find the probability that:

a.) the digits of n are all distinct.

b.) The digits of n are all equal.

c.) n has exactly two distinct digits.

d.) d₀ = d₂.

e.) d₀ ¹ d₁.

7.) Let S = {1, 2, 3}.

a.) How many relations are there on S? (notice I didn't say write them out, just

say how many there are)

b.) Find an example of a relation on S that is reflexive and transitive.

c.) A relation, R, on S is irreflexive if and only if (a, a) Ï R for all a Î S. Give an example of a relation on S that is neither reflexive nor irreflexive.

8.) Consider the relation on R² defined as follows.

(x, y) » (z, w) if and only if x = z

a.) Determine whether or not this is an equivalence relation.

b.) If it is an equivalence relation, give a geometric description of the partition of R² formed by the equivalence classes.

9.) Consider Ã(S) (the power set of S) if S = {1, 2, 3}. Define a relation on Ã(S) as follows.

A # B if and only if A Ç B ¹ Æ

Determine whether or not # defines an equivalence relation Ã(S).

10.) Consider the relation on defined by x y if and only if x £ y².

a.) Determine whether defines a partial order on .

b.) If defines a partial order on , determine whether it is a total order.

11.) Consider the relation on defined by x y if and only if x £ y + 2. Determine whether this defines a partial order on .

Final Exam

1.) What is the coefficient of the term containing x³ in the expansion of (2x + 3y)²³?

2.) Olive Garden's on-line menu lists nine appetizers, three salads, two soups, 163 possible pizza appetizers, 34 types of entrées, 18 non-alcoholic beverages and six types of desserts. If you order one of each kind of item, how many different meals could you order?

3.) Consider Ã(S) (the power set of S) if S = {1, 2, 3}. Define a relation on Ã(S) as follows.

A # B if and only if A Ç B ¹ Æ

Determine whether or not # defines an equivalence relation Ã(S).

4.) Let S = {1, 2, 3, 4}.

a.) How many relations are there on S? (notice I didn't say write them out, just

say how many there are)

b.) Find an example of a relation on S (with cardinality at least 4) that is symmetric and transitive.

c.) A relation, R, on S is irreflexive if and only if (a, a) Ï R for all a Î S. Give an example of a relation on S that is neither transitive nor irreflexive.

5.) Prove that the square of the sum of the squares of any two odd numbers is even.

6.) Let our "universe" be U={a, b, c, d, e, f, g, h, i, j, k}. Let A={a, b, c, d}, B={e, f, i}, and C={g, h, j, k}.

a.) Evaluate (AC) B.

b.) Evaluate (AB)^CC.

c.) Evaluate (B C) \ A.

d.) Do A, B and C form a partition of U? Why or why not?

7.) Prove that (A È B) Ç C = (A Ç C) È (B Ç C).

8.) Construct a truth table for:

~(P Ú Q) Þ ~Q

9.) Prove that the sum of a rational number and an irrational number is irrational.

10.) Prove that every natural number greater than 2 can be written as the sum of three natural numbers a, b and c, such that at least two of the numbers are the same and the third differs from the others by no more than 1.

11.) Prove the following.

For every natural number, n, .

12.) Coins are randomly removed from a piggy bank containing 12 pennies, eight nickels, ten dimes, and three quarters. How many coins must be removed to guarantee:

a.) five pennies?

b.) four coins of the same kind?

c.) two quarters?

d.) a pair of pennies and a pair of another kind?

e.)