Math 55: Discrete Mathematics

Professor Francis Su
Section 1, Spring 2023
MW 1:15pm in Shan 2440

Course Webpage: https://math.hmc.edu/su/math55/

My Office: Shanahan 3416
My Email: (my last name) at math.hmc.edu
My Drop-In Hours:
Tuesdays 4-5:30pm (on Zoom, for password see course Sakai page)
Also available by appointment.

Academic Excellence:
Peer Tutors and opportunities to work with others in Math 55:
https://www.hmc.edu/learning-programs/academic-excellence/

Graders: Alina Lu, Kanalu Monaco, Ryan Ramos

Course Description

This course is an introduction combinatorics, number theory, and graph theory with an emphasis on creative problem solving and learning to read and write rigorous proofs. My goal is to create an inclusive classroom climate where everyone feels responsible for the participation and the joy that others experience in learning.

Text

There is no required textbook to buy.

We will use portions of Oscar Levin’s Discrete Mathematics: An Open Introduction (3rd edition), which is available both as a pdf and in an interactive online ebook.

Coursework

Homeworks will be assigned and collected weekly, on Wednesdays at 9am. There will be one midterm (week of March 8) and one final exam. Each component (homework, midterm, final) is worth at least 30% of your final grade, with the “best” component worth 40%.

The learning you are doing in this class takes place in a larger framework of school and life. Even if I am excited about teaching and you are excited about learning, work is not the most important thing, and sometimes life can take precedence. I can be somewhat flexible in accommodating requests for homework extensions and absences for other important events. Please make these requests 24 hours in advance, if possible.

Similarly, ‘success’ by whatever measure is not the most important thing in this course either. Every assessment of your work in this class is a measure of progress, not a measure of promise. Joy, wonder, productive struggle, having your mind expanded—these are more important!

Honor Code

The HMC Honor Code applies in all matters of conduct concerning this course. Though cooperation on homework assignments is encouraged, you are expected to write up all your solutions individually to ensure your own understanding. Your solutions should acknowledge the assistance of other people or resources of any kind.

A note about online resources: these can sometimes be helpful for learning, but an over-reliance on them can be detrimental to your learning if the ideas do not “pass through your brain”.

Moreover you should not directly use online resources or other people to find solutions to assigned work in this class. Doing so will be regarded as a violation of the HMC honor code. In addition you will miss the joy of discovering a solution for yourself, which is one of the best feelings in the world.

Lecture Notes and Zoom

Lecture Notes will be posted here (link posted soon). If you cannot come to class, see the course Sakai page for Zoom link and recordings. Keep your camera off and you won’t appear on the Zoom recording. (Also, on Zoom, I will not be able to hear or see the chat.)

Homeworks

Due on Gradescope on Wednesdays at 9am.

Some of you may find LaTeX helpful in typesetting your homework. If so, there is a LaTeX class for homework here.

Read my handout on good mathematical writing. And this article if you haven’t done seen it before.

Read Levin Section 1.1.

Do the following:

Fill out this information card, if you haven’t done so already, so I can get to know you better.

Q1. Based on the handout, why is it important to write in complete sentences?

Q2. What qualities characterize a well-written solution?

Q3. Describe the difference in meaning between these three sentences:
“Let A=B.”
“Therefore A=B.”
“A=B.”

And do the following problems from Levin. (Note that the ebook version offers interactive opportunities to check your answers on some problems, but you will need to do more than just give an answer. You will need to explain your reasoning.)

When you see ‘R’ next to a problem number, that means read the problem and do it to test your understanding, but you do not have to turn an ‘R’ problem in.

Levin 1.1 ( 2, R3, 7, R9, 10, 12, 13, 14).

Read Levin Section 1.2 and Section 1.3

Do the following:

When you see ‘R’ next to a problem number, that means read the problem and do it to test your understanding, but you do not have to turn an ‘R’ problem in.

Levin 1.2 ( R2, 7, 9, R10, 11 )

Levin 1.3 ( R2, 4, 6, 10 )

Levin 1.4 ( 3, 9, 13 )

Cardinality means ‘size’.

Also: remember the ebook version of Levin offers interactive opportunities to check answers on many problems. But be sure to give more explanation than just answers in Levin.

