Groupwork Sessions I Developed For My Summer 2001 Discrete Math Class

Worksheet #1

1. If a compound proposition involves n propositions, how many rows will a truth table require?

2. Find a compound proposition involving three propositions p, q, and r which is true when exactly two of p,q,r are true, and is false otherwise.

3. Based on Question 2, do you see intuitively why every compound proposition can be expressed using only "and", "or", and "not" ?

4. Express p --> q using only "and", "or", and "not".

Worksheet #2

1. In a survey of 270 college students, it is found that 64 like brussels sprouts, 94 like broccoli, 58 like cauliflower, 26 like both brussels sprouts and broccoli, 28 like both brussels sprouts and cauliflower, 14 like all three vegetables, and 128 dislike all three vegetables. How many of the students like broccoli and cauliflower, but not brussels sprouts?

2. Let A_i = {i,i+1,i+2,...}. Find (a) the union of A_1, A_2, ..., A_n, and (b) the intersection of A_1, A_2,...,A_n.

3. Find two sets A and B such that A is an element of B and A is simultaneously a subset of B.

Worksheet #3

1. Consider the polynomial f(x) = a_n*x^n + a_{n-1}*x^{n-1} + ... + a_1*x + a_0, viewed as a function from R to R. Under what conditions on n is f guaranteed to be (a) onto (b) not onto (c) 1-1 (d) not 1-1 ?

2. If f: A ---> B is a function and A and B are finite sets with |A|=|B|, try to show why (a) if f is 1-1, then it's also onto, and (b) if f is onto, then it's also 1-1.

