UMBC CMSC203, Discrete Structures, Spring 2009

Homework Assignments

Notation:

• Rosen 6/e, Rosen 5/e and Rosen 4/e indicate respectively the sixth, fifth and fourth editions of Discrete Mathematics and Its Applications, Kenneth Rosen, McGraw-Hill.

• Epp 3/e and Epp 2/e indicate respectively the third and second editions of Discrete Mathematics with Applications, Susanna S. Epp, Thomson Publishing.

Homework 1, Due Tuesday, 02/03

1. [Adapted from Rosen 6/e]
   State whether each of the following relationships between sets is true or false. Justify your answer briefly. (Here, ∅ is the empty set.)

   1. ∅ ∈ ∅

   2. {∅} ∈ {∅}

   3. ∅ ∈ {∅}

   4. {∅} ⊆ {∅}

   5. ∅ ⊆ ∅

2. [Adapted from Epp 3/e]
   Let R be the set of all real numbers and let A indicate the complement of the set A. We define the sets A, B and C as follows:

   A = { x ∈ R | -3 ≤ x ≤ 0 }

   B = { x ∈ R | -1 < x < 2 }

   C = { x ∈ R | 6 < x ≤ 8 }

   Describe the following sets:

   1. A ∪ B

   2. A ∩ C

   3. A ∪ B

   4. A ∩ B

   5. A ∪ B

3. For each of the following functions, state whether the function is one-to-one, whether the function is onto and whether the function is a bijection. Pay close attention to the domain and codomain of each function. Briefly justify your answer.

   1. f : N → N,   f (n) = n² + 5.

   2. f : Z → Z,   f (n) = n² + 5.

   3. f : N → N,   f (n) = 2 n + 7.

   4. f : R → R,   f (x) = 2 x + 7.

   5. f : R → R,   f (x) = 2 x³ + 1.

   Note: N, Z and R denote the set of natural numbers, integers and real numbers respectively.

4. Questions 4, 5 and 6 are on this handout: hw1-456.pdf.

5. Questions 4, 5 and 6 are on this handout: hw1-456.pdf.

6. Questions 4, 5 and 6 are on this handout: hw1-456.pdf.

Homework 2, Due Tuesday, 02/10

1. Real Maps. Theoretically, the Four Color Theorem tells us that every map can be colored with 4 colors so that every region is colored differently from a neighboring region. However, real maps have "real considerations" and might require 5 colors. Name one such consideration. Give an example of a "real" map that requires 5 colors.

2. Hamiltonian Circuits. [Adapted from Problem Solving Through Recreational Mathematics by Averbach & Chein, 1980.]
   A graph has a Hamiltonian circuit if there is a path in the graph that visits every vertex exactly once and returns to the first vertex in the path. Does the graph below have a Hamiltonian circuit? Justify your answer.

   

3. Regular Graphs. In a d-regular graph, every vertex in the graph has degree d. Recall that the degree of a vertex is the number of edges incident on the vertex. (I.e., count the number of edges coming out of a vertex and that is its degree.)
   1. Draw a 3-regular graph with 6 vertices.
   2. Draw a 3-regular graph with 8 vertices.
   3. Draw a 3-regular graph with 10 vertices.
   4. Are there any 3-regular graphs with 9 vertices? why or why not?

Homework 3, Due Tuesday, 02/17

1. Tautologies. Use a truth table to show that the following proposition is a tautology. You must show the intermediate steps in the truth table.

   (¬ (p ∨ q)) ⊕ ( (¬p) → q)

2. Knights and Knaves. [From "A Whole Slew of Computer-Generated Knights and Knaves Puzzles" by Zac Ernst, 1999.]
   Statements made by knights are true. Statements made by knaves are false. You meet three people, Joe, Zippy and Alice. You know that each is either a knight or a knave. This is what they said:

   Joe: "Alice is a knave and Zippy is a knight."
   Zippy: "I am a knight or Joe is a knave."
   Alice: "Zippy is a knave."

   Which of Joe, Zippy and Alice are knights? which are knaves? Show your reasoning.

3. Robins on Thursday. [Adapted from Problem Solving Through Recreational Mathematics by Averbach & Chein, 1980.]
   Suppose that we know the following statement is true:

   If today is Thursday and the sun is shining, then either the robins are singing or it is not summer.

   Let p = "Today is Thursday", q = "the sun is shining", r = "the robins are singing" and s = "it is summer".

   1. Rewrite the statement above using logic operators and the variables p, q, r and s.

   2. If you find out that "It is summer and the robins are not singing", what can you conclude? Show your reasoning.

   3. If you find out that "Today is Thursday and the robins are singing", what can you conclude? Show your reasoning.

   4. If you find out that "Today is Thursday and the robins are not singing", what can you conclude? Show your reasoning.

