Problem Set 4

Due Friday, July 26 at 5:30 pm Pacific

Solutions are available!

🔑 Solutions


This problem set – the last one purely on discrete mathematics – is designed as a cumulative review of the topics we’ve covered so far and a proving ground to try out your newfound skills with mathematical induction. The problems here span all sorts of topics and we hope that it serves as a fitting coda to our whirlwind tour of discrete math!

We recommend that you read the Guide to Induction before starting this problem set. It contains a lot of useful advice about how to approach problems inductively, how to structure inductive proofs, and how to not fall into common inductive traps. Additionally, before submitting, be sure to read over the Induction Proofwriting Checklist for a list of specific things to watch for in your solutions before submitting.

As a note on this problem set – normally, you're welcome to use any proof technique you'd like to prove results in this course. On this problem set, we've specifically asked on some problems that you prove a result inductively. For those problems, you should prove those results using induction or complete induction, even if there is another way to prove the result. (If you'd like to use induction in conjunction with other techniques like proof by contradiction or proof by contrapositive, that's perfectly fine.)

Good luck, and have fun!

Grading

Since this problem set comes due on the same day as our midterm exam, we are enacting a special grading policy for this problem set only.

  • The due date for this assignment is still Friday 7/28 at 4PM PT.
  • Submitting by the deadline earns a small "on-time" bonus. We will add the bonus points onto your assignment score (approximately 5% of the total points available for this assignment).
  • There is a penalty-free 48-hour "grace period" for late submission. The grace period allows you to submit the assignment after the deadline, with no impact on your grade. Therefore, the latest you can submit within the grace period is Sunday 7/30 at 4PM PT.
  • Problem Set 5 will still be released according to our normal assignment cadence.

$\LaTeX$ Template

If you would like to type your solutions in $\LaTeX$, you may want to download this template file where you can place your answers:

🖋 PS4 $\LaTeX$ Template

This problem set does not have a coding component.

Problem One: Friends, Strangers, Enemies, and Hats

In lecture, we proved the Theorem on Friends and Strangers, which says that if you have a group of six people where, for each pair of people, those people either know one another (they’re friends) or they don’t know each other (they’re strangers), you can always find three mutual friends or three mutual strangers. Here, “three mutual friends” means “three people where each two of them are friends,” and “three mutual strangers” means “three people where each two of them are strangers.”

This is one of many different results about what must happen when you get a sufficiently large number of people together. The rest of this problem explores some other results in that vein.

  1. There’s a party with 36 attendees. Each person is wearing a hat, and there are seven possible hat colors: aureolin, bole, chartreuse, drab, ecru, fulvous, and gamboge. (Yes, those are all colors.) As in the Theorem on Friends and Strangers, for any pair of people at the party, either the pair are friends or the pair are strangers.

    Prove that you can always find three mutual friends all wearing the same color hat or three mutual strangers all wearing the same color hat.

    In the course of solving this problem, you will likely need to make use of the Theorem on Friends and Strangers from lecture. If you do, you should just cite the result from lecture rather than reproving it from scratch. For example, you could say something like "by the Theorem on Friends and Strangers, we know that … ." As usual, though, don't repeat the theorem in the abstract. Instead, apply it to some specific scenario to state some new fact you learn as a result.

  1. There’s a party with 17 attendees. This time, things are a bit more complicated. For each pair of people at the party, either those people are strangers, those people are friends, or those people are enemies. Fortunately, none of them are wearing hats. 😃

    Prove that you can always find three mutual friends, or three mutual strangers, or three mutual enemies.

Find problems like these interesting? Take Math 107 (Graph Theory) or Math 108 (Combinatorics)!

Problem Two: Recurrence Relations

A recurrence relation is a way of defining an infinitely long sequence (usually, a sequence of numbers). A recurrence relation specifies the value of the first term or terms of the sequence, then defines the remaining entries from the previous terms. For example, here’s a simple recurrence relation:

\[a_0 = 1 \qquad a_{n+1} = 2a_n\]

The first terms of this sequence are given as follows:

  • $a_0 = 1$, since that’s what the first rule says.
  • $a_1 = 2$, since the second rule says that $a_1 = 2a_0 = 2 \cdot 1 = 2\text.$
  • $a_2 = 4$, since the second rule says that $a_2 = 2a_1 = 2 \cdot 2 = 4\text.$
  • $a_3 = 8$, since the second rule says that $a_3 = 2a_2 = 2 \cdot 4 = 8\text.$

Extending further, this sequence starts off with the numbers

\[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, \dots,\]

