Math 55: Discrete Math – Summer 2025

rotating hypercube, projected (Jason Hise)

Professor Francis Su
Section 2, Summer 2025

Meetings: (zoom) MWF 8:00am – 10:30am,
May 28 – July 2
(except Fri Jun 13 and Mon June 22).
Zoom link can be found in an email from me, or on the course Canvas site.

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

My Email: (my last name) at math.hmc.edu

Grutor: Joshua Zhong (jozhong) can be reached at g.hmc.edu

Office Hours: online, with me or Joshua (same Zoom link as class)
Mon-Tue-Wed-Thu-Fri 3pm.

Course Description

This course is an introduction to combinatorics, number theory, and graph theory with an emphasis on creative problem solving and learning to read and write rigorous proofs. Topics include: combinations, permutations, inclusion-exclusion, strong induction, recurrences, Bayes’ theorem, the Euclidean algorithm, unique factorization, modular arithmetic, Euler’s theorem, RSA encryption, planar and Eulerian graphs, and graph coloring. 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 (4th edition), which is available both as a PDF and in an interactive online ebook.

Coursework

Homeworks will be assigned and due each class day at 8am via Gradescope. There will be one midterm (due Jun 13 at 5pm) and one final exam (due Jul 3 at 5pm). Each component (homework, midterm, final) is worth at least 30% of your final grade, with the “best” component worth 40%.

Every assignment has an automatic 24 hour extension–you do not need to formally request this extension. Since this is a summer course, I cannot accommodate homeworks later than this unless you are excused by the Dean.

The learning you are doing in this class takes place in a larger framework of school and life. Sometimes life takes precedence. 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 mathematical progress, not a measure of your mathematical promise. Joy, wonder, and expanding your mind through struggle—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.

AI Policy

(1) Online resources, including artificial intelligence, may be consulted for general learning that is not directly related to assigned problems. However, such resources, especially AI, should be viewed with a healthy skepticism–they can be wrong, or they may rely on ideas we have not covered in this class. Moreover, an over-reliance on them can be detrimental to your learning if the ideas do not “pass through your brain” or give you a deeper understanding.

(2) You should not use AI or other resources to locate solutions for any assigned work. You may check your answers using the ‘Activate’ button in the Levin e-text, but you may not use published solutions for the text. Doing any of these things 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

I will not be recording lectures, but zoom link and lecture notes will be linked from the course Canvas site.

Homeworks

Due on Gradescope each class day at 8am.

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

Read the syllabus above, and my handout on good mathematical writing. And this article if you haven’t seen it before.

Read Levin Sections 3.1-3.4.

Do the following:

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.”

Also, do the following problems from Levin at end of each Section. The numbers refer to what Levin calls “Practice Problems”, unless it is marked with an “a” which refers to “Additional Problems”.

Levin 3.2 ( 2, a2 ) 3.3 ( 3, 7, 8, a2 )

(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 answers. You will need to explain your reasoning well in order to get full credit. Caution: pressing the “Activate” button on a problem may change the problem, especially if you select ‘randomize’. But you should solve the original problem, which you can see by pressing ‘Reset’.)

Submit your homework on Gradescope.

Read Levin Sections 3.5-3.6.

Do the following:

Levin 3.1 ( 7, 10, a1 ) 3.4 ( 4, 8, a1 ) 3.6 ( a3, a9, a13 ).

Note on problem 3.4.8: the Board members are part of the group of businesspeople.

The ebook version of Levin offers interactive opportunities to check answers on many problems. You can use expressions like n! or * (times) or even C(n,k) for (n choose k) and it will evaluate them properly. But be sure to give more explanation than just the answers, you should justify each answer.

Read Levin Sections 3.5-3.6, 3.8.

Do the following:

Levin 3.5 ( 6, 9, a2 ) 3.6 ( a6, a8 ) 3.8 ( 2, 3, 8, a2 )

You may express answers in (n choose k) notation but do not leave answers in multichoose notation.

Read Levin Sections 4.5 and 4.6.

Do the following:

Levin 4.5 ( a6, a7, a9, a11, a12, a14 ) 4.6 ( a6, a8 ) and:

Question A. In just a few sentences, state 2 things you find notable or interesting about induction arguments that you hadn’t appreciated before.

Read Levin Section 4.1 and 4.4.

Do the following:

Levin 4.1 ( 4, a12) 4.4 ( 4, a3, a4, a7 ) and Questions B and C and D 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)$ .

Question D. Sicherman dice are a pair of six-sided dice with non-standard numbers. One die has faces 1, 2, 2, 3, 3, 4, and the other has faces 1, 3, 4, 5, 6, 8. Use generating functions to explain why this pair of dice together behaves the same way as a pair of standard dice (i.e., the number of ways to get the sum N is the same for a pair of Sicherman dice as for a pair of regular dice). Feel free to use a computational tool (like Wolfram Alpha, which can multiply polynomials).

Problem 6A. For integers $a, b$ where $a<0$ , show that the set $A = \{ n \in {\mathbb Z} : a - n b \geq 0 \}$ is not empty by producing a specific integer $n$ that works for each case: $b<0$ and $b > 0$ . (This fact can be used to prove the division algorithm for the case where $a<0$ .)

Problem 6B. Consider the cubes: 1, 8, 27, 64, 125, 216 … When divided by 9, what remainders are possible? Show that a cube of the form $(3m+1)^3$ for an integer $m$ ) must have remainder 1 when divided by 9.

