Homework 1: Discrete Math Practice (23 Points)
Chris Tralie
Due Sunday 9/3/2023 at 11:59PM
Overview / Logistics
The purpose of this problem set is to get you warmed back up on notation and proof techniques that you will use in the course. Upload your solutions to Canvas as a word document, a PDF document, or as a picture of legible handwriting.
Problem 0 (4 pts)
There are 4 easy points to earn here: Read over the syllabus and complete the syllabus quiz at this link (2 pts)
 Sign up for the class Discord and send me answers to the survey questions at this link (2 pts)
Problem 1 (3 pts)
Write a short informal English description of the following sets. Recall that ℕ are the natural numbers and Z are the integers

\[ \{ n n = 2m, m \in \mathbb{N}, \text{ and } n = 7k, k \in \mathbb{N} \} \]

\[ \{ n n = 2k + 1, k \in \mathbb{Z} \} \]

\[ \{ n n = 2^k, k \in \mathbb{N} \} \]
Problem 2 (3 pts)
Write a formal description of the following sets using set notation
 The set containing all natural numbers which are an odd power of 2
 The set containing all natural numbers which are an even power of 2, excluding 1
 The set containing the numbers corresponding to all 300 level CS courses at Ursinus
Problem 3 (3 pts)
Prove that there are at least two people in Philadelphia with the same number of hairs on their head.
HINT: Use the pigeonhole principle. You'll have to look a couple of numbers up as well (cite your sources)
Problem 4 (3 pts)
Given 65 points in an equilateral triangle of side length 1, prove that the distance between the closest two points is at most 1/8 (0.125).
Hint: Look back at lab 6 from CS 174, and use the pigeonhole principle.
For fun
When I do math research, I often write computer programs to help me explore examples to gain some intuition or to see if I can find a counterexample to a conjecture I have. In this case, we might try to space points as far away as we can in a triangle and see how close the closest pair is. To that end, I wrote a little program that samples 10,000 points uniformly from an equilateral triangle using barycentric coordinates, and then does greedy furthest point sampling to find 65 of them that are spaced far apart. Click here to view the code if you're curious. Below is the result of running that experiment 100 times. At least in these experiments, we never exceeded 0.125! (That's not enough to prove it, but it does make us more confident)
Problem 5 (3 pts)
Find the error in the following proof that every student on campus is running the same operating system (if this were actually true, it would be a CS professor's dream, particularly if that OS was Linux...)
Claim: Any group N students at Ursinus are running the same operating system
Proof: By induction on N
Base Case: For N = 1, there's only one person to consider, so no matter what operating system they're running, everyone is running the same operating system.
Inductive Step: Assume the hypothesis is true for N students, and prove that it is true for N+1 students. Take any set S of N+1 students. We show that all of the students in this group are using the same OS. Remove some arbitrary student a from this set to obtain the set S_{1}; that is. \[ S = S_1 \cup \{ a \} \] By the inductive hypothesis, all students in S_{1} are running the same OS, since S_{1} = N. Now remove a different student b from S to obtain different set S_{2}; that is \[ S = S_2 \cup \{ b \}, b \neq a \] By the same reasoning, all of the students in S_{2} are running the same OS. Since a and b are different, this implies that \[ a \in S_2, b \in S_1 \] which, by the inductive hypothesis, means that a is using the same OS as everyone in S_{2}, and b is using the same OS as everyone in S_{1}. The people overlapping in S_{1} and S_{2} must then be using the same operating system. So since the overlap is using the same operating system, and each of S_{1} and S_{2} are using the same operating system, then all of S must be using the same operating system. Proof complete!
Hint: Pick a particular value for N and try drawing out an example that traces through the argument. Can you find an N for which some line of reasoning breaks down?
Problem 6 (4 pts)
In this problem, we will see how three definitions play together in an interesting way
Definition 1: Simple Triangulation
A simple triangulation of a set of at least 3 points in the plane is a set of triangles drawn between the points satisfying the following properties
 Every point is touched by at least one triangle
 If two triangles intersect, then they intersect along the entirety of exactly one edge
 The entire set of triangles is connected, and there are no holes (missing triangles) in the middle
Definition 2: Dual Graph
The dual graph of a simple triangulation is the graph obtained by creating a node for each triangle and with edges between nodes corresponding to triangles that overlap at an edge. The picture below shows the dual graph of the above triangulation superimposed on the triangulation
Definition 3: Convex Point Set
A convex point set is a set of points in the plane whose convex hull is empty. In other words, if I snap a rubber band around the outside of all of the points, there will be no points on the inside. Below is an example of a convex point set
Below is an example of a point set that is not convex
Click here for an interactive demo of convex hulls of points sets.
Your Task
Prove by induction that the dual graph of a simple triangulation of a convex point set is a tree. Below are two examples
 You may use the fact that removing any point from a convex point set yields a convex point set
 You may use the fact that any simple triangulation has an ear, or a triangle along the outside that can be removed, leaving a smaller valid simple triangulation
 Look back in Sipser 0.2 for the definition of a tree as a special case of a graph, and prove that you're satisfying the properties of a tree