which all happen to be powers of two. It turns out that this isn't a coincidence – this recurrence relation perfectly describes the powers of two.

Fill in the blanks below to complete the proof by induction.

Theorem: For all natural numbers $n$, we have $a_n = 2^n$.

Proof: Let $P(n)$ be the statement "$a_n = 2^n$." We will prove by induction that $P(n)$ holds for all $n \in \naturals$, from which the theorem follows.

As our base case, we prove $P(\blank)$, that $\blank$. To see this, $\blank$.

For our inductive step, assume for some arbitrary $k \in \naturals$ that $P(k)$ is true, meaning that $\blank$. We need to show $P(\blank)$, meaning that $\blank$. To see this, note that

\[\begin{aligned} a_{k+1} &= \blank \\ &= \blank && \text{(by our IH)} \\ &= \blank \text. \end{aligned}\]

Therefore, we see that $\blank$, so $P(\blank)$ is true, completing the induction. $\qed$

The relative sizes of the blanks here do not necessarily indicate how much you need to write in each spot.

In case you’re wondering what you’re asked to prove here, you can think of this recurrence relation as a mathematical way of writing out this recursive function:

int a(int n) {
    if (n == 0) return 1;
    return 2 * a(n - 1);
}

For any $n \in \naturals$, you can compute a(n) by just running this code, and after doing some computation it will return the value of $a_n$. What we’re asking you to do is the mathematical equivalent of showing that the value returned by a(n) is always $2^n$. While it might help to think about things in terms of this analogy, your proof should not reference this code and should just use the definitions given in the problem statement.

Taking a recurrence relation like the relation $a_n$ here and finding a simple, non-recursive expression for it is called solving the recurrence. It's common in theoretical CS to need to solve recurrences. For example, when determining the efficiency of a recursive algorithm, you might first start by writing a recurrence relation for its runtime, then solve the recurrence to get a simpler, direct way of calculating its efficiency. Take CS161 to learn how to do this!

Problem Three: Stacking Cans

On a recent trip to grocery store, I saw a bunch of cans stacked up in a pyramid like the one shown here. Each layer in the pyramid was made from a hexagon of cans, with each hexagon slightly bigger than the hexagon below it.

A pyramid made of cans arranged in hexagons. The top layer is a single can. The second layer is seven cans forming a hexagon (one can in the center, six cans surrounding that can and touching), or, equivalently, a hexagon made of two cans per side surrounding a single hexagon. The third layer is nineteen cans forming a hexagon with three cans on a side, with the middle filled by a hexagon two cans to a side. The fourth layer is 37 cans arranged into hexagon with four cans to a side, filled with a hexagon three cans to a side

I went home to try making something like this from the cans in my pantry and quickly figured out that I didn't have enough cans to do so. Turns out, you need a lot of cans to make a pyramid like this! In this question, you'll figure out just how many cans are required.

The first step in this process is to figure out how many cans are in each hexagon. Here are cross-sectional views of the hexagons from the pyramid:

Each layer from the above pyramid spread out to make the cans in the layers more visible. It becomes clear that to go from one layer to the next, we surround the previous layer in a hexagonal perimeter of cans

Notice that in moving from the first hexagon to the second we've surrounded the center can in six cans. In moving from the second hexagon to the third we've surrounded the seven previous cans with twelve new cans. And in moving from the third hexagon to the fourth we've surrounded the previous nineteen cans with eighteen new cans. And more generally, it seems like we go from one hexagon to the next by surrounding the previous hexagon with a number of cans equal to the next multiple of six. That lets us write a recurrence relation for how many cans are in the $n$th hexagon:

\[h_1 = 1 \qquad h_{n+1} = h_n + 6n \text.\]

Pause for a minute to make sure you see why this is.

  1. Prove by induction that $h_n = 3n(n - 1) + 1$ for all natural numbers $n \ge 1 \text.$

    As in Problem Two, you begin here with the recursive definition of $h$ given above, then need to show that the terms of the series are also given by the simpler formula $3n(n - 1) + 1$.