Problem 6C. 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 6D. 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.

Problem 6E. Use the Euclidean algorithm to find the gcd of consecutive Fibonacci Numbers: $\gcd(F_{n}, F_{n+1})$ .

Problem 6F. Prove that if N is a positive integer, make a conjecture about gcd(N, N+1) = 1, then prove it.

Problem 6G. A prime is a positive integer greater than 1 that has no other positive divisors besides itself and 1. 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.

(We use this fact as a starting point for the proof that the factorization is actually unique.)

Problem 6H. The primes less than 15 are 2, 3, 5, 7, 11, 13. Use this list to determine whether the number 221 is prime by:
(a) checking if any prime on the list are divisors of 221, and
(b) explaining why you do not have to check if any other numbers are divisors of 221.
(Hint: if 221 had any factors >= 15, why would have to have a prime factor smaller than 15?)

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

The exam will be available on Gradescope on Thurs June 12. You will have 3 hours to do it (adjusted for any accommodations.) Once you check the exam out, there will be a 6 hour window to download and upload to Gradescope. It’s due Friday at 5pm, but I will allow submissions through Saturday at 5pm.

An 8.5×11 sheet of notes (front and back, prepared by you) will be allowed, but do not use anything else during the exam period (no internet, no AI, etc).

Problem 7A. Find gcd(300, 18) and lcm(300, 18) by first factoring 300 and 18 into primes to find the gcd, and then using the gcd-lcm theorem to find the lcm.

Problem 7B. 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 7C. 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 7D. Without a calculator, determine: (a) 2143 mod 10, (b) 2143 mod 5, (c) 2143 mod 7.

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

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

Problem 7G. 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 7H. Use Wilson’s theorem to help you find the remainder when 99! is divided by 101.

Problem 7I. 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 in integers. Also, 5 is prime.)

Problem 8A. (a) Fill out a multiplication table for numbers mod 6. Which numbers mod 6 have inverses? In which rows do all the numbers 0, 1, 2, … , 5 appear exactly once? Explain what you see.
(b) Fill out a multiplication table for numbers mod 7. Which numbers mod 7 have inverses? In which rows do all the numbers 0, 1, 2, … , 6 appear exactly once? Explain what you see.

Problem 8B. Fill out a table of powers of numbers mod 7, like so:

$\underline{ n | \ n^2 \ n^3 \ n^4 \ n^5 \ n^6 \ n^7}$
$0 |$
$1 |$
$2 |$
$3 |$
$4 |$
$5 |$
$6 |$
Then notice: which numbers mod 7 have some power equal to 1? And explain how one of the columns in your table shows the truth of Fermat’s Theorem.

Problem 8C. Fill out a table of powers of numbers mod 6, like so:

$\underline{ n | \ n^2 \ n^3 \ n^4 \ n^5 \ n^6}$
$0 |$
$1 |$
$2 |$
$3 |$
$4 |$
$5 |$
Then notice: which numbers mod 6 have some power equal to 1? And explain how one (or more) of the columns in your table show the truth of Euler’s Theorem.

Problem 8D. Mod 11, the inverse of 3 is 4. Solve the congruence $3 x \equiv 7 \mod 11$ by multiplying both sides of the congruence by 4 and finding $x$ .

Problem 8E. According to Euler’s theorem, if $(a,N)=1$ , then $a^{\phi(N)} \equiv 1 \mod N$ . This gives us a method for finding the inverse of a number $a$ as $a^{\phi(N)-1}$ . Mod 7, which column in the table of Problem BB gives the inverses of n? Verify that these are, in fact, inverses of the corresponding numbers.

Problem 8F. Look at this table of Euler’s totient function. For which $N$ is $\phi(N)$ an even number? Make a conjecture and prove it.

Problem 8G. The Google search function will find 66^2 mod 119 by typing it in the search box, like this. But it won’t compute 66^77 mod 119, because the power is too large. So compute 66^77 mod 119 by the method discussed in class to compute large powers, using the fact that 77 = 64+8+4+1, because the binary expansion of 77 is 1001101. (Feel free to use Google to compute squares mod 119 when needed.)

Problem 8H. Using N=119, determine $\phi(N)$ and verify that the public key E=5 is relatively prime to $\phi(N)$ . Then determine the corresponding private key D, where 0<=D< $\phi(N)$ , that corresponds to E. (You can find D from E the same way that you can find E from D as discussed in the class notes.)

Problem 8I. Using the N and the public key E in the prior problem, encrypt the message M=19 to get an encrypted message C. What is C? Then use the private key D you found in the prior problem to decrypt C and verify that you get M.

Read: Levin Sections 2.1 and 2.4.

Do the following:

Levin 2.1 ( a3, a5 , a13, a14, a15 ) and 2.4 ( a1, a3. a4, a10 )

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.

Read Levin Sections 2.2 and 2.3

Do the following:

Levin 2.1 ( a7 ) You’ll need to read the section to learn the definition of bipartitite.
Levin 2.2 ( a3, a4, a7, a9 ).
Levin 2.3 ( a2, a3, a5, a11 ).

I’m not a fan of the minimal criminal terminology, but it’s a minimal counterexample, as you can see from reading section 2.2.

Read Levin Section 4.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.

Problem Z. Answer the second “Investigate!” problem in the Section 4.4, about the math department’s 10 classes.

Levin 4.4 ( R1, R2, 3, R4, 6a, 10, 11 ).

The exam will be on Gradescope.

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

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%?