Read Levin Section 1.4, Section 1.5, and Section 1.6.

Do the following:

When you see ‘R’ next to a problem number, that means read the problem and do it to test your understanding, but you do not have to turn an ‘R’ problem in.

Levin 1.4 ( 6, 8 )

Levin 1.5 ( R3, R5, 7, 9, 11 )

Levin 1.6 ( 2, 3, 7, 10 )

You may express answers in “n choose k” notation but do not leave answers in multichoose notation.

Also: remember the ebook version of Levin offers interactive opportunities to check answers on many problems. But be sure to give more explanation than just answers in Levin.

Read Levin Section 2.5.

Do the following:

When you see ‘R’ next to a problem number, that means read the problem and do it to test your understanding, but you do not have to turn an ‘R’ problem in.

Levi n 2.5 ( R5, 7, 9, 11, 12, 14, 22, 24, 29 ) and Question A below.

Question A. In problem #6, look at the Solution. Can you modify the argument to show that the statement holds for n>=3? Why or why not?

And yes, problems 12 and 14 have solutions, but do not look at the solution until you have wrestled with the problem.

Read Levin Section 2.1 and 2.4.

Do the following:

When you see ‘R’ next to a problem number, that means read the problem and do it to test your understanding, but you do not have to turn an ‘R’ problem in.

Levin 2.1 (R4, R9, 13, 15, 16 ), Levin 2.4 ( R1, 4, 5, 8, R10, 11 ) and Questions B and C below.

Question B. Recall the field goals and touchdown problem from the last problem set (2.5.9).

a. Let $a_n =$ the number of ways to get $n$ points using just 3-point field goals. Explain why this sequence has generating function $A(x) = 1+ x^3 + x^6 + x^9 + \cdots$ and then explain why this expression is equal to $1/(1-x^3)$ .

b. Similarly, let $b_n =$ the number of ways to get $n$ points using 7-point touchdowns. Explain why this sequence has generating function $B(x)=1/(1-x^7)$ .

c. Let $c_n =$ the number of ways to get $n$ points using both field goals and touchdowns. This sequence has generating function $C(x)=A(x)B(x)$ . Use this Wolfram Alpha link to compute its power series. Under “Series Expansion at x=0” look for the button “More terms” and press it 3 times to see more of the series. Explain why the series is missing a term for $x^{11}$ and why the series has a coefficient of 2 for $x^{21}$ .

Question C. Write out the generating function $K(x)$ for the Fibonacci Sequence: $F_0=0, F_1=1$ , and $F_n=F_{n-1}+F_{n-2}$ . Then show $K(x) = x/(1-x-x^2)$ .

Do the following problems. There is no textbook for these problems, but the lecture notes are available on the Sakai course page.

Question D. A fair coin, when flipped, has equal probability of landing heads (H) or tails (T). Suppose a fair coin is flipped 3 times, and you observe the resulting sequence of heads and tails. (Thus the order is important.)
(a) How many outcomes are in the sample space S? Are they equally likely?
(b) Let E be the event consisting of all outcomes where the number of heads is exactly 2. Explicitly write out the set E as a subset of outcomes in S.
(c) What is the probability of E?

Question E. In a deck of 52 cards, half the cards are red and half the cards are black. Suppose you draw 2 cards, without replacement, from the deck. Is it more likely that those cards will have the same color, or more likely that they will have different colors? Determine the probabilities of each.

Question F. Let $A$ be the complement of the set $B$ in the sample space $S$ . Thus $A$ and $B$ are disjoint sets whose union is $S$ . Use the axioms of probability (see lecture notes on Probability) to explain why $P(A) = 1 - P(B)$ .

Question G. Suppose that on a given day the probability that it rains is 0.4. The probability that the weather is warm is 0.08. The probability that it rains AND that the weather is warm is 0.04. What is the probability that the weather is warm given that it rains? What is the probability that it rains given that the weather is warm?

Question H. Use the definition of conditional probability to show that $P(A \cap B \cap C) = P(A) \ P(B | A) \ P(C | A \cap B)$ .