Now that we know how many cans are in each hexagon, we can start working out how many cans it takes to make a pyramid with $n$ layers.

  1. Fill in the following blanks. No justification is required.

    • A 0-layer tower has $\blank$ cans in it.
    • A 1-layer tower has $1$ can in it.
    • A 2-layer tower has $8$ cans in it.
    • A 3-layer tower has $\blank$ cans in it.
    • A 4-layer tower has $\blank$ cans in it.
    • A 5-layer tower has $\blank$ cans in it.
    • A 6-layer tower has $\blank$ cans in it.
    • A 7-layer tower has $\blank$ cans in it.
    • A 8-layer tower has $\blank$ cans in it.
    • A 9-layer tower has $\blank$ cans in it.
    • A 10-layer tower has $\blank$ cans in it.

  1. Fill in the following blank with a simple mathematical expression (e.g. $n^2 + 19n + 1$, $\sqrt{n^2 + 5}$, $\floor{\frac{n}{2}}^2$, etc, but not a recurrence relation like $t_{n+1} = t_n + h_{n+1}$). No justification is required.

    An $n$-layer tower has $\blank$ cans in it.

  1. Prove by induction on $n$ that your formula from part (iii) holds for all natural numbers $n$.

    We've asked you to prove this is true for all natural numbers $n$, including when $n = 0\text.$

Your answer to part (iv) explains why I wasn't able to build any reasonable pyramid from the cans I have at home. It's worth taking a minute or two to ponder how much it would cost to build a pyramid twenty layers deep!

A purely optional but very rewarding question to ponder: the formula you proved correct in part (iv) suggests there's a completely different way to arrange the cans in the pyramid into an appealing geometrical shape. What is that other shape? Can you find a way to explain why that shape - which superficially has nothing to do with hexagons - relates back to hexagonal layers?

Problem Four: The Circle Game

You have a circle with $2n$ arbitrarily-chosen points on its circumference for some natural number $n \ge 0$. Of the $2n$ points, $n$ are labeled $+1$, and the remaining $n$ are labeled $-1$. One sample circle with eight points, of which four are labeled $+1$ and four are labeled $-1$, is shown below.

A circle with eight points arranged clockwise: A, B, C, D, E, F, G, and H. Point A is labeled +1. Point B is labeled +1. Point C is labeled -1. Point D is labeled -1. Point E is labeled -1. Point F is labeled +1. Point G is labeled -1. Point H is labeled +1.

Here's a game you can play. Pick some position on the circle as your starting point - it can either be one of the points with a number on it, or an unnumbered point that just happens to be on the circle. Now, move clockwise around the circle. You lose the game if at any point on you pass through more $-1$ points than $+1$ points. You win the game if you get all the way back to your starting point without losing. For example, if you start at point $A$, the game would go like this:

  • Start at $A$: $+1$.
  • Pass through $B$: $+2$.
  • Pass through $C$: $+1$.
  • Pass through $D$: $0$.
  • Pass through $E$: $-1$. (You lose.)

If you started at point $G$, the game would go like this:

  • Start at $G$: $-1$ (You lose.)

However, if you started at point $F$, the game would go like this:

  • Start at $F$: $+1$.
  • Pass through $G$: $0$.
  • Pass through $H$: $+1$.
  • Pass through $A$: $+2$.
  • Pass through $B$: $+3$.
  • Pass through $C$: $+2$.
  • Pass through $D$: $+1$.
  • Pass through $E$: $+0$.
  • Return to $F$. (You win!)

There’s a remarkable theorem about this game:

Theorem: For all natural numbers, $n$, for all circles with $n$ points labeled $+1$ and $n$ points labeled $-1$ on its boundary, there exists a starting position on the circle from which you can start and win the circle game.

We’re going to ask you to prove this using a proof by induction with this predicate $P(n)$:

$P(n)$ is the predicate “for all circles with $n$ points labeled $+1$ and $n$ points labeled $-1$ on its boundary, there exists a starting position on the circle from which you can start and win the circle game.”

Before proceeding, let’s confirm you see the general structure of the proof.

  1. In our inductive step, our "want to show" is $P(k + 1)$. Write out $P(k + 1)$. Whether this is a universally-quantified statement or an existentially-quantified statement will guide what we do next. In this case, our $P(k + 1)$ is universally quantified. Based on that, what is the first thing we're going to want to do to show our "want to show"? Tell us precisely what thing you should arbitrarily pick.

    There are multiple quantifiers in $P(n)$. For now, we only care about the first one, which is universal.

  1. Prove by induction that $P(n)$ is true for all $n \in \naturals$.

Problem Five: Regular Graphs

A graph $G = (V, E)$ is called $d$-regular if every node in $G$ has degree exactly $d$. (As a reminder, the degree of a node $v$ is the number of edges that have $v$ as an endpoint, or, equivalently, the number of nodes that $v$ is adjacent to.)

For example, here's a 3-regular graph with 6 nodes and a 4-regular graph with 7 nodes:

