Math 55: Discrete Math – Summer 2023

Professor Francis Su
Section 2, Summer 2023

Meetings: (zoom) MWF 9am – noon, May 22 – June 23
(except Memorial Day May 29 and Juneteenth Jun 19).
Final Exam due Jun 30.

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

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

Grutors: Sarah Williams, Lea Twicken

Office Hours: online (same Zoom link)
Mon-Tue-Wed-Thu-Fri 4pm.
Tue-Thu 11am.
Tue/Thu at 4pm will be hosted by Prof. Su, others hosted by Lea Twicken.

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 (3rd 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 9am via Gradescope. There will be one midterm (due Jun 9) and one final exam (due Jun 30). 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. 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.

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

I will not be recording lectures, but lecture notes will be available.

Homeworks

Due on Gradescope each class day at 9am.

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 Section 1.1.

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

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 here. 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 will not be turning ‘R’ problems 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 ). Note: on problem 10b, the 5 Board members are part of the 20 executives.

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.

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

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

The exam will be available on Gradescope on Wednesday after class. It’s due Friday at 9am, but I will allow submissions through Saturday at noon.

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

Problem AA. (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 BB. 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 CC. 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 DD. 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 EE. 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 FF. 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 GG. 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 HH. 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 II. 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.

Do also:

Levin 4.1 ( R2, 3, R4, 5, 14, 15, 16 )

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.

Read Levin Sections 4.1, 4.5, 4.2.

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 4.5 ( 1, 3, 4, 10 )

Levin 4.1 Read the definition of bipartite in this section, then do ( 7 )

Levin 4.2 ( R2, 3, 4, 7, 9 )

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.

Levin 4.3 ( 2, 3, R4, 5, 11 )

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.

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.