## 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