A 3-regular graph with 6 nodes is formed as follows. The nodes are A, B, C, D, E, and F. Node A is adjacent to nodes B, E, and F. Node B is adjacent to nodes A, C, and D. Node C is adjacent to nodes B, D, and F. Node D is adjacent to nodes B, C, and E. Node E is adjacent to nodes A, D, and F. Node F is adjacent to nodes A, C, and E. A 4-regular graph with 7 nodes is formed as follows. The nodes are A, B, C, D, E, F, and G. Node A is adjacent to nodes C, D, E, and F. Node B is adjacent to nodes D, E, F, and G. Node C is adjacent to nodes A, E, F, and G. Node D is adjacent to ndoes A, B, F, and G. Node E is adjacent to nodes A, B, C, and G. Node F is adjacent to nodes A, B, C, and D. Node G is adjacent to nodes B, C, D, and E.

Prove by induction that for all natural numbers $n$ there exists an $n$-regular graph containing exactly $2^n$ nodes.

Is this a problem where you'll "induct up," or a problem where you'll "induct down?"

As a hint, moving from $2^k$ to $2^{k+1}$ doubles the number of nodes in the graph, and moving from $2^{k+1}$ to $2^k$ halves the number of nodes in the graph. If you think this is an "induct up" problem, try finding a natural way to "double" a graph. If you think this is an "induct down" problem, try finding a natural way to "halve" a graph.

Regular graphs often make appearances in combinatorics and theoretical computer science. Graphs with the specific property you're exploring in this problem - where there are a huge number of nodes of modest degree - have applications in parallel computing, network design, and error-correcting codes. Take CS149 (Parallel Computing) or CS250 (Algebraic Error-Correcting Codes) to learn more!

Problem Six: It’ll All Even Out

Our very first proof by induction was the proof that for any natural number $n$, we have that

\[2^0 + 2^1 + 2^2 + \dots + 2^{n-1} = 2^n - 1\text.\]

This result is still true for the case where $n = 0$, since in that case the sum on the left-hand side of the equation is the empty sum of zero numbers, which is by definition equal to zero. It’s also true for the case where $n = 1$; in that case, the sum on the left-hand side of the equality just has a single term in it ($2^0$) and the right-hand side has the same value.

Below is a proof by complete induction of an incorrect statement about sums of real numbers.

⚠ (Incorrect!) ⚠ Theorem: Let $x_1, x_2, x_3, \dots, x_n$ be any $n$ real numbers. Then $x_1 + x_2 + \dots + x_n$ is even.

⚠ (Incorrect!) ⚠ Proof: Let $P(n)$ be the statement “for any $n$ real numbers $x_1, x_2, \dots, x_n\text,$ the sum $x_1 + x_2 + \dots + x_n$ is even.” We will prove by complete induction that $P(n)$ holds for all $n \in \naturals$, from which the theorem follows.

As a base case, we prove $P(0)$, that the sum of any $0$ real numbers is even. The sum of any zero numbers is the empty sum and is by definition equal to $0$, which is even. Thus $P(0)$ holds.

For our inductive step, assume for some arbitrary $k \in \naturals$ that $P(0), \dots, \text{ and } P(k)$ are true. We will prove that $P(k+1)$ is true. To do so, let $x_1, x_2, \dots, x_k, \text{ and } x_{k+1}$ be arbitrary real numbers and consider the sum

\[x_1 + x_2 + \dots + x_k + x_{k+1}\text.\]

We can group the first $k$ terms and the last term independently to see that

\[x_1 + x_2 + \dots + x_k + x_{k+1} = (x_1 + x_2 + \dots + x_k) + x_{k+1}\text.\]

Now, consider the sum $x_1 + x_2 + \dots + x_k$ of the first $k$ terms. This is the sum of $k$ real numbers, so by our inductive hypothesis that $P(k)$ is true we know that this sum must be even. Similarly, consider the sum $x_{k+1}$ consisting of just the single term $x_{k+1}$. By our inductive hypothesis that $P(1)$ is true, we know that this sum must be even.

Overall, we have shown that $x_1 + x_2 + \dots + x_k + x_{k+1}$ can be written as the sum of two even numbers (namely, $x_1 + x_2 + \dots + x_k$ and $x_{k+1}$), so $x_1 + x_2 + \dots + x_k + x_{k+1}$ is even. Thus $P(k+1)$ is true, completing the induction. $\qed$

