Discrete Mathematics Homework


Homework 1

Write a proof that given any net diagram, any specified element at the top of the diagram, any specified position at the bottom of the diagram and any specified height in the net diagram, it is possible to add a single rung at that height so that the element at the top will end up at the specified position on the bottom of the diagram.
(back to home page)
Homework 2 - Due Wednesday, 1/30, in class
  1. Find a net diagram to produce the permutation "75612843" relative to the home position "12345678."
  2. What is the least number of rungs needed in a net diagram for problem 1?
  3. Suppose a permutation contains k inversions.  Prove that any net diagram that uses only short rungs must contain at least k rungs. 
  4. How many different permutations of "12345" can be made by a net diagram consisting of exactly one rung?
  5. How many different permutations of "12345" can be made by a net diagram consisting of exactly two rungs?
  6. What is the greatest number of rungs that could be needed in a permutation of the numbers "12345" ?  Give examples of two different permutations that need exactly that many rungs.  [XC+5  How many permutations of "12345" need that maximum number of rungs?]
(back to home page) 		Definiton:
A short rung is a rung that connects two adjacent vertical struts in a net diagram.  For example, the figure below uses only short rungs.
Homework 3 - Due Monday, 2/18, in class
  1. How many anagrams are there of each of these words:
    1. CAT
    2. DOG
    3. GO
    4. JANE
    5. RUN
    6. SEE
    7. LOOK
  2. Make a tree diagram showing all anagrams of the following words
    1. CAT
    2. SEE
    3. JANE
    4. LOOK
  3. Make a tree diagram showing all anagrams of the word PETER
  4. How many outcomes are possible in each of the following experiments?  In each case, express your answer as an integer, and show your work.
    1. Flip a coin 4 times
    2. Toss a die three times
    3. Flip a coin twice and toss a die twice
    4. Draw 3 cards from a deck, without replacing the cards after they're drawn
  5. How many functions are there from the set {A, B, C, D, E} to the set {1, 2, 3, 4, 5, 6, 7}?  You do not need to express your answer as an integer.
  6. How many functions are there from {A, B, C} to {A, B, C}?
  7. Draw a function from {A, B, C} to {1, 2, 3} that is 1-1 but not onto.
  8. Draw a function from {A, B, C} to {1, 2, 3} that is onto but not 1-1.
  9. Draw a function from {A, B, C} to {1, 2, 3} that is both 1-1 and onto.
  10. If I draw a net diagram with the rungs at all different levels, then you can view that net diagram as generating a sequence of permutations, along the way from top to bottom, as shown in the picture to the right. 

    The word ABC has six permutations.  Draw a net diagram with three vertical bars labelled "ABC" at the top, and five horizontal rungs, so that along the way from top to bottom, it generates all six permutations of ABC, including the identity permutation at the top, before any of the rungs.

    Can this be done using only short rungs?

    [XC +10]  Make a net diagram having 23 rungs that gives all 24 permutations of ABCD.  Show the permutations along the way, and give a sentence or two explaining how you did it.
(back to home page)
This net diagram has eight rungs, yielding eight (not-necessarily distinct) permutations of ABCDE in addition to the identity permutation.

These permutations are shown after each rung.
Homework 4
  1. Draw the first 8 rows of Pascal's Triangle, and circle (4 Choose 3) and (7 Choose 2) it.
  2. Evaluate each of the following as an integer:  5 Choose 2, 10 Choose 3, 12 Choose 2, 8 Choose 3 and 21 Choose 3.
  3. A teacher wishes to assign four students to be blackboard cleaners.  How many ways are there to make this selection from among her 15 students?  Express your answer as an integer.
  4. How many ways are there to flip 4 coins sequentially, and get 2 Heads and 2 Tails?  HHTT is one such way.
  5. Flip a coin 10 times.  What is the probability of getting exactly 3 Heads?   (Recall, this would be the ratio:  # successful outcomes / total # possible outcomes.)
  6. Toss twelve dice.  What is the probability that each number comes up exactly twice?
  7. Deal five cards from a deck.  What is the probability that you've got all the aces?
  8. How many seven-card hands are there that have one club, one diamond, two hearts and three spades?  Recall that the cards in a "hand" are considered to be a set, not a sequence.  That is, rearranging the cards does not change the hand.
  9. Expand (2x + 3y)4 using the binomial theorem.
  10. What is the coefficient of each of the following terms in the expansion of (w + x + y + z)7.  Express each of your answers as an integer. 
    1. wxyz4
    2. w2x3z2


(back to home page)
Homework 5 - Due Wednesday, April 9.
  1. Draw the multiplication table for multiplication mod 9.  This ought to be a 9x9 table.
  2. Based on your work from problem 1, which numbers have multiplicative inverses mod 9?   Explain your answer, and for each number that does have an inverse, say what it is.
  3. Find the greatest common divisor of each of the following pairs of integers, using any method you wish:  (10, 15), (33, 44), (168, 190).
  4. Fund the greatest common divisor of each of the following pairs of integers, using the Euclidean Algorithm:  (452, 608), (1541, 966), (456, 877), (203, 1980), (44, 19889), (60, 75431)
  5. For each of the pairs in problem 4 which are relatively prime, find the multiplicative inverse of the smaller number mod the larger number.  Also, show how you would check your answer.  (You may use a calculator for any part of this problem, as long as you indicate where you used the calculator.)
  6. Find two integers x and y such that 60x + 75431y = 1.
  7. Evaluate 47124123 mod 7, 189723 mod 8, 829317890 mod 11 and 17831231478 mod 12.  (You may use a calculator for any part of this problem, as long as you indicate where you used the calculator.)
  8. For each of these expressions:  6123789 mod 7, 7940384723784 mod 10, and 310136499 mod 31,   say why each of these may be evaluated in your head, and then evaluate them.
Final Homework - Not to be graded.  Use as a study guide.

1.    Prove that the sum of two odd numbers must be an even number.

2.    Prove that the product of an even number and an odd number must be an even number.

3.    Construct or prove that there is no graph with six vertices having degrees 2, 3, 3, 4, 5, 6 respectively.

4.    Construct or prove that there is no graph with six vertices having degrees 2, 3, 4, 4, 5, 6 respectively.

5.    Build a truth table for the compound proposition (p  AND q)  --> (p OR  q).

6.    Prove that ¬(p  OR q) is logically equivalent to  (¬p AND  ¬q), by building a truth table for each expression.

7.    Prove that if a graph has a path from vertex v to vertex w, and a path from vertex w to vertex x, then it also has a path from vertex v to vertex x.