Math 55 - Discrete Mathematics - Homework Assignments - Fall 2007

Homework is due in section at the beginning of class the day it is due (Wednesday section). A few problems on each weekly homework assignment will be chosen at random to be graded. You are encouraged to work in groups in homework, but you must each turn in your own work. No late homework will be accepted, since answers will be available at Copy Central Northside and/or here the day after they are due. The lowest three homework grades will be dropped. The material in this class can only be learned by doing lots of problems, so the homework is very important.

Section and problem numbers below refer to the 6th edition of the textbook by Rosen, which differ from the 5th edition.

Assignment 1, due Sept 5 (posted Aug 28, 7:05am)

Sec 1.1: 8(a,c,e), 10(a,f), 28(e), 56, 60

Sec 1.2: 10(a), 26, 50

Sec 1.3: 8(a,d), 10(a,c,e), 16, 38(a,c,e), 44

Sec 1.4: 4(a,b,c), 28(f,i,j), 48

Sec 1.5: 20, 24

Sec 1.6: 12, 16

Assignment 1 solutions, in pdf

Assignment 2, due Sept 12 (posted Sep 6)

Sec 2.1: 8(a,b,c,g), 16, 20, 26

Sec 2.2: 4, 34, 44, 46, 50 for sets {2,4,6,8,10} and {1,3,5,7,9}

Sec 2.3: 6, 16 (but for Z, not N), 30, 36, 68 , 70(a,c)

Assignment 2 solutions, in pdf

Assignment 3, due Sept 19 (posted Sep 11, 2:45pm)(due date corrected 9/16) (also available in pdf)

(1) In Lecture 6, we used nearly the same proof to show that the set of real numbers is uncountable, and that the set of all functions with domain N and codomain {0,1} is uncountable. In this problem you are to modify these two proofs very slightly, so that they are still correct, but work slighlty differently. For the proof that real numbers are uncountable, use the expansion of each real number in decimal instead of binary. For the proof about functions, show that the set of functions with domain N and codomain {0,1,2,3,4,5,6,7,8,9} is uncountable.

(2) A real number is called "algebraic" if it is the root of a polynomial with rational coefficients and degree at least 1. Let A be the set of all algebraic numbers. So A includes the rational numbers, sqrt(2), cuberoot(5-sqrt(2))/sqrt(3)), any other such expression with roots and integers, and infinitely many other irrational numbers besides. This exercise will show that A is still countable.

(2.1) Show that if r is a root of a polynomial with rational coefficients, then it is also the root of a polynomial with integer coefficients. So we won't miss any algebraic numbers by restricting ourselves to polynomials with integer coefficients instead of rational coefficients.

(2.2) Show that the set P_d of polynomials of degree d >= 1 and with integer coefficients is countable. (A polynomial has degree d if it can be written as a_d*x^d + a_{d-1}*x^(d-1) + ... + a_1*x + a_0 where a_d is nonzero.)

(2.3) Show that the set A_d of all roots of all polynomials in P_d is countable.

(2.4) Show that the set A of all algebraic numbers is countable.

(2.5) Conclude that there are many more real numbers than can be expressed as roots of polynomials with rational coefficients.

(3) Prove by contradiction that log_(1.23) 4.56 is irrational.

(4) Simplify O(f(n)) where f(n) is given below. Your expression should be both as simple and accurate as possible (it should not overestimate f(n) by more than a constant factor). All logarithms are base pi.
f(n) =
[ 9^(2^(n^.3)) - 2^(9^(n^.3)) ] *
[ .99^(n^3) + log (log (log (log n ))) ] *
[ (log (log n))^(log (log (log n))) +
(log (log (log n)))^(log (log n)) ] *
[ 3^n * n^4 - 4^n * n^3 ] *
[ 89*n^4 + 1234 * n * (log n)^18 ]

Sec 2.4: 12, 22,

Sec 3.2: 18, 36

Assignment 3 solutions, in pdf

Assignment 4, due Sept 26 (posted Sep 23, 2:10p; this is very short because of the midterm on Sep 24).

(1) What is the prime factorization of 17! ?

(2) How many zeros are there at the end of the decimal expansion of 17! ?

Assignment 4 answers

(1) Multiply the prime factorizations of 2 through 17 to get 2^15 * 3^6 * 5^3 * 7^2 * 11 * 13 * 17

(2) The answer is the number of times 10 divides 17!, and according to its prime factorization the answer is 3 times, since 2 divides it 15 times but 5 only 3 times.

Assignment 5, due Oct 3 (posted Sep 28, 3:50pm)

Sec 3.4: 22, 24, 34

Sec 3.5: 8, 14, 26, 32

Sec 3.6: 24(c,d), 28(c), 46(d)

Assignment 5 solutions, in pdf

Assignment 6, due Oct 10 (posted Oct 3, 5:23am)

The purpose of this question is to illustrate that there are a lot of primes.

