Math Discrete

Math Discrete

  • Current Problem Sets
    General instructions: Write up the solutions for the problems in each lesson. Scan the work into
    a pdf file. No other file format is accepted. If there are multiple pages for an assignment, merge
    the pages into a single pdf. Upload your work to Blackboard. Give the file an identifying name
    such as MyNameMath208L01.pdf (the L01 is for Lesson 1). Be sure to save the file with such a
    name on your computer, not just in Blackboard, since the name of the file on your computer will
    be the name it will have when it is downloaded from Blackboard.
    Make sure the work is dark enough to be read. Use a dark pen or pencil, or maybe increase
    the contrast on the scanner. Show the work that leads to the solution; correct answers without
    necessary work will earn little if any credit.
    Remember that you cannot expect more than three assignments to be graded in any seven day
    period. Graded assignments will be available through Blackboard.
    Problems 1 through 5 are worth are worth 5 points each. Problem 6 is a bonus problem worth
    3 points. The total score for a problem set cannot be greater than 25.
    Sample exercises with solutions are found in an appendix to the text. When solving the problems
    in this list, you may use any facts given in the text exercises but not in the text problems. If
    you want to use a fact in a problem, give a solution to the problem as part of your work.
    Problems to be submitted.
    1. Lesson 1
    (1) Determine which of the following sentences are propositions. Give a brief reason for your
    answer.
    (a) Seven is two more than five.
    (b) Stop whining!
    (c) There is a black hole at the center of every galaxy.
    (d) This sentence has five words.
    (2) Construct truth tables for each of the following.
    (a) ¬q −→ p.
    (b) (p ∨ q) −→ r. (You will need eight rows for this one.)
    (3) Let s be the proposition It is snowing, f be the proposition It is below freezing, and r be It
    is raining. Convert the following English sentences into statements using the symbols s, f,
    r and logical connectives.
    (a) It is snowing or it is not below freezing.
    (b) If it is snowing, then it is not raining and it is below freezing.
    (4) Use a truth table to verify the equivalence: p −→ ¬q ≡ ¬p ∨ ¬q.
    Explain why the truth table shows that the propositions are equivalent.
    (5) Use a truth table to show that the statements p −→ (q −→ r) and (p −→ q) −→ r
    are not logically equivalent.
    Explain why the truth table shows that the propositions are not equivalent.
    1
    2
    (6) (bonus) Give a proof of the following equivalence following the pattern of proof shown in
    the examples in section 2.6 of the text: ¬p −→ (p −→ q) ≡ T.
    2. Lesson 2
    (1) Let P(x) : x
    2 ≤ 4. The domain for x is all positive integers (1, 2, 3, . . .). Determine the
    truth values of the following propositions.
    (a) P(5)
    (b) ¬∀x P(x)
    (2) Let P(x, y) be x has read y, where the domain of discourse for x is all students in this
    class, and the domain of discourse for y is all books written by Mark Twain. Express the
    following propositions in English.
    (a) ∀x P(x, Huckleberry Finn).
    (b) ∃x ∀y P(x, y).
    (c) ∀y ∃x P(x, y).
    (3) Let F(x, y) be the statement x trusts y, where the domain of discourse for both x and y is
    all people.
    (a) Use quantifiers to express each of the following propositions in symbols.
    (i) Nobody trusts Ralph.
    (ii) Everybody trusts Fred.
    (iii) Somebody trusts everybody.
    (b) Now write the negation of those propositions in symbols. The cheap way would be to
    simply write ¬ in front of each of the answers to part (a). Don’t do that. Use the
    rules discussed in the text so your answer does not have ¬ occurring to the left of any
    quantifiers.
    (c) Express each of those negations in an English sentence.
    (4) Show that p −→ q and ¬p, ∴ ¬q is not a valid rule of inference. It is called the fallacy
    of denying the hypothesis. To expand a bit on the reading for this lesson, here is how
    to show a proposed rule of inference is valid using a truth table: Construct a truth table
    with columns for the hypotheses and a column for the conclusion. Check that in every
    row where the hypotheses all have truth value T, the conclusion also has truth value T.
    In plain English, check that if we agree the hypotheses are all true, then the conclusion
    is true as well. Notice that in rows where the hypotheses do not all have truth value T,
    the truth value of the conclusion does not matter. Flipping that validity test around, an
    argument is not valid if there is a row in the truth table where the hypotheses are all T,
    but the conclusion is F. Such a row shows that it is possible to agree that the hypotheses
    are all true, and yet still have the conclusion false. That means the argument is not valid.
    (5) Express the following argument symbolically, and then prove, using the style of proof shown
    in table 4.2 of the text, that the argument is valid. If Ralph doesn’t have a sore shoulder or
    3
    he doesn’t feel sick, then he will go bowling and he will go to the movie. If he goes to the
    movie, he will buy popcorn. He didn’t buy popcorn. So Ralph has a sore shoulder.
    (Use s for Ralph has a sore shoulder. f for Ralph feels sick. b for Ralph goes bowling.
    m for Ralph goes to the movie. p for Ralph buys popcorn.
    Warning: You will probably want to use the rule of Simplification at some point in your
    proof. You need to be careful with that rule! In plain English, the rule says that if you
    know p and q is true, then you can conclude p is true. But watch out: if p ∧ q is part of a
    larger proposition, you can not replace p ∧ q with p. For example, consider the proposition
    If I bet $1000 on My Pony and My Pony wins the race, then I will be rich. Obviously it is
    not valid to say, by Simplification, If I bet $1000 on My Pony, then I will be rich. So, be
    careful using Simplification.
    (6) (bonus) Prove
    ∃x(A(x) ∧ ¬B(x))
    ∀x(A(x) −→ C(x))
    ∴ ∃x(C(x) ∧ ¬B(x))
    Hint: This is very similar to example 4.2 in the text.
    3. Lesson 3
    (1) Write the following sets using the roster form:
    (a) {x ∈ Z|10 ≤ x
    2 < 100} (Careful, that is Z, not N!)
    (b) {x ∈ N|x ≤ 4} (Remember that, in this text anyhow, 0 ∈ N.)
    (2) Use set-builder notation to give a description of each set.
    (a) {4, 8, 12}.
    (b) {−2, 0, 2, 4, 6}.
    (3) Let A = {1, 2, 3, 5, 6, 7} and B = {2, 4, 6, 8, 9}. Find
    (a) A ∩ B
    (b) A ∪ B
    (c) A − B
    (d) B − A
    (4) Draw Venn diagrams for A ∩ (B ∪ C) and (A ∩ B) ∪ (A ∩ C) to show that A ∩ (B ∪ C) =
    (A ∩ B) ∪ (A ∩ C).
    (5) Let A = {1, 2, 3, 4} × {1, 2, 3}. List the elements of the set B = {(s, t) ∈ A | s ≥ t }.
    (6) (bonus) Is the proposition Every element of the empty set has three toes true or false? Explain
    your answer! Hint: In symbols, the proposition is written: ∀x(x ∈ ∅ −→ x has three toes).
    Think about the truth value of that implication.
    4
    4. Lesson 4
    For these exercises, you will need to know the definitions of even and odd integers. An integer
    n is even if n = 2k for some integer k. An integer n is odd if n = 2k + 1 for some integer
    k. There are no integers that are both even and odd! Examples: 6 is even since 6 = (2)(3),
    −8 is even since −8 = (2)(−4), 0 is even since 0 = (2)(0), 3 is odd since 3 = 2(1) + 1, and
    −9 is odd since −9 = (2)(−5) + 1.
    (1) Give a direct proof that the sum of an odd integer and an even integer is odd.
    Hint: Start by letting m be an odd integer and letting n be an even integer. That means
    m = 2k + 1 for some integer k and n = 2j for some integer j. Notice that if we let the odd
    and even integers be 2k + 1 and 2k, the proof will only account for the cases in which n is
    one less than m. That is why we need to have m = 2k + 1 and n = 2j for integers k, j, so
    that the sum of any odd and any even will be considered. You are interested in m + n, so
    add them up and see what you get. Why is the thing you get an odd integer (think about
    the definition of odd)?
    (2) Give an indirect proof that if n
    3
    is even, then n is even. Hint: Study the solution of a
    similar statement in the sample solutions for this lesson.
    (3) Give a proof by contradiction that if 5n − 4 is odd, then n is odd.
    Hint: This is the problem in this set that gives the most grief. Study the section in the
    notes where the mechanics of proving a statement of the form If P, then Q by contradiction
    is discussed. Be sure you understand why the first line of the proof should be something
    like Suppose 5n − 4 is odd and n is even.
    (4) Give an example of a predicate P(n) about positive integers n, such that P(n) is true for
    every positive integer from 1 to one billion, but which is never-the-less not true for all positive
    integers. (Hints: (1) There is a really simple choice possible for the predicate P(n),
    (2) Make sure you write down a predicate with variable n, and not a proposition!) The
    purpose of this problem is to convince you that when checking a for all type proposition, it
    is not good enough to just check the truth for a few sample cases, or, for that matter, even
    a few billion sample cases. A general proof that covers all possible cases is necessary.
    (5) Give a counterexample to the proposition Every positive integer that ends with the digits
    13 is a prime.
    (6) (bonus) The maximum of two numbers, a and b, is a provided a ≥ b. Notation: max(a, b) =
    a. The minimum of a and b is a provided a ≤ b. Notation: min(a, b) = a. Examples:
    max(2, 3) = 3, max(5, 0) = 5, min(2, 3) = 2, min(5, 0) = 0, max(4, 4) = min(4, 4) = 4.
    Give a proof by cases (two cases is the natural choice for this problem) that for any numbers
    s, t,
    min(s, t) + max(s, t) = s + t.
    5
    5. Lesson 5
    (1) Let A = {a, b, c, d} and R = {(a, a),(a, c),(b, b),(b, d),(c, a),(c, c)} be a relation on A. Draw
    a digraph which represents R. You might want to review the definition of digraph!
    (2) Find the composition, R ◦ S, where S = { (1, a),(4, a),(5, b),(2, c),(3, c),(3, d) } with R =
    {(a, x),(a, y),(b, x),(c, z),(d, z)} as a set of ordered pairs.
    (3) Let R1 = {(1, 2),(1, 3),(1, 5),(2, 1),(5, 6),(6, 6)} and
    R2 = {(1, 2),(1, 6),(3, 6),(4, 2),(5, 6),(6, 2),(6, 3)}. Find R1 ∪ R2 and R1 ∩ R2.
    (4) Define a relation on {1, 2, 3, 4, 5} by R = {(1, 2),(2, 1),(2, 3),(3, 2),(3, 4),(4, 3),
    (4, 5),(5, 4),(5, 1),(1, 5)}. For each of the five properties of a relation defined in this chapter
    (reflexive, irreflexive, symmetric, antisymmetric, and transitive) either show R satisfies the
    property, or explain why it does not.
    (5) Define the relation M(A, B) : A ∩ B 6= ∅, where the domains for A and B are all subsets of
    Z. For each of the five properties of a relation defined in this chapter (reflexive, irreflexive,
    symmetric, antisymmetric, and transitive) either show M satisfies the property, or explain
    why it does not.
    Hint: This problem causes a lot of grief. The relation M is a relation between subsets of
    Z. For example, {1, 2}M{9} is false, since {1, 2} ∩ {9} = ∅. But {1, 2}M{2, 4, 6, 7} is true
    since {1, 2} ∩ {2, 4, 6, 7} = {2}, and not ∅.
    (6) (bonus) Let A = ∅ and consider the empty relation, E = ∅, on A. For each of the five properties
    of a relation defined in this chapter (reflexive, irreflexive, symmetric, antisymmetric,
    and transitive) either show M satisfies the property, or explain why it does not.
    Warning: Reasoning about the empty set can cause grave mental anguish. Suggestion:
    write out each of the five definitions you need to check (reflexive, symmetric, etc.) and
    decide if the statement is true or false.
    For example: For the reflexive condition, the statement to check is
    ∀x(x ∈ ∅ =⇒ (x, x) ∈ E)
    Since the left side of the implication (x ∈ ∅) is definitely false (after all there isn’t anything
    in the empty set!) the entire implication is true (recall the truth table for implication).
    That means the proposition above is true, and so E is reflexive. Reasoning for the remaining
    four conditions all follow a similar pattern.
    6. Lesson 6
    (1) Let A be the set of people alive on earth. For each relation defined below, determine if it
    is an equivalence relation on A. If it is, describe the equivalence classes. If it is not,
    determine which properties of an equivalence relation fail.
    (a) a H b ⇐⇒ a and b are the same age in (in years).
    6
    (b) a G b ⇐⇒ a and b have grandparent in common.
    (2) Consider the relation S(x, y) : x is a brother or sister of y on the set, H, of living humans.
    (Here x is a brother of y will mean x is a male different from y with the same two parents
    as y, so don’t consider half brothers. Likewise, in general, don’t consider half siblings.) Determine
    which of the three properties, reflexive, symmetric, transitive, hold for the relation
    S (explain your three answers). (Hint: Think carefully about transitive! Almost everyone
    gets this part wrong.) Is S an equivalence relation on H?
    (3) There are many different equivalence relation possible on the set A = {a, b, c, d}. For example,
    here are just three different ones:
    (a) E1 = {(a, a),(b, b),(c, c),(d, d),(a, c),(c, a),(b, d),(d, b)}.
    (b) E2 = {(a, a),(b, b),(c, c),(d, d),(a, c),(c, a),(a, b),(b, a),(b, c),(c, b)}.
    (c) E3 = {(a, a),(b, b),(c, c),(d, d)}.
    E1 has 8 ordered pairs while E2 has 10 and E3 has 4. Question: Of all the possible equivalence
    relations on A, what is the largest number of ordered pairs possible in the relation?
    (4) Let A be the set of all ordered pairs of positive integers. So some members of A are
    (3, 6),(7, 7),(11, 4),(1, 2981). A relation on A is defined by the rule (a, b)R(c, d) if and only
    if ad = bc. For example (3, 5)R(6, 10) is true since (3)(10) = (5)(6).
    (a) Explain why R is an equivalence relation on A.
    (b) List four ordered pairs in the equivalence class of (2, 3).
    (5) Let A = {1, 2, 3, 4, 5, 6}. Form a partition of A using {1, 2}, {3, 4, 5}, and {6}. These are
    the equivalence classes for an equivalence relation, E, on A. Draw the digraph of E.
    (6) (bonus) Let A = {1, 2, 3}. The relation E = {(1, 1),(2, 2),(3, 3),(2, 3),(3, 2)} is an equivalence
    relation on A. F = {(1, 1),(2, 2),(3, 3),(1, 2),(2, 1)} is another equivalence relation
    on A. Compute the composition F ◦ E. Is F ◦ E and equivalence relation on A?
    7. Lesson 7: Test #1
    8. Lesson 8
    (1) What is the 50th term of the arithmetic sequence with initial term 4 and common
    difference 3?
    7
    (2) Evaluate X
    4
    k=−3
    (2k + 5). (Hint: Since there are only eight terms in the sum, you can just
    write them all out and add.)
    (3) Evaluate X
    99
    i=0
    

    2
    3
    i
    . (Hint: Since there are 100 terms in the sum, it isn’t a good idea to
    write them all out and add. Use the formula for the sum of terms of a geometric sequence.
    Leave the answer with exponents rather than using a calculator to try to get a decimal
    approximation of the answer.)
    (4) (a) List the first four terms of the sequence defined recursively by a0 = 2, and, for n ≥ 1,
    an = 2a
    2
    n−1 − 1.
    (b) List the first five terms of the sequence with initial terms u1 = 1 and u2 = 5, and, for
    n ≥ 3, un = 5un−1 − 6un−2. Guess a closed form formula for the sequence. Hint: The
    terms are simple combinations of powers of 2 and powers of 3.
    (5) Give a recursive definition of the geometric sequence with initial term a and common
    ratio r.
    Hint: an = arn−1
    isn’t a correct answer since this formula isn’t recursive. Make sure you
    write down a recursive formula: (1) give the initial term, and (2) give the rule for building
    new terms from previous terms.
    (6) (bonus) Express in summation notation: 1
    2
    +
    1
    4
    +
    1
    6
    + · · · +
    1
    2n
    , the sum of the reciprocals
    of the first n even positive integers. (Note that there are n terms in the sum.)
    Hint: A common mistake on this question is using the symbol n both as an index for
    summation and to indicate the last term to be added in. To make sure you haven’t fallen
    into that trap, replace every n in your formula by a specific value, say 5. The result should
    be a sum 1
    2
    +
    1
    4
    +
    1
    6
    +
    1
    8
    +
    1
    10
    .
    9. Lesson 9
    (1) A set S of integers is defined recursively by the rules:
    (1) 1 ∈ S, and (2) If n ∈ S, then 2n + 1 ∈ S.
    (a) Is 20 ∈ S?
    (b) Is 175 ∈ S?
    Explain your answers.
    (2) A set, S, of strings over the alphabet Σ = {a, b, c} is defined recursively by (1) a ∈ S and
    (2) if x ∈ S then xbc ∈ S. List all the strings in S of length seven or less.
    8
    (3) A set, S, of positive integers is defined recursively by the rule:
    (1) 3 ∈ S, and (2) If n ∈ S, then 2n − 3 ∈ S. List all the elements in the set S.
    (4) Give a recursive definition of the set of positive integers that end with the digit 7.
    (5) Describe the strings in the set S of strings over the alphabet Σ = {a, b, c} defined recursively
    by (1) c ∈ S and (2) if x ∈ S then xa ∈ S and xb ∈ S and cx ∈ S.
    Hint: Your description should be a sentence that provides an easy test to check if a given
    string is in the set or not. An example of such a description is: S consists of all strings of
    a’s, b’s, and c’s, with more a’s than b’s. That isn’t a correct description since cab is in S
    and doesn’t have more a’s than b’s, and also baac isn’t in S, but does have more a’s than
    b’s. So that attempted description is really terrible. The best way to do this problem is
    to use the rules to build a bunch of strings in S until a suitable description becomes obvious.
    (6) (bonus) A set S of ordered pairs of integers is defined recursively by (1) (1, 2) ∈ S and
    (2, 1) ∈ S, and (2) if (m, n) ∈ S, then (m+2, n) ∈ S, and (m, n+2) ∈ S, and (m+1, n+1) ∈
    S. There is a simple description of the ordered pairs in S. What is it? Your description
    should be good enough so that you can instantly decide if (12236, 912242) is in S.
    10. Lesson 10
    Warning: It’s not unusual to find these problems really tough. One difficulty is that these problems
    will make some demands on your algebra skills. Another difficulty is just getting the format of an
    inductive proof correct. Here are a few suggestions concerning that: (1) Be sure to check the basis
    case; (2) At the start of the inductive step, clearly state the inductive hypothesis; (3) After stating
    the inductive hypothesis, write down what you need to prove; (4) Point out clearly where you apply
    the inductive hypothesis in the proof of the inductive step.
    (1) Use induction to prove: For every integer n ≥ 1,
    1 · 2 + 2 · 3 + 3 · 4 + · · · + n(n + 1) = n(n + 1)(n + 2)
    3
    .
    (2) Use the first form of induction (see example 16.5) to show that using only 4c/ stamps and
    7c/ stamps, any postage amount 18c/ or greater can be formed.
    (3) Redo the previous problem using the second form of induction (see example in the text).
    The basis step is just a bit messier this time, but the inductive step is much easier.
    (4) A sequence is defined recursively by the rules: (1) a0 = 0, and (2) for n ≥ 1, an = 2an−1+2.
    Use induction to prove an = 2n+1 − 2 for all n ≥ 0.
    (5) Use induction to prove: For every integer n ≥ 1, the number n
    5 − n is a multiple of 5.
    9
    Hint: An integer is a multiple of 5 if it is 5 times some integer. For example, 165 = (5)(33)
    so 165 is a multiple of 5.
    (6) (bonus) Here is a proof that for n ≥ 0, 1 + 2 + 22 + · · · + 2n = 2n+1
    .
    Proof. Suppose 1 + 2 + 22 + · · · + 2n = 2n+1 for some n ≥ 0. Then
    1 + 2 + 22 + · · · + 2n + 2n+1 = 2n+1 + 2n+1 using the inductive hypothesis
    = 2(2n+1) = 2n+2 = 2(n+1)+1
    ,
    as we needed to show.
    Now, obviously there is something wrong with this proof by induction since, for example,
    1 + 2 + 22 = 7, but 22+1 = 23 = 8. What specifically is wrong with the proof?
    11. Lesson 11
    For the proofs requested below, use facts and theorem given in this lesson, including results given
    in the exercises, as justifications. Assume all letters represent integers.
    (1) Mimic the proof given in the sample solutions for the proposition if a > 0 and b > 0, then
    ab > 0 to prove:
    (a) If a < 0 and b < 0, then ab > 0.
    (b) If a < 0 and b > 0, then ab < 0.
    (2) Prove that is m2 = n
    2
    , then m = n or m = −n.
    (Hints: (1) From algebra: a
    2 − b
    2 = (a + b)(a − b), and
    (2) From exercises: If ab = 0, then either a = 0 or b = 0.)
    (3) Determine all the integers that 0 divides.
    Hint: Think carefully about the definition of the divides relation! This question is
    about the divides relation, not about the arithmetic operation of division (a maybe subtle
    distinction). The correct answer is probably not what you might first think it is.
    (4) Prove: For integers r, s, t,and u, if r|t and s|u, then rs|tu.
    (5) Determine the quotient and remainder when 117653 is divided by 27869. (Finally, an easy
    problem.)
    (6) (bonus) Prove or give a counterexample: If p is a prime, then 6p + 1 is a prime.
    12. Lesson 12
    (1) Use the Euclidean Algorithm to compute the following gcd’s:
    10
    (a) gcd(216, 111).
    (b) gcd(1001, 11).
    (c) gcd(663, 5168).
    (d) gcd(1357, 2468).
    (e) gcd(733103, 91637).
    (2) If p is a prime, and n is any integer, what are the possible values of gcd(p, n)? Hint: Try
    a few experiments with specific numbers to spot the correct answer. Alternatively, think
    about the positive integers that can divide a prime. Warning: In the notation gcd(a, b),
    do not assume that a ≥ b. The two parameters a and b can be written in either order:
    gcd(15, 12) = gcd(12, 15) = 3.
    (3) Determine gcd(6123, 2913) and write it as a linear combination of 6123 and 2913.
    (4) What can you conclude about gcd(a, b) if there are integers s, t such that as + bt = 8?
    (5) What is the smallest positive integer that can be written as a linear combination of 2191
    and 1351?
    (6) (bonus) If n is a positive integer, what is gcd(n, n + 1)? Explain your answer.
    13. Lesson 13
    (1) Determine the prime factorization of 212100.
    (2) How many positive divisors does 212100 have? You don’t have to list them all, just determine
    how many there are. This isn’t difficult using the result of problem 1. See a similar
    example in the notes.
    (3) Find all integer solutions to 14x + 77y = 69.
    (4) Find all integer solutions to 14x + 77y = 70.
    (5) Beth stocked her video store with a number of video game machines at $79 each, and a
    number of video games at $41 each. If she spent a total of $6358, how many of each item
    did she purchase?
    (6) (bonus) Determine all integer solutions to 5x − 7y = 99. Watch that minus sign!
    11
    14. Lesson 14: Test #2
    15. Lesson 15
    (1) (a) Suppose we have a 52 card deck with the cards in order ace , 2, 3, . . . , queen, king top
    to bottom, for clubs, then diamonds, then hearts, then spades. A step consists to
    taking the top card and moving it to the bottom of the deck. We start with the ace of
    clubs as the top card. After two steps, the top card is the 3 of clubs. What is the top
    card after 735 steps?
    (b) The marks on a combination lock are numbered 0 to 39. If the lock is at mark 19, and
    the dial is turned one mark clockwise, it will be at mark 18. If the lock is at mark 19
    and turned 137 marks clockwise, at what mark will it be?
    (2) (a) Arrange the numbers −39, −27, −8, 11, 37, 68, 91
    so they are in the order 0, 1, 2, 3, 4, 5, 6 modulo 7.
    (b) Determine n between 0 and 16 such that
    311 + 891 ≡ n (mod 17).
    (c) Determine n between 0 and 16 such that
    (405)(777) ≡ n (mod 17).
    (d) Determine n between 0 and 16 such that
    710447 ≡ n (mod 17).
    (3) Find all solutions: 33x ≡ 183 (mod 753).
    (4) A multiple choice test contains 10 questions. There are four possible answers for each question.
    (a) How many ways can a student complete the test if every question must be answered?
    (b) How many ways can a student complete the test if questions can be left unanswered?
    (5) Here are two questions most easily done using the Good = Total − Bad method.
    (a) How many seven-letter words contain at least one X?
    (b) How many seven-letter words contain at least two X’s? Hint: The Bad ones are those
    with no X’s and those with exactly one X. Think carefully about counting the number
    of words with exactly one X.
    (6) (bonus) A code word is either a sequence of three letters followed by two digits or two letters
    followed by three digits. (Unless otherwise indicated, letters will means letters chosen from
    12
    the usual 26-letter alphabet and digits are selected from {0, 1, 2, 3, . . . , 8, 9}. Also, unless it
    is stated that letters have to be different, you should assume repeats are allowed. Likewise
    for digits.) How many different code words are possible?
    16. Lesson 16
    (1) (a) (a permutation problem, order matters) An ID code consists of 4 different letters and
    3 different digits. How many codes are possible if the letters must be kept together?
    For example, 34ABCD9 and W AXT604 are good, but T R67Y Z3 is bad.
    (b) (a combination problem, order does not matter) A lottery ticket consists of four different
    integers between 1 and 99 (inclusive). How many different lottery tickets are there?
    (2) Determine the coefficient of x
    4y
    5
    in the expansion of (3x − 2y)
    9
    . Be sure to take the 3 and
    the −2 coefficients into account.
    (3) Give an algebraic proof that 
    2n
    2
    
    = 2
    n
    2
    
    + n
    2
    .
    Hint: The idea is to expand and simplify each side of the equation, then compare the two
    results and make sure they are the same. This problem seems to cause a lot of anguish.
    It might help if the two sides are computed for a few specific values of n to see how the
    arithmetic works out. Try n = 3 and n = 4 for example.
    (4) A poker hand consists of five cards selected from a 52 card deck. The order of the cards in
    a poker hand does not matter. A poker hand is called a full house if it has two cards of one
    rank and three cards of a second rank. For example, a hand consisting of two 7’s and three
    queens is a full house. How many different full house hands are there?
    (5) How many permutations of the letters a,b,c,d,e,f,g either begin with an a or end with an a?
    (6) (bonus) A committee of size five is selected from a group of ten clowns and twelve lion
    tamers.
    (a) How many different committees are possible?
    (b) How many committees are possible if there must be exactly two clowns on the committee?
    (c) How many committees are possible if lion tamers must outnumber clowns on the committee?
    13
    17. Lesson 17
    (1) Inclusion-exclusion counting: Among the members of a book club, 2 people have read War
    and Peace (WP) and Moby Dick (MD) and The Great Gatsby (GG), 3 have read WP and
    GG only, 1 has read MD and GG only, 4 have read WP and MD only, 11 have read only
    WP, 7 have read only MD, and 21 have read only GG. Assuming everyone in the club has
    read at least one of those three books, how many members does the book club have?
    (2) More inclusion-exclusion counting: How many bit strings of length 15 have bits 1, 2, and 3
    equal to 101, or have bits 12, 13, 14, and 15 equal to 1001 or have bits 3, 4, 5, and 6 equal
    to 1010? (Number bits from left to right. In other words, bit #1 is the left most bit and
    bit #15 is the right most bit.)
    Hint: The fact that the third bit appears in two of the required patterns means some
    special care will be needed to get the count correct.
    (3) Show that there are two different positive powers of 5 (in other words, 5n
    , for positive
    integers n), that differ by a multiple of 123.
    (4) Plutonians have three feet. Suppose the Plutonian Vancleef has a box with one hundreds
    each of red, blue, yellow, green, and white socks. Plutonian etiquette requires that Vancleef
    wear three socks of the same color. It’s dark, and Vancleef can’t see. What is the minimum
    number of socks Vancleef needs to take from the box to be sure there will be a suitable
    triplet of socks?
    (5) Rocky has 31 days to prepare for his Discrete Math final. He has decided to do at least
    one tough problem each day, but no more than 50 problems total. Show there must be a
    sequence of consecutive days in which he does exactly 11 problems.
    (6) (bonus) Here’s a pretty hard looking (but really not too hard if done carefully) inclusionexclusion
    problem. The correct answer is 76. You job is to show the work that leads to
    that answer.
    How many permutations of the digits 1, 2, 3, 4, 5, have at least one digit in its own spot?
    In other words, a 1 in the first spot, or a 2 in the second, etc. For example, 35241 is OK
    since it has a 4 in the fourth spot, and 14235 is OK, since it has a 1 in the first spot (and
    also a 5 in the fifth spot). But 31452 in no good. Hint: Let A1 be the set of permutations
    that have 1 in the first spot, let A2 be the set of permutations that 2 in the second spot,
    and so on. As a start, notice that |A1| = |A2| = |A3| = |A4| = |A5| = 4!
    18. Lesson 18
    (1) Suppose on December 31, 2000, a deposit of $100 is made in a savings account that pays
    10% annual interest (Ah, those were the days!). So one year after the initial deposit, on
    December 31, 2001, the account will be credited with $10, and have a value of $110. On
    December 31, 2002 that account will be credited with an additional $11, and have value
    $121. Find a recursive relation that gives the value of the account n years after the initial
    deposit.
    14
    (2) Sal climbs stairs by taking either one, two, or three steps at a time.
    (a) Determine a recursive formula for the number of different ways Sal can climb a flight
    of n steps. Don’t forget to include the initial conditions.
    (b) In how many different ways can Sal climb a flight of ten steps?
    (3) Passwords for a certain computer system are strings of uppercase letters. A valid password
    must contain an even number of X’s. Determine a recurrence relation for the number of
    valid passwords of length n. Note: 0 is an even number, so ABBC is a valid password.
    This counting problem is pretty tricky. Here’s a good way to think about it: to make a
    good password of length n you can either (a) add any non-X to the end of a good password
    of length n − 1, or (b) add an X to the end of a bad password of length n − 1. For (b)
    you can use the Good = Total-Bad trick to count the number of bad passwords of length n−1.
    (4) Solve by unfolding: a0 = 3, and, for n ≥ 1, an = 5an−1.
    (5) Solve by unfolding: a0 = 3, and, for n ≥ 1, an = 5an−1 + 3. Hint: This one will involve
    applying the geometric sum formula.
    (6) (bonus) Suppose the Tower of Hanoi rules are changed so that stones may only be transferred
    to an adjacent clearing in one move. Let In be the minimum number of moves
    required to transfer tower from clearing A to clearing C? For example, it takes two moves
    to move a one stone tower from A to C: One move from A to B, then a second move from
    B to C. So I1 = 2
    (a) By brute force, determine I2, and I3.
    (b) Find a recursive relation for In.
    (c) Guess a formula for In.
    19. Lesson 19
    Warning: These problems are going to severely tax your algebra skills and maybe also your
    patience since they are likely to require a lot of time and paper. Be prepared to review some
    college algebra techniques if necessary.
    (1) Solve a0 = 1, and an = 3an−1, for n ≥ 1 using the characteristic equation method.
    (2) Solve a0 = 1, and an = 3an−1 + 1 for n ≥ 1 using the characteristic equation method.
    Hint: Try an = A, a constant, to find a particular solution.
    (3) Solve a0 = 1, a1 = 3 and an = an−1 + 6an−2, for n ≥ 2.
    15
    (4) a0 = 1, a1 = 3 and an = an−1 + 6an−2 + 1, for n ≥ 2. Hint: Use the general solution to the
    homogeneous problem above, and then try an = A, a constant, to find particular solution.
    (5) Solve a0 = 1, a1 = 6 and an = 6an−1 − 9an−2 + n, for n ≥ 2.
    Hints: (1) Be sure to remember what to do when there are repeated characteristic roots.
    (2) Try an = An + B for a particular solution.
    (6) (bonus) Solve a0 = 0, a1 = 1 and an = an−1 + an−2 + 2n
    , for n ≥ 2.
    Hints: This one involves a lot more algebra than the problems above. Solving the homogeneous
    problem will involve using the quadratic formula. The characteristic roots turn out
    to be 1 ±

    5
    2
    (but show the work!). For a particular solution, try an = A2
    n
    . You should
    find A = 4 (but show the work!). Put those two pieces together to write down the general
    solution
    an = A(
    1 + √
    5
    2
    )
    n + B(
    1 −

    5
    2
    )
    n + 4(2n
    )
    and the determine the values for A and B by using the two initial conditions, a0 = 0 and
    a1 = 1. The necessary arithmetic will be somewhat complicated, but not impossible.
    20. Lesson 20
    (1) Determine the adjacency matrix and the incidence matrix for the graph below.
    z
    v
    w
    y x
    (2) For the graph below
    (a) Find an Eulerian path, or prove that none exists.
    (b) Find a Hamiltonian circuit or prove that none exists.
    16
    a b c
    d e f
    g h i
    (3) For the graph below
    (a) Determine all the bridges.
    (b) Determine all the cutvertices.
    a b c d e f
    g h
    (4) For each candidate degree sequence below, either draw a graph with that degree sequence
    or explain why that list cannot be the degree sequence of a graph.
    (a) 4, 4, 4, 4, 4
    (b) 6, 4, 4, 4, 4
    (c) 0, 0, 0, 0, 0
    (d) 3, 2, 1, 1, 1
    (e) 3, 3, 2, 2, 1
    (5) A forest is a graph consisting of one or more (separate) trees. If the total number of vertices
    in a forest is f, and the number of trees in the forest is t, what is the total number of edges
    in the forest?
    (6) (bonus) A tree is called star-like if there is exactly one vertex with degree greater than
    2. How many different (that it, nonisomorphic) star-like trees are there with six vertices?
    (Note: If you draw the graph with the vertex of of degree greater than 2 having the arms
    of the tree radiating out from it like spokes on a wheel, the name star-like will make sense.
    21. Lesson 21: Test #3
find the cost of your paper