Of course, this theorem isn’t true, so the proof must be wrong. But what specifically did it do wrong?

  1. The proof defines a predicate $P(n)$, then uses complete induction to prove $P(n)$ holds for all $n \in \naturals$. Is $P(n)$ actually a predicate? Does it pass the Induction Proofwriting Checklist? Is it actually the case that, if $P(n)$ is true for all $n \in \naturals$, then the theorem in question is true? If any of your answers are “no,” explain why, pointing out, specifically, what the proof does wrong.

  1. Is $P(0)$ true? Is the base case of this proof written correctly? If so, just say “yes, it’s correct.” If not, point out a specific claim it makes that’s incorrect and explain why it’s incorrect.

    We aren’t looking for “sins of omission” here in the sense of “the proof should have also done $X$ in addition to what it already did.” Rather, we’re looking for “sins of commission” in sense of “the proof does $X$, and $X$ is incorrect.”

  1. Is $P(1)$ true? Is the inductive step of this proof written correctly? If so, just say “yes, it’s correct.” If not, point out a specific claim it makes that’s incorrect and explain why it’s incorrect.

Optional Fun Problem: Egyptian Fractions

Leonardo Fibonacci, an eleventh-century Italian mathematician, is credited with introducing Hindu-Arabic numerals (the number system we use today) to Europe in his book Liber Abaci. The book Liber Abaci is also the source of the Fibonacci sequence (a sequence that begins 0, 1 and where each successive term is the sum of the two previous terms).

Relevant for this problem, Liber Abaci also described a method of writing out fractions called Egyptian fractions, which has been employed since ancient times; the Rhind Mathematical Papyrus, composed about 3,500 years ago in Thebes, includes several tables of fractions written out this way.

An Egyptian fraction is a sum of distinct fractions whose numerators are all 1 (these fractions are called unit fractions). For example, here are some sample Egyptian fraction representations:

\[\begin{array}{c} \frac{2}{3} = \frac{1}{2} + \frac{1}{6} \\ \frac{2}{15} = \frac{1}{10} + \frac{1}{30} \\ \frac{7}{15} = \frac{1}{3} + \frac{1}{8} + \frac{1}{120} \\ \frac{2}{85} = \frac{1}{51} + \frac{1}{255} \end{array}\]

Egyptian fractions are useful for divvying up objects fairly. For example, suppose you have two cakes to distribute to fifteen people – that is, everyone should get a $\frac{2}{15}$ fraction of those cakes. Begin by slicing each cake into tenths and giving each person one ($\frac{1}{10}$). Now, take the remaining tenths you haven’t distributed and cut them into thirds, giving thirtieths of the original cake. Each person then takes one of those ($\frac{1}{30}$). Because $\frac{1}{10} + \frac{1}{30} = \frac{2}{15}$, everyone gets their fair share. Pretty cool, isn’t it?

It's not immediately obvious that every fraction between 0 and 1 can be written this way, but, surprisingly, that is indeed the case. One way of finding an Egyptian fraction representation of a number is to use a greedy algorithm that works by finding the largest unit fraction at any point that can be subtracted out from the rational number. For example, to compute an Egyptian fraction representation for $\frac{42}{137}$, we would start off by noting that $\frac{1}{4}$ is the largest unit fraction less than $\frac{42}{137}$. We then say that

\[\frac{42}{137} = \frac{1}{4} + (\frac{42}{137} - \frac{1}{4}) = \frac{1}{4} + \frac{31}{548} \text.\]

We then repeat this process by finding the largest unit fraction less than $\frac{31}{548}$ and subtracting it out. This number is $\frac{1}{18}$, so we get

\[\frac{42}{137} = \frac{1}{4} + \frac{1}{18} + (\frac{31}{548} - \frac{1}{18}) = \frac{1}{4} + \frac{1}{18} + \frac{5}{4,932} \text.\]

The largest unit fraction we can subtract from $\frac{5}{4932}$ is $\frac{1}{987}$:

\[\frac{42}{137} = \frac{1}{4} + \frac{1}{18} + \frac{1}{987} (\frac{5}{4,932} - \frac{1}{987}) = \frac{1}{4} + \frac{1}{18} + \frac{1}{987} + \frac{1}{1,622,628} \text.\]

And at this point we're done, because the leftover fraction is itself a unit fraction.

Prove that the greedy algorithm for Egyptian fractions always terminates for any rational number $r$ in the range $0 \lt r \lt 1$ and always produces a valid Egyptian fraction. (A rational number is a real number that can be written as $r = \frac{p}{q}$ for some integers $p$ and $q$ where $q \ne 0$.) That is, the sum of the unit fractions should be the original number, there should only be finitely many fractions, and no unit fraction should be repeated. This shows that every rational number in the range $0 \lt r \lt 1$ has at least one Egyptian fraction representation.