Homework 4, Due Tuesday, 02/24

1. Indirect Proof. Give an indirect proof for the following claim:

   If n³ + 13 is an odd integer, then n is an even integer.

2. Proof by Contradiction. Prove by contradiction that the Grötzsch Graph shown below is not 3-colorable. Hint: Note that the graph has a 5-way symmetry. Another Hint: Look at the cycle a-d-k-j-b-a. How many colors does it take to color this cycle? How many times does each color appear?
   

3. Proof by Cases. Prove that the 5-clique (a.k.a. K₅) shown below is not planar. Make your argument by cases. Pictures are helpful.
   

4. Equivalence Proof. [Adapted from Rosen 5/e]
   Prove the equality of the two sets below by showing that every element of the set on the left hand side of the equality is also an element of the set on the right hand side, and vice versa. (I.e., do not prove this using algebraic identities.)

   (B − A) ∪ (C − A)  =  (B ∪ C) − A

Homework 5, Due Tuesday, 03/03

1. Arithmetic with mod. Use the repeated squaring technique to compute 26³⁷ % 77. Show all of your work. Your work should not have any numbers bigger than 77² = 5929.

2. Inverses mod 23. For each integer x, 1 ≤ x < 23, find an integer y, 1 ≤ y < 23, such that

   x ⋅ y ≡ 1 (mod 23).

   In other words, x ⋅ y % 23 = 1. Then, x and y are called inverses modulo 23.

3. A Shortcut. Fermat's Little Theorem states that if p is prime, then for any integer a not divisible by p,

   a ^{p − 1} ≡ 1    (mod p).

   Take advantage of Fermat's Little Theorem to compute the value 9⁵²⁸² % 17 by noticing that 9¹⁶ ≡ 1  (mod 17). Show your work.

Homework 6, Due Tuesday, 03/10

1. Euclid's Algorithm. Use Euclid's algorithm to compute the greatest common divisor of 1413828 and 551655. Show all your work. Note: Do not use a computer program to do this computation.

2. RSA Key Generation. Suppose that you picked p = 1307 and q = 1129 for your RSA keys. Then, n = 1475603 and φ(n) = (p - 1)(q - 1) = 1473168. You still need to find e and d such that e ⋅ d % φ(n) = 1. Use the Extended Euclid Algorithm to help you find an e and a d. Make sure you report e and d as positive values less than φ(n). Show your work using the Extended Euclid Algorithm. (See notes on the Extended Euclid Algorithm.) Note: Do not use a computer program to do this computation.

   Additional Note: You need to pick an e such that gcd(e,φ(n)) = 1. The usual recommendation is to pick a prime number. However, you must still check that gcd(e,φ(n)) = 1 when e is prime, because it is possible that e divides φ(n). For example, in this problem picking e = 3 doesn't work because φ(n) = 1473168 is divisible by 3 and so gcd(3,1473168) = 3. There are no inverses of 3 modulo 1473168.

   Another Additional Note: You are not allowed to pick e = 1.

3. A System of Congruences. Use the Chinese Remainder Theorem to find an integer x such that 0 ≤ x < 1456 and the following congruences hold:

   x ≡ 3   (mod 7)
   x ≡ 6   (mod 13)
   x ≡ 12   (mod 16)

   Note that 7 ⋅ 13 ⋅ 16 = 1456 and recall that the notation

   a ≡ b   (mod n)
   

   means that a % n = b % n, where % is the remainder operator. Show your work. (See notes on the Chinese Remainder Theorem.)

Homework 7, Due Tuesday, 03/24

In the following questions you are asked to use proof by induction. Your proof must not simply be a sequence of equations, even if the statement you are proving is arithmetic in nature. Clearly indicate using complete English sentences: 1) what you are allowed to assume from the induction hypothesis, 2) what you need to show to establish the induction step, and 3) which steps of the proof uses the induction hypothesis.

1. Prove by induction that for all integers n ≥ 1

   1³ + 2³ + 3³ + ⋅⋅⋅ n³ = [ n (n+1) / 2]²

2. Prove by induction that for all integers n ≥ 1

   1 1⋅5

   +

   1 5⋅9

   +

   1 9⋅13

   +  ⋅⋅⋅  +

   1 (4 n - 3) (4 n + 1)

   =

   n 4 n + 1

   .