Question I. A fair die has numbers 1-6 on the sides, equally likely to show up. Suppose you roll 2 fair dice. Let A be the event that the first die shows the number 1. Let B be the event that the TOTAL of both dice numbers is 2. Are A and B independent events? Are A and B disjoint events? Explain.

Question J. Use the Law of Total Probability to determine the probability that a Mudd student has a car. Suppose you know that the probabilities of a Mudd frosh, sophomore, junior, senior having a car is (0, 0.2, 0.5, 0.8 respectively, and there are 225 frosh, 200 sophomores, 230 juniors, and 210 seniors.

Question K. Suppose 1 in 12 Americans are from Texas, and 2/3 of Texans are Republicans. If 1/2 of Americans are Republicans, what is the probability that a randomly chosen Republican in the U.S. is from Texas?

Question L. Suppose you have a test for a rare disease. The false positive rate of the test is the probability that a person tests positive if they don’t have the disease. The true positive rate (also called the sensitivity) of a test is the probability that a person tests positive if they do have the disease. Suppose that 1 out of 10,000 people have the disease, and the true positive rate is 99% (or 0.99). How small does the false positive rate have to be in order for the probability that a test-positive person has the disease to be at least 80%?

If you can’t complete it by Mar 8, turn it in on Gradescope by Mar 10 at 11pm.

This homework is a shorter than usual due to Spring Break.

Problem M. Prove the Integer Combination Theorem that we discussed in class: If d|a and d|b, then for any integers x and y, show that d|(ax+by).

Hint: you’ll want to appeal to the definition of “divides”.

Problem N. Show that every number N > 1 can be expressed as a (finite) product of primes.

Hint: Do this by strong induction on N. Thus your inductive hypothesis will be: “Assume that this can be done for all N less than or equal to K.” Then in the inductive step, you’ll want to show that it can be done for N=K+1.

(Recall that we used this fact as a starting point for the proof on Wed 3/8 that the factorization is actually unique.)

Problem O. How many divisors does a prime power $p^k$ have? How many divisors does a product of $k$ distinct primes (like $p_1 p_2 \cdots p_k$ ) have?

Problem P. (a) Find gcd(300, 18) using the Euclidean algorithm. Then find integers x and y such that 300x + 18y = gcd(300, 18) using the method discussed in class.
(b) Find gcd(300, 18) and lcm(300, 18) by first factoring 300 and 18 into primes, and then using the gcd-lcm theorem.

Problem Q. The primes less than 20 are 2, 3, 5, 7, 11, 13, 17, 19. Determine whether the number 221 is prime. (You might use the given list of primes, since if 143 were composite, it should have a smaller factor that is prime.)

Problem R. Show that if a number $N$ is composite, then it must have a prime factor less than or equal to $\sqrt{N}$ . (Hint: if the conclusion were false, show that leads to a contradiction.)

Problem S. How many prime numbers are there between 1 and 100, inclusive? Between 1001 and 1100, inclusive? Between 10001 and 10100 inclusive? [Feel free to consult a list of primes.] How do the actual counts compare to the number of primes predicted by the Prime Number Theorem? Recall that the Prime Number Theorem says that the function $\pi(N)$ , the number of primes less than or equal to $N$ , is approximately $N/\ln(N)$ .

Problem T. Without a calculator, determine: (a) 2143 mod 10, (b) 2143 mod 5, (c) 2143 mod 7.

Problem U. Without a calculator, determine $2143^{2143} \mod 7$ .

Problem V. Without a calculator, determine the last digit of $2143^{2143}$ .

Problem W. You have 1205 crates of soda cans. Each crate has 16 soda cans in it. You have to repackage all the soda cans into packages of 12 cans each. After making as many complete packages as possible, how many soda cans will be left over? Solve this problem without a calculator, and make your life easy using (mod 12) arithmetic.

Problem X. Use Wilson’s theorem to help you find the remainder when 99! is divided by 101.

Problem Y. Show that the equation $x^4 + 1 = 3 y^4$ can never be solved in integers x and y.
(Hint: if the equation cannot be solved in integers mod 5, it cannot be solved at all. Also, 5 is prime.)

Below this line, all homeworks are TENTATIVE. This means they are likely to be assigned, but there is no guarantee that they will until you see them moved above.