(a) Let n and d be integers, and x = n*10^d. Use the Prime Number Theorem to evaluate the limit as d -> infinity of pi(x + 10^d)/pi(x), where pi(x) is the number of primes less than or equal to x (in other words, n is fixed and d is growing to infinity).

(b) Use part (a) to show that given any arbitrary string of decimal digits (representing the integer n), then for all sufficiently large M, there is always a prime p such that

(1) p has an M-digit decimal expansion, and

(2) p's decimal expansion starts with the given string (representing n)

For example, there are infinitely many primes that start with the digits 31415926535.

Sec 3.6: 38, 40, 56

Sec 3.7: 4, 16, 20, 22, 24, 28

Assignment 6 solutions, in pdf

Assignment 7, due Oct 17 (posted Oct 11, 6:10am)

Sec 4.1: 6, 10, 16, 36, 46, 58

Sec 4.2: 4, 8, 14, 30, 34,

Assignment 7 solutions, in pdf

Assignment 8, due Oct 24 (posted Oct 17, 9:00am)

(1) Let f(n) be the n-th Fibonacci number, i.e. f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2) for n >= 2. Let r1 = (1+sqrt(5))/2, r2 = (1-sqrt(5))/2. Prove by induction that f(n) = (r1^n - r2^n)/sqrt(5)

(2) Let cost(n) be the number of additions needed to compute f(n) by the following recursive algorithm:

func f(n)
if n=0 return(1)
else if n=1 return(1)
else return(f(n-1)+f(n-2))

Use induction to prove that cost(n) = f(n+1)-1, which means that the cost of the recursive algorithm grows very fast, O(r1^n), i.e. about O(1.62^n)

(3) Suppose g(1) = 7, g(2) = 8, and g(n)=2*g(n-1)-2*g(n-2) for n>2. Derive a closed form formula for g(n).

Sec 4.3: 14, 26(a,c), 38, 48, 52, 62

Sec 4.4: 24, 26, 42

Assignment 8 solutions, in pdf

Assignment 9, due Oct 31 (posted Oct 25, 6:00pm)

Sec 5.1: 40, 56, 58

Sec 5.2: 10, 36, 42

Sec 5.3: 26, 42

Sec 5.4: 10, 26, 30, 38

Assignment 9 solutions, in pdf

Assignment 10, due Nov 14 (posted Nov 7, 3:50pm)

1) You are organizing a dance with students attending from 4 classes: there are 4 freshman (Ann, Dan, Fran, and Stan), 4 sophomores (Eeny, Meeny, Miny and Moe), 4 juniors (Harry, Ron, Hermione and Albus), and 6 seniors (Jack, Kack, Lack, Mack, Nack and Oack). For one of the dances, you need to arrange 10 students to stand in a circle, all facing the center and holding hands. How many different circles of students can you arrange if there must be exactly 2 sophomores and 2 juniors, with a sophomore immediately to the right of each junior?

2) In the game of Set, you have a deck of cards. Each card has 1 or more objects drawn on it, which have the following properties:

Each object has one of 3 shapes: diamond, oval or squiggle.

Each object has one of 3 colors: purple, red or green.

Each object has one of 3 shadings: solid, striped or empty.

There can be 1, 2 or 3 objects drawn on each card (if there is more than 1 object on a card, all have the identical shape, color and shading).

To play the game, some of the cards are put face up on the table, and all players look for 3 cards that "match", where to match the three cards must

all have the same shaped objects, or must have 3 different shapes

all have the same color objects, or must have 3 different colors

all have the same shaded objects, or must have 3 different shadings

all have the same number of objects, or must have 3 different numbers

Whenever a player sees matching cards, they yell "match!", pick up the three matching cards, and replace them with 3 new cards. The game continues until no player can find any more matches, and the player who found the most matches wins.

2.1) If the deck of cards has exactly one of each kind of possible card, how many cards are there?

2.2) How many different subsets of 3 cards are there in the deck that match?

3) (Based on a 1st grade homework assignment from a local school.)

3.1) Suppose you can have 9 pieces of fruit, which can be either apples or oranges. How many ways can you have 9 pieces of fruit (for example, you could have 4 apples and 5 oranges, or 0 apples and 9 oranges, etc.)?

3.2) Answer 3.1) for n pieces of fruit.

3.3) Suppose you can have 9 pieces of fruit, which can be apples, oranges or pears. How many ways can you have 9 pieces of fruit (actual 1st grade assignment)?

3.4) Answer 3.3) for n pieces of fruit.

3.5) Suppose you can have n pieces of fruit, and there are m different kinds of fruit. How many ways can you have n pieces of fruit?

4) (Based on another 1st grade homework assignment.) Suppose you can make shapes from putting together identical equilateral triangles edge-to-edge. Triangles must not overlap, and if they are adjacent, they must line up along an entire edge. In the picture below, the leftmost shape is ok, and the other two are not. Shapes must be connected (i.e. you can get from any triangle to any other triangle by moving across adjacent edges).