3. Prove by induction that for all integers n ≥ 2

   (1 − 2 −2) ⋅ (1 − 3 −2) ⋅ (1 − 4 −2) ⋅⋅⋅ (1 − n −2)

   =

   n + 1    2 n

   .

Homework 8, Due Tuesday, 04/07

In the following questions you are asked to use proof by induction. Your proof must not simply be a sequence of equations, even if the statement you are proving is arithmetic in nature. Clearly indicate using complete English sentences: 1) what you are allowed to assume from the induction hypothesis, 2) what you need to show to establish the induction step, and 3) which steps of the proof uses the induction hypothesis.

1. Fibonnaci Numbers. [Adapted from Rosen 5/e]
   The Fibonacci numbers f₀,  f₁,  f₂, ... are defined recursively by f₀ = 0,  f₁ = 1,  f₂ = 1 and for all n ≥ 3,

   f_n = f_{n − 1} + f_{n − 2} .

   Use structural induction to show that

   ( f₁ )² + ( f₂ )² + ⋅⋅⋅ + ( f_n )² = f_n f_n+1

2. String Reversal. [Adapted from Rosen 5/e]
   In this problem, we consider only strings over {0, 1} of length greater than or equal to 0. For example, the string 01001 is a string of length 5. We use λ to denote the empty string. For a string w we can define the reversal of the string, written w^R, as follows:
   • λ^R = λ
   • for a string x, ( 0 x )^R = x^R 0.
   • for a string x, ( 1 x )^R = x^R 1.
   For example, we can unwind the recursive definition of 01001^R by:

   01001^R = 1001^R0 = 001^R10 = 01^R010 = 1^R0010 = λ^R10010 = λ10010 = 10010.

   Use structural induction to prove that for all strings w and x, (w x)^R = x^R w^R.

   Additional Note: For this problem, you may assume without proof that string concatenation is associative. So, given 3 strings x, y and z,  ( x y ) z = x ( y z ).

3. Partition. Consider the following function written in the C programming language: int partition(int A[], int n) { int i, j ; /* array indices */ int x ; /* pivot item */ int temp ; x = A[0] ; i = -1 ; j = n ; while (1) { do { j-- ; } while (A[j] > x) ; do { i++ ; } while (A[i] < x) ; if (i < j) { temp = A[i] ; /* swap A[i] and A[j] */ A[i] = A[j] ; A[j] = temp ; } else { return j ; } } }

   1. Suppose that partition(A, n) is called with an array A holding the 12 items

      16, 22, 12, 8, 15, 11, 10, 7, 14, 5, 9, 24

      and with n equal 12. How is A rearranged when partition returns? What is the meaning of the value returned by partition? (Hint: the partition() function might be used in Quicksort.)

   2. Develop a loop invariant for the outer while loop that can be used to prove that partition() does what you say it does. Argue that the loop invariant holds initially and for each iteration of the outer while loop.

   3. What does the loop invariant say when the outer while loop terminates (using the return statement in the else part of the if statement)?

Homework 9, Due Tuesday, 04/14

1. Burritos. At Mr. Cheap O'Tillay's Restaurant, customers can order a burrito with a choice of 2 types of tortillas (flour, whole wheat), 3 types of beans (refried, black, red), 4 types of cheese (cheddar, nacho, Monterrey Jack, Colby) and 3 types of meat (beef, chicken, pork). How many different burritos can the customers order if each burrito must include 1 tortilla, 2 or fewer choices of beans, 2 or fewer choices of cheese, and 1 or fewer choice of meat?

2. Colored Balls. A bin has 29 balls that are either red, green or orange.
   1. Argue that the bin must contain 10 red balls, 10 green balls or 10 orange balls.
   2. Argue that the bin must contain 8 red balls, 7 green balls or 15 orange balls.

3. Dog Sled Team. We wish to form a sled dog team with 7 dogs chosen from a group of 14 Siberian Huskies and 9 Alaskan Malamutes. How many different teams can be formed if we must have more Siberian Huskies than Alaskan Malamutes?
   Note: in this question the dogs are considered individuals and are distinguishable.

Homework 10, Due Tuesday, 04/21

1. Car Park. There are 4 red cars and 7 blue cars parked in 11 consecutive spots of a parking lot. Each car is distinguishable by its license plate.
   1. How many ways can the cars be parked in these 11 spots so the 4 red cars are adjacent to each other?
   2. How many ways can the cars be parked in these 11 spots so none of the 4 red cars is adjacent to another red car?

2. Marble Placement. In a board game, you have 19 indistinguishable marbles that you can place in 5 distinguishable locations. You must place at least 2 marbles at each location, but are otherwise allowed to place as many or as few marbles at each location. How many different ways can you make these placements?

