CMSC203 Discrete Structures, Sections 0201, Spring 2008

Homework Assignments

Homework 1, Due Thursday 02/07

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. Statements made by knights are true. Statements made by knaves are false. You meet two people, Mel and Zeke, and you know that each is either a knight or a knave. This is what they said:

   Mel: "I am a knight and Zeke is a knave."
   Zeke: "Mel is a knight."

   Is Mel a knight or a knave? Is Zeke a knight or a knave? Show your reasoning.

3. Three Jealous Girlfriends. [Adapted from Introductory Graph Theory by Gary Chartrand.]

   As in the Three Cannibals and Three Missionaries Problem, three women and their three boyfriends must cross a river using a boat which holds only two people. Here, the constraint is that no boyfriend is left with one or both of the other women without his own girlfriend also present.

   Is a solution possible? Formulate this problem as an undirected graph and either present a solution or argue that none exist.

Homework 2, Due Thursday 02/14

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 circuit in the graph that visits every vertex exactly once. Does the graph below have a Hamiltonian circuit? Justify your answer.

   

3. Betelgeuse. [Adapted from Problem Solving Through Recreational Mathematics by Averbach & Chein, 1980.]
   A space traveler returns from the Betelgeuse star system and gives a report on the aliens encountered there:

   It is not true that if the aliens are green then they either have three heads or else they cannot fly, unless it is also true that they are green if and only if they can fly and that they do not have three heads.

   Assume that the aliens are all alike. Let f be the proposition that "the aliens can fly", let g be the proposition that "the aliens are green" and let h be the proposition that "the aliens have three heads".

   Use logic notation and the variables f, g and h to rephrase the space traveler's report.

   Can the aliens fly? Are they green? Do they have 3 heads? Show your work.

Homework 3, Due Thursday 02/21

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

   If n⁵ + 7 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.
   

Homework 4, Due Thursday 02/28

1. Arithmetic with mod. Use Theorem 4 on page 59 (NT-7) to compute 47²⁹ % 53 without using any numbers bigger than 53² = 2809. Show your work.

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

   x ⋅ y ≡ 1 (mod 17).

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

3. RSA Key Generation. Suppose that you picked p = 503 and q = 907 for your RSA keys. Then, n = 456221 and φ(n) = (p - 1)(q - 1) = 454812. 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.

Homework 5, Due Thursday 03/06

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

   x ≡ 4   (mod 5)
   x ≡ 2   (mod 9)
   x ≡ 7   (mod 14)

   Note that 5 ⋅ 9 ⋅ 14 = 630 and recall that the notation

   a ≡ b   (mod n)
   

   means that a % n = b % n, where % is the remainder operator.

2. 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.

3. Unique Inverses. Suppose that a and n are relatively prime positive integers. That is, gcd(a, n) = 1. Using the Extended Euclid Algorithm, we can find an integer x such that 0 ≤ x < n and a⋅x ≡ 1  (mod n). Prove that this x is unique.

Homework 6, Due Thursday 03/13

1. Provide a well-written proof using the "element of" method that for all sets A, B and C:

   A ∩ (B ⊕ C) = (A ∩ B) ⊕ (A ∩ C)

   A well-written proof must include complete English sentences describing major steps of the proof.

2. Let f : B → C and g : A → B be functions. The composition of f and g, written f _° g, is a function from A to C defined by:

   (f _° g) (x) = f (g(x)).

   Show that if f is one-to-one and g is one-to-one then f _° g is one-to-one.

3. Let A and B be countably infinite sets. Prove that A ∪ B must also be countably infinite.

Homework 7, Due Thursday 03/27

1. Prove by induction that

   1 1⋅5

   +

   1 5⋅9

   +

   1 9⋅13

   +  ⋅⋅⋅  +

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

   =

   n 4 n + 1

   .

Homework 8, Due Tuesday 04/08

1. Prove by induction that

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

   =

   n + 1    2 n

   .

2. In graph theory, a k-regular graph is an undirected graph where every vertex has degree k. Prove by induction on k that for every k ≥ 0 there exists a k-regular graph.

3. Let x ≥ 0 be a real number. Prove by induction on n, that for all n ≥ 2,

   1 + nx ≤ (1 + x)ⁿ.

   Note: the inequality actually holds for x ≥ −1.

Homework 9, Due Tuesday 04/15

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 10, Due Tuesday 04/22

1. 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 ⊆ A × B is antisymmetric if for all (a, b) ∈ A × B, (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. 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. A bin has 34 balls that are either red, green or orange.

   1. Argue that the bin must contain 12 red balls, 12 green balls or 12 orange balls.

   2. Argue that the bin must contain 9 red balls, 6 green balls or 21 orange balls.

Homework 11, Due Tuesday 04/29

1. Consider the integers between 1000 and 9999 (inclusive).
   1. How many of these integers do not have any repeated digits?
   2. How many of these integers repeat at least one digit?

2. 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?

3. On the Isle of Roke, license plates for cars are allowed to have up to 7 characters chosen from the set of 26 letters A-Z, 9 digits 1-9 and the space. (The digit 0 is not allowed due to similarity with the letter O.) Furthermore, each license plate must start with a letter and must not end with a space.
   1. How many different license plates are possible on the Isle of Roke?
   2. A list of 61 four-character sequences have been banned for being potentially offensive. These sequences must not appear as a substring on any license plate. Now how many different license plates are possible?

      Turns out this problem cannot be done without knowing the characters in the banned words. For example, if OOOO is banned, then AOOOOBC and ABOOOOC are both banned. These are easy to account for, but we must also make sure that AOOOOOB (with 5 O's) is counted only once. To do this we need to know which of the 61 words are "self overlapping".

Homework 12, Due Tuesday 05/06

1. You have 15 tickets that can be used for 6 different rides at the county fair. You can take each ride as few or as many times as you like, but you must use all 15 tickets. How many different ways can you allocate the tickets? (Assume that the order in which you take the rides does not matter.)

2. In a board game, you have 16 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. You have 9 balls that you throw at 4 bins labeled A, B, C and D. 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 9 balls, one at a time, at the bins. What is the probability that exactly 2 balls land in bin A? Justify your answer.
   2. You throw the 9 balls, one at a time, at the bins. What is the probability that 3 or fewer balls land in bin C? Justify your answer.

Homework 13, Due Tuesday 05/13

1. A fair 20-sided die with values 1 through 20 is rolled 3 times.
   1. What is the probability that the die shows a number that is 13 or higher exactly twice?
   2. What is the conditional probability the die shows 13 or higher exactly twice, given that the first roll is 17?

2. A jar of animal crackers contains 17 crackers depicting reptiles and 27 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. You select 5 cards from the standard deck of playing cards. Of the 5 cards, 2 are Aces and 3 are not. You shuffle the cards well (so each permutation of the 5 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?