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:
  1. Read over the syllabus and complete the syllabus quiz at this link (2 pts)
  2. 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

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

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

  3. \[ \{ n| n = 2^k, k \in \mathbb{N} \} \]

Problem 2 (3 pts)

Write a formal description of the following sets using set notation

  1. The set containing all natural numbers which are an odd power of 2
  2. The set containing all natural numbers which are an even power of 2, excluding 1
  3. 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 S1; that is. \[ S = S_1 \cup \{ a \} \] By the inductive hypothesis, all students in S1 are running the same OS, since |S1| = N. Now remove a different student b from S to obtain different set S2; that is \[ S = S_2 \cup \{ b \}, b \neq a \] By the same reasoning, all of the students in S2 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 S2, and b is using the same OS as everyone in S1. The people overlapping in S1 and S2 must then be using the same operating system. So since the overlap is using the same operating system, and each of S1 and S2 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

  1. Every point is touched by at least one triangle
  2. If two triangles intersect, then they intersect along the entirety of exactly one edge
  3. 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

Hints
  • 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