[Note: What you've shown is that f is 1-1 <===> f is onto when the domain and codomain are finite sets of the same size. THIS IS VERY IMPORTANT! Whenever you are trying to show a bijection between two finite sets which you know in advance are the same size, you need only show the 1-1 property OR the onto property: once you've shown one or the other, the second property must automatically hold by this exercise!

Worksheet #4

1. Find integers a and b such that 6 = 17a + 73b.

2. We can associate the alphabet letters with 00-25 via: A <--> 00, B <--> 01, ... Z <--> 25. We can code a message by first changing the letters into numbers, and then using a coding function f. A certain message is coded via f(n) = 7n + 10 (mod 26) and reads LJMKGM GMXF QEXMW. Decode this message.

3. Show that if m is at least 2 and m | (a-b), then gcd(a,m)=gcd(b,m).

Worksheet #5

1. For an integer n, show that if 3n+2 is even, then 9n+5 is odd.

2. Prove that 1 + 1/4 + 1/9 + ... + 1/n^2 < 2 - 1/n whenever n is at least 2.

3. Without a calculator, compute 92^108 (mod 55).

Worksheet #6

1. Four male and three female suspects are being arranged for a line-up. How many ways are there to do this if (a) there are no restrictions? (b) the men and women must alternate? (c) the three women must stand in consecutive positions? (d) the shortest man and tallest woman must stand next to each other?

2. There are 51 houses on a street. Each house has an address between 1000 and 1099 inclusive. Show that at least two houses have addresses which are consecutive integers.

3. How many bit strings of length 10 (a) either begin with 3 zeroes or end with 2 zeros? (b) contain 8 consecutive zeroes?

Worksheet #7

1. Consider forming strings of letters of length 26 by using each letter of the alphabet exactly once. How many strings are possible with (a) no restrictions? (b) "CAT" as a sub-word within the string? (c) "CAT" or "DOG" as sub-words within the string? (d) "CAT" or "HAMPSTER" as subwords within the string? (e) "CAT" and either "DOG" or "FISH" as subwords within the string?

2. How many strings of 7 distinct letters of the alphabet contain (a) at least 1 vowel? (b) exactly 1 vowel? (c) at least 2 vowels?

3. A restaurant produces 80 different fortunes for its fortune cookies. (a) How many times must a student eat at this restaurant to ensure that he gets the same fortune 7 different times? (b) Assuming the restaurant only produces 1000 copies of each fortune, how many times must the student eat at this restaurant to ensure getting at least 3 different fortunes at least 7 times each?

Worksheet #8

1. (a) In how many ways can 12 different pieces of jewelry be given to 6 different people? (b) In how many ways can 12 identical pieces of jewelry be given to 6 different people? (c) In how many ways can 6 different pieces of jewelry be placed in 12 different boxes if each box can fit at most one piece? (d) In how many ways can 6 identical pieces of jewelry be placed in 12 different boxes if each box can fit at most one piece? (e) In how many ways can 12 different pieces of jewelry be given to 6 different people if each person gets exactly two pieces?

2. How many 5-card poker hands do not contain all 4 suits?

3. (a) How many ways are there to put 30 identical racquetballs into the 5 compartments of your gym bag if you always like at least 2 balls in each compartment, but the first compartment can hold at most 6 balls? (b) How many balls would be needed to guarantee that some compartment other than the first one has at least 4 balls in it?

Worksheet #9

1. The "Collected Novels" of Mrs. Kip Vandegril have been published in ten volumes. Assume that Roger checks out five of these volumes from the local library, chosen at random, without knowing that Mrs. Vandegril wrote only five novels, each occupying two volumes.

(a) What is the probability that Roger can read (i) no complete novels? (ii) exactly one complete novel? (iii) exactly two complete novels? (iv) more than two complete novels? (b) What is the expected number of novels that Roger can read?

2. This problem discusses a rare case in which the sample space is infinite. Imagine the experiment in which a coin is flipped until it comes up heads. Assume the probability of heads on a given flip is p.

(a) What is the probability that the experiment ends with the nth flip?

(b) Show that the sum of the probabilities in (a) over all positive integers n is 1.

3. At a party n people toss their hats into a closet. Each person then selects a hat at random. What's the probability that a given person will get their own hat back? What's the expected number of people who will get their own hat back?

Worksheet #10

1. Find the general solution of the recurrence relation a_n = 4a_{n-1} - 4a_{n-2} + (n+1)*2^n.

2. In how many ways can 15 identical stuffed animals be given to six children so that each child gets 1,2, or 3 stuffed animals?

3. Put the following numbers in increasing numerical order: p(D_5), p(D_8), p(D_10), p(D_13), 1/e.

Worksheet #11

1. Let A = the set of all strings of English letters. Determine whether the following binary relations on A are reflexive, symmetric, transitive, and/or antisymmetric:

(a) R_1 = {(x,y): x and y are strings with no letters in common}

(b) R_2 = {(x,y): x and y are strings of different lengths}

2. Let |A|=n. How many binary relations are there on A? How many of these are (a) reflexive? (b) symmetric? (c) reflexive AND symmetric? (d) reflexive OR symmetric? (hint: use (a),(b),(c) for (d).)

3. Give an example of a set A and a relation R on A which is (a) reflexive and symmetric, but not transitive; (b) reflexive and transitive, but not symmetric; (c) symmetric and transitive, but not reflexive. [Hint: try to draw charts to reflect the right properties]

4. Based on 3(c), we know the following "claim" must be wrong:

FALSE CLAIM: Let R be a symmetric and transitive relation on a set A. Then R must be reflexive.

Find my error in the "proof" of this "claim": (omitted)

5. Give an example of a set A and a relation R on A which is (a) both symmetric and antisymmetric; (b) either symmetric nor antisymmetric; (c) can you make a conjecture describing exactly which relations on A will be both symmetric and antisymmetric in general?

Worksheet #12

1. Let S_10 = the set of all permutations of {1,2,3,4,5,6,7,8,9,10}. Define a relation <= on S_10 as follows: for p_1, p_2 in S_10, say p_1 <= p_2 <====> p_1=p_2 or p_1 leaves less numbers in their fixed original positions than p_2

(a) Convince yourself that <= is a partial order on S_10.

(b) Is there a greatest element? a least element?

2. Let S+10 be as before. Define p_1 R p_2 <====> p_1 and p_2 leave the same number of numbers in their fixed, original positions.

(a) Convince yourself that R is an equivalence relation.

(b) How many equivalence classes are there? [Be careful!]

(d) How many elements are in the equivalence class of 173X564892?

Worksheet #13

1. How many vertices and edges do the following graphs have: (a) K_n (b) C_n (c) W_n (d) Q_n (e) K_m,n ?

2. Let G be a simple graph which is bipartite. If G has v vertices and e edges, show that e <= v^2/4.

3. A partially ordered set in which every pair of elements has both a least upper bound and a greatest lower bound is called a lattice. Let S be any set and consider the poset (P(S), subset). Show that this is a lattice. [Hint: how do you get the L.U.B. and G.L.B. of a pair of subsets A and B?]

Worksheet #14

0. This groupwork concerns planar graphs, so first remind your group about the Euler formula and the main inequalities relating e to v in a connected, planar, simple graph-you're going to need them below!

1. A friend claims to have constructed a connected, planar, simple, bipartite graph with 8 vertices and 13 edges. Give your friend a reality check!

2. Show that Q_1, Q_2, and Q_3 are planar, but that for n at least 4, Q_n is non-planar.

3. Is the Petersen graph planar?

4. [hard] The crossing number of a simple graph is the minimum number of crossings that can occur when this graph is drawn in the plane (and no 3 edges are allowed to cross simultaneously at a single point). Intuitively, the crossing number is a measure of "how close" a graph is to being planar. For example, G is planar <===> it has crossing number=0. And the smaller the crossing number, the "closer" G is to being planar.

What is the crossing number of (a) K_3,3 (b) K_5 (c) K_4,3 (d) the Petersen graph ?

[Note: Be careful. Once you think you've drawn the graph with the fewest crosses possible, say k crosses, YOU MUST STILL SHOW that it's impossible to draw it with k-1 crosses before you can say with certainty that the crossing number is k. Strategy to show this: Take a contradiction approach. If you could somehow draw the graph with only k-1 crosses, then removing the edges which cause the crosses will leave you with a planar graph, and now you can use what you know about planar graphs!]

Worksheet #15

1. For what values of m and n does the complete bipartite graph K_m,n have (a) an Euler circuit? (b) an Euler path but not an Euler circuit? (c) a Hamilton circuit?

2. Show why a bipartite graph with an odd number of vertices cannot have a Hamilton circuit.

3. A knight's tour is a sequence of legal moves by a knight starting at some square of a chessboard and visiting each square exactly once.

(a) What does a knight's tour have to do with this material?

(b) Why isn't there a knight's tour on a 3 by 3 chessboard?

(d)(hard/optional) How about a 4 by 4 chessboard?

Return to Scott's Main Page