How many different shapes using 2, 3, 4, 5, and 6 triangles are there? Shapes are considered the same if one shape can be slid or rotated (but not turned over) to lie exactly on top of the other shape. (The 6 triangle problem was the actual 1st grade assignment. For fun you can try 7 triangles, but this is harder.)

5) Sec 5.5: 14, 28, 64

6) Sec 6.1: 32, 40

7) Lenstra's notes: Exercises 1, 2

Assignment 10 solutions, in pdf

Assignment 11, due Nov 21 (posted Nov 15, 11:00am)

Lenstra's notes: Exercises 3, 4, 5, 6

Sec 6.1: 14, 24, 36,

Sec 6.2: 10, 18, 26

Sec 6.4: 4, 6, 18, 20

Assignment 11 solutions, in pdf

Assignment 12, due Nov 28 (posted Nov 22, 8:05am)

(1) In an election for B and G, suppose there were exactly 2 votes cast. As in the notes, let avG be the actual number of votes cast for G and avB be the actual number of votes cast for B. Each vote cast is counted correcty with probability 1-p, and miscounted with probability p. Let vcG be the number of votes counted for G and let vcB be the number of votes counted for B.
Thus the set of possible values for the pair (avG,avB) is (2,0), (1,1), and (0,2). The pair (vcG, vcB) can independently take on the same three pairs of values.
Your assigment is to compute
P(vcG votes were counted for G and vcB votes were counted for B when G actually got avG votes and B actually got avB votes)
for all 9 possible combinations of (avG,avB) and (vcG, vcB). In other words, your answer should be 9 functions of p.
For example, suppose (avG,avB) = (2,0), so both votes were actually cast for G, and (vcG,vcB) = (0,2), so both votes were counted for B. This can only happen if both votes were miscounted, which has probability p^2. Your job is to compute the remaining 8 probabilities.

(2) Consider the election between G and B again. The notation is again as in the class notes. Now assume that after a vote is cast

P(the vote is counted for the wrong person) = p

P(the vote is lost and not counted) = q

P(the vote is counted correctly) = 1-p-q

Let d be defined as in the class notes, i.e. the number of votes counted for B minus the number of votes counted for G. Write down an expression for P(d >= n) as a function of n, avB , avG, p and q. You do not have to simplify this expression.

Lenstra's notes: Exercises 7, 8, 9, 10, 11, 12

Sec. 6.4: 12, 22, 26

Assignment 12 solutions, in pdf (correction posted 12/16, 12:35pm)

Assignment 13, due Dec 5 (posted Nov 29, 6:05am)

In the last homework, you considered an election scenario where independently for each vote

P(the vote is counted for the wrong person) = p

P(the vote is lost and not counted) = q

P(the vote is counted correctly) = 1-p-q

Let margin be defined as in the class notes, i.e. the number of votes counted for B minus the number of votes counted for G. We will use the Central Limit Theorem to evaluate how close the Florida election was, assuming there is small probability q of each vote being lost. In other words, analogous to the class notes, assume

avB = actual votes for B = 2,912,521

avG = actual votes for G = 2,912,522 (i.e. G won by 1 vote)

p = P(vote counted wrong) = .001

q = P(vote lost and not counted) = .01

1-p-q = P(vote counted correctly) = .989

margin = votes counted for B - votes counted for G

Express the margin as
margin = f_B1 + f_B2 + ... + f_B,avB + f_G1 + f_G2 + ... + f_G,avG
where each f_B,i represents how vote i for B was counted:

P(f_B,i = -1, i.e. the vote is counted incorrectly, for G) = .001

P(f_B,i = 0, i.e. the vote is lost and not counted) = .01

P(f_B,i = +1, the vote is counted correctly, for B) = .989

and where each f_G,i represents how vote i for G was counted:

P(f_G,i = +1, i.e. the vote is counted incorrectly, for B) = .001

P(f_G,i = 0, i.e. the vote is lost and not counted) = .01

P(f_G,i = -1, the vote is counted correctly, for G) = .989

Given this setup, your assignment is to

Compute the expectation and standard deviation of each f_B,i and f_G,i

Compute the expectation and standard deviation of the margin

Express the probability that the margin >= 537 in terms of Normal(), the normal distribution function defined in class.

Find an approximate numerical value of the probability that the margin >= 537, by using a table of values of Normal(), or a web site like this one.

Lenstra's notes: Exercises 13, 14, 15, 16, 17, 18, 19, 21

Assignment 13 solutions, in pdf

Assignment 14 (the last!), due Dec 10 (not 12!) (posted Dec 5, 4:30am)

Sec. 7.4: 6, 14, 42

Lenstra's notes: Exercises 23, 25

Assignment 14 solutions, in pdf