3. Balls & Bins. You have 13 balls that you throw at 5 bins labeled A, B, C, D and E. Our assumption is that when a ball is thrown at the bins, there is an equal probability that the ball lands in any particular bin. Also, the ball will always land in one of the bins. Each bin is large enough to hold any number of balls.
   1. You throw the 13 balls, one at a time, at the bins. What is the probability that exactly 3 balls land in bin A? Justify your answer.
   2. You throw the 13 balls, one at a time, at the bins. What is the probability that 4 or fewer balls land in bin B? Justify your answer.

Homework 11, Due Tuesday, 04/28

1. Two Urns. [Adapted from Epp, 3/e.]
   You have two urns. One urn holds 5 red balls and 13 yellow balls. The second urn holds 9 red balls and 11 yellow balls. You pick one ball using this procedure: randomly pick one of the two urns with equal probability, then pick a ball from the chosen urn so that each ball is chosen with equal probability.
   1. What is the probability that the chosen ball is red?
   2. If the chosen ball is red, what is the probability that the chosen ball came from the first urn?

2. Animal Crackers. A jar of animal crackers contains 13 crackers depicting reptiles and 29 crackers depicting mammals. Two crackers are chosen from the jar, one after the other without replacement.
   1. What is the probability that both crackers are mammals?
   2. What is the conditional probability that the second cracker is a mammal given that the first one is a reptile?
   3. What is the probability that the second cracker is a mammal?
   4. What is the probability that at least one of the two crackers is a mammal?

3. Three-bit Strings. [Adapted from Rosen 5/e.]
   We generate a 3-bit string w randomly so that each bit of w has an equal chance of being 0 or 1. Let E be the event that w has an odd number of 1's and let F be the event that the last bit of w is a 1. Are E and F independent? Show your calculations and explain your answer.

Homework 12, Due Tuesday, 05/05

1. 4- and 8-sided Die. You have a fair 4-sided die and a fair 8-sided die. (Here a die is fair if when the die is rolled, there is an equal probability for any particular side to be on top.) The sides of the 4-sided die are labeled with 2, 7, 7 and 9. The sides of the 8-sided die are labeled with 1, 1, 2, 3, 3, 4, 5 and 5.
   1. What is the expected value of the number on top when you roll the 4-sided die?
   2. What is the expected value of the number on top when you roll the 8-sided die?
   3. What is the expected value of the sum of the numbers on top when you roll both dice?

2. Rolling for 10+. You have two normal 6-sided dice (with sides labeled 1, 2, 3, 4, 5 and 6). Assume that the dice are fair. Suppose that you keep rolling the two dice until the sum of the numbers on the dice is greater than or equal to 10. What is the expected number times that you will roll the dice?

3. Two Aces. You select 6 cards from a standard deck of playing cards. Of the 6 cards, 2 are Aces and 4 are not. You shuffle the cards well (so each permutation of the 6 cards is equally likely). Then, you deal out the selected cards (without replacement) face up until two Aces are shown. What is the expected number of cards dealt?

   Hint: To calculate the probability that exactly 4 cards are dealt until two Aces are shown, consider the fact that the first Ace could be the first card, the second card or the third card. The fourth card is, of course, the second Ace. Then no more cards are dealt.

Homework 13, Due Tuesday, 05/12

1. Relation Properties. For each of the following relations, state whether relation is reflexive, symmetric, antisymmetric and transitive. Briefly justify your response in each case.

   Note: a relation R on A is antisymmetric if for all (a, b) ∈ A × A, (a, b) ∈ R and (b, a) ∈ R implies that a = b.

   1. R₁ = { (a, b) | a and b are integers and a = 3b }

   2. R₂ = { (a, b) | a and b are integers and |a − b| is even }

   3. R₃ = { (a, b) | a and b are integers and a b = 0 }

2. Two Equivalence Relations. Suppose that R₁ and R₂ are both equivalence relations on A.

   1. Must R₁ ∩ R₂ be an equivalence relation? Give a proof or a counterexample.

   2. Must R₁ ∪ R₂ be an equivalence relation? Give a proof or a counterexample.

3. Partial Orders. Consider the set A = { 2, 3, 6, 8, 24, 30, 32 } and the relation R on A defined by:

   R = { (a, b) | a divides b }.

   Since R is reflexive, antisymmetric and transitive, it is a partial order.

   1. Draw a Hasse diagram for R.

   2. List two incomparable elements in R

   3. What are the minimal and maximal elements of this partial order?

   4. Does R have a greatest element? Why or why not?