Problem Set 1

Due Friday, April 12 at 3:00 pm Pacific

Here we are – the first problem set of the quarter! This problem set is designed to give you practice writing proofs on a variety of different topics. We hope that this problem set gives you a sense of what proof-based mathematics is like and helps solidify your understanding of set theory.

Before you start this problem set, please do the following:

• Review the Guide to Proofs for information about common proofwriting techniques.
• Review the Guide to Partners for information about how to work effectively in a pair.
• Review the Guide to Office Hours for information about how office hours work.
• Review the Guide to $\LaTeX$ to learn how to typeset your solutions with $\LaTeX$.
• Review the Proofwriting Checklist for a detailed set of criteria you should apply to your proofs before submitting them. We will be running this same checklist on your proofs when grading, so please be sure to look over it before submitting!
• Review the Guide to $\in$ and $\subseteq$ to make sure you understand the distinction between these terms.

As always, please feel free to call into office hours or post on EdStem if you have any questions. We're happy to help out.

Good luck, and have fun!

Starter Files

You will need to download and set up this Qt Creator project to complete the first two problems on this problem set:

📦 PS1 Starter Files

Unpack the files somewhere convenient and open up the bundled project.

As a reminder, you are required to type your solutions to this problem set. If you would like to type your solutions in $\LaTeX$, you may want to download this template file where you can place your answers:

🖋 PS1 $\LaTeX$ Template

You are also free to use Microsoft Word, Google Docs, etc. to type up your solutions.

Problem One: Much Ado About Nothing

It can take a bit of practice to get used to the empty set. This problem will ask you to think about a few different sets related to $\emptyset$.

Answer each part of this question by editing the file MuchAdoAboutNothing.sets in the res/ directory of the starter files. There’s information in the top of each of the files about how to represent sets; most importantly, note that to write out the empty set, you should write {} rather than using the empty-set symbol. For example, the set $\Set{\emptyset}$ would be written as { { } }.

1. Give a set equal to $\emptyset \cup \Set{\emptyset}$.

2. Give a set equal to $\emptyset \cap \Set{\emptyset}$.

3. Give a set equal to $\Set{\emptyset} \cup \Set{\Set{\emptyset}}$.

4. Give a set equal to $\Set{\emptyset} \cap \Set{\Set{\emptyset}}$.

5. Give a set equal to $\wp(\wp(\emptyset))$.

6. Give a set equal to $\wp(\wp(\wp(\emptyset)))$.

The starter code contains a driver program you can use to see the contents of your files and run tests to check your answers. Submit your answers through GradeScope under “Coding Problems for Problem Set One” by uploading your edited files. You’re welcome to submit as many times as you’d like; we’ll count as your grade the last version of the uploaded files.

Problem Two: Set Theory in C++

The C++ standard library contains a type called std::set that represents a set of elements, all of which must be of the same type. For example, the type std::set<int> represents a set of integers, the type std::set<std::string> represents a set of strings, and std::set<std::set<int>> is a type representing a set of sets of integers.

There are all sorts of operations you can perform on std::sets. For example, here’s how you iterate over all the elements of a set:

std::set<T> mySet;
for (T elem: mySet) {
    /* … do something with the current element elem … */
}

(Don't worry if you see a warning message when using this style of loop; it's perfectly fine for our purposes.)

Here’s how you check whether a particular value is an element of a set:

if (mySet.count(value)) {
    /* … value ∈ mySet … */
} else {
    /* … value ∉ mySet … */
}

And, finally, here’s how you can get the cardinality of a set:

size_t size = mySet.size();

Here, the size_t type is a type representing a natural number, since sets can’t have negative size. (The folks who designed the C++ standard libraries had a strong discrete math background.)

One of the major differences between the sets we’ve talked about in CS103 and the std::set type is that in discrete mathematics, sets can contain anything – numbers, philosophies, recipes, other sets, etc. – but in C++ all objects in a set must have the same type. For the purposes of this problem, we’ve created a custom C++ type called Object. Variables of type Object can represent just about anything, so a std::set<Object> represents something pretty similar to the sets we’ve been studying so far.

Some Objects are actually just std::sets in disguise. If you have an Object, you can test whether it’s actually a set by using this provided helper function:

bool isSet(Object o);

This takes in an Object, then returns true if that Object is actually a set and false otherwise. If you have an Object that really is a set, you can convert it to a set by using this helper function:

std::set<Object> asSet(Object o);

This function takes in an Object that you know happens to be a set, then returns the std::set<Object> that it actually is.

For example, suppose you have an Object that you know is really the set $\Set{1, 2, 3, 4}$. You could iterate over it using this code:

Object reallyASet = /* … */;
for (Object x: asSet(reallyASet)) {
    /* … do something with x … */
}

In this problem, we’d like you to demonstrate your understanding of sets and set theory by coding up a number of functions in C++ that operate on sets. In doing so, we hope that you’ll solidify your grasp of the distinctions between related concepts in set theory, such as the the $\in$ and $\subseteq$ relations and power sets.

Open the file SetTheory.cpp from the starter files. There, you’ll find a bunch of stubs of functions that you’ll need to implement. The provided starter code contains a test harness you can use to try out your functions. You won’t need to modify any of the other C++ files bundled with the starter code.

As with Problem One, you’ll submit the code that you write through GradeScope separately from the rest of the problems on this problem set. The GradeScope autograder will get back to you with feedback about how you’re doing on this problem, and you’re welcome to submit as many times as you’d like.

1. Implement a function

   bool isElementOf(Object S, Object T);
   

   that takes as input two Objects $S$ and $T$, then returns whether $S \in T$.

   $S$ and $T$ might not be sets; you’ll need to use the isSet and asSet functions appropriately.

2. Implement a function

   bool isSubsetOf(Object S, Object T);
   

   that takes as input an object $S$ and an object $T$, then returns whether $S \subseteq T$.

   $S$ and $T$ might not be sets; use the isSet predicate to check whether the appropriate arguments are sets and asSet to get a view of them as sets.

3. Implement a function

   bool areDisjointSets(Object S, Object T);
   

   that takes as input two objects $S$ and $T$, then returns whether $S$ and $T$ are sets where $S \cap T = \emptyset$. (Two sets with this property are called disjoint.) The input parameters $S$ and $T$ may or may not be sets, and if they aren’t, your function should return false.

4. Implement a function

   bool isSingletonOf(Object S, Object T);
   

   that takes as input two objects $S$ and $T$, then returns whether $S = \Set{T}$. Again, $S$ and $T$ may or may not be sets.

5. Implement a function

   bool isElementOfPowerSet(Object S, Object T);
   

   that takes as input two objects $S$ and $T$, then returns whether $S$ and $T$ are sets and $S \in \wp(T)$. Again, $S$ and $T$ may or may not be sets.

   As a hint, you shouldn’t need to write code that computes $\wp(T)$ explicitly. See if you can find a different way to do this.

6. Implement a function

   bool isSubsetOfPowerSet(Object S, Object T);
   

   that takes as input two objects $S$ and $T$, then returns whether $S$ and $T$ are sets and $S \subseteq \wp(T)$. Again, $S$ and $T$ may or may not be sets.

7. Implement a function

   bool isSubsetOfDoublePowerSet(Object S, Object T);
   

   that takes as input two objects $S$ and $T$, then returns whether $S$ and $T$ are sets and $S \subseteq \wp(\wp(T))$. Again, $S$ and $T$ may or may not be sets.

To submit your work, upload your edited SetTheory.cpp file to GradeScope. You’ll get immediate feedback on your score from our autograder, and you’re allowed to resubmit as many times as you’d like.

As a note, you shouldn’t edit SetTheory.h; our autograder will always use the default version of that file when running tests.

Problem Three: Describing the World in Set Theory

The notation of set theory (e.g. $\cup, \cap, \wp, \subseteq, \in, \emptyset, =,$ etc.) is a great tool for describing the real world. Answer each of the following questions by writing an expression using set theory notation, but without using plain English, without using set-builder notation, without introducing any new variables, and without using propositional or first-order logic (which we’ll cover next week). No justification is required.

1. Let $C$ be the set of all cats and $D$ be the set of all dogs. Let $A$ be the set of all adorable things and $B$ be the set of all bouncy things. Write an expression that says "all cats and all dogs are both adorable and bouncy."

   Once you’ve written up your answer to this problem, take a minute to type-check it. As an example, suppose that you have the following answer:

   \[(A \in B) \cap (A \in C).\]

   This expression can’t be correct, and here’s one way to see this. The expression $A \in B$ is of type Boolean – either $A \in B$ is true or it isn’t – and the same is true of $A \in C$. However, the intersection operator $\cap$ can only be applied to sets. The expression therefore contains a type error: it tries to apply an operator that only works on sets to Boolean values.

   You can type-check this answer in a different way. For example, suppose you came up with this expression:

   \[A \cup D.\]

   Here, $A$ and $D$ are sets, so it’s perfectly fine to write $A \cup D$, which evaluates to an object of type set. But notice that the statement here asks you to write an expression that says “all cats and all dogs are both adorable and bouncy,” and that statement is of type Boolean (cats and dogs either have these properties or they don’t). Therefore, $A \cup D$ can’t possibly be an expression with the right meaning, since the type of the expression (set) doesn’t match the type of the statement (Boolean).

   If you’re having trouble with this problem, consider working backwards. You know that you need an expression that evaluates to type Boolean. What operations on sets do you have that produce Booleans? Or perhaps make the problem simpler. How would you say "all cats are adorable?" How about "all cats are both adorable and bouncy?"

2. Suppose you’re on an exciting first date. Let $Y$ represent the set of all your hobbies and $D$ represent the set of all your date’s hobbies. Write an expression that says that you have a hobby that your date doesn’t have.

   As before, type-check your answer! Should your answer represent a set? A Boolean? Something else?

3. Let’s say that a committee is a group of people, which we can think of as being represented by the set of people that comprise it. Let’s have $S$ represent the set of all students at Stanford and let $F$ represent the set of all faculty at Stanford. Write an expression representing the set of all committees you can make from Stanford students and faculty that contain at least one student and at least one faculty member. You can assume no one is both a student and a faculty member.

   Something to think about: how would you say “all committees made purely of students?” Something else to think about: what is the type of the statement to translate? Is it a Boolean? A set? Neither?

Problem Four: Writing Direct Proofs

It’s time to write your first proofs! Over the next three problems, we’ll walk you through three proofs of three different theorems. A key theme throughout these problems is

☞ the structure of a theorem dictates the structure of the proof. ☜

That is, the way the theorem is written gives the high-level structure of how the proof will be written. Indeed, you can make progress toward proving a theorem simply by “unpacking” the statement of the theorem to figure out what needs to happen and when.

In this problem, you will write a direct proof of this theorem:

Theorem: For all integers $n$, if $n$ is odd, then $n^2$ is odd.

For example, we see that $3$ is odd, and $3^2 = 9$ is odd as well.

Remember that the structure of a direct proof is dictated by the sentence structure of the theorem. In this case, our theorem looks like this:

Take a look back at the Guide to Proofs, the slides from our lecture on mathematical proofs, or the Proofwriting Checklist, for a refresher about how to work with universally-quantified statements and implications.

We want to extract from the sentence structure of our theorem the two foundations of our direct proof. The first is the starting point of the proof, which we call the assume step. Here, you’ll pick an arbitrarily-chosen value meeting the requirements of the antecedent of the implication. The second is the destination of the proof, which we call the want-to-show step. Here, that’s the consequent of the implication.

It is important to note that the want-to-show is not the entire theorem, although that might seem like the obvious thing to say since you clearly do want to show it! Think of the pair as like a start and destination of driving directions, and want-to-show is just the name of the destination.

1. Write the first sentence of this proof (the assume step).

   Ours starts with the word “pick,” but there are other valid options listed in the Guide to Proofs and Proofwriting Checklist.

2. Write the second sentence of this proof (the want-to-show step).

   Ours starts with the words “We want to show that…”

3. Now complete the proof, using this template as a guide, and copying in the two sentences you wrote above. The sizes of the blanks are not necessarily to scale.

   Notice that the first two sentences of a direct proof follow mechanically from the structure of the theorem. The third sentence in this example is also illustrative of a very common pattern for third sentences, which is to expand a definition from the “assume” sentence (in this case, the definition of odd integers).

   Theorem: For any integer $n$, if $n$ is odd, then $n^2$ is odd.

   Proof: Pick $\blank$. We want to show that $\blank$. Since $n$ is odd, there is an integer $k$ where $\blank$. (Note: When following the direct proof guidelines, the first three sentences are fairly mechanical, but now we need to exercise actual creativity. It helps to look at our want-to-show to remind ourselves of our destination on this journey. It says we want to show something about $n^2$, so we will begin with the expression $n^2$, and then apply algebra to it.) Then we see that

   \[\begin{aligned} n^2 & = \blank \\ & = \blank \\ & = \blank. \end{aligned}\]

   Therefore, there is an integer $m$ (namely, $\blank$) such that $\blank$, so $\blank$ (write your “Want to Show” statement here to announce that you’ve proved it), as required. ■

4. In the conclusion of the proof, the template has you using a variable named $m$ to show that $n^2$ is odd. The definition of odd integers from the lecture slides uses a variable $k$ for this purpose. Why did we choose $m$ here instead? Could we have used $k$?

Problem Five: Writing Proofs by Contrapositive

You’ve now written your first direct proof – great job! Let’s move on to our next proof technique, the proof by contrapositive. In this problem, you’ll use a proof by contrapositive to prove this theorem:

Theorem: For all integers $a$, $b$, and $c$, if $a^2 + b^2 = c^2$, then at least one of $a$, $b$, and $c$ is even.

Proof by contrapositive is another technique for theorems with a sentence structure that has the form of an implication. In fact, proof by contrapositive will proceed exactly like a direct proof, with similar “assume” and “want-to-show” steps, but will do so only after taking the contrapositive of the theorem to get a new, equivalent statement to prove.

1. What is the contrapositive of the theorem?

   Since the “for all” part comes before the “if” that begins the implication, the “for all” part remains unchanged by taking the contrapositive. Be very careful how you negate the “at least one of.”

2. Write the “assume” sentence of your proof, based on the antecedent of the contrapositive.

3. Write the “want-to-show” sentence of your proof, based on the consequent of the contrapositive.

4. Complete the proof, using this template as a guide, and copying in the two sentences you wrote above. As before, the sizes of the blanks are not necessarily to scale.

   Theorem: For any integers $a$, $b$, and $c$, if $a^2 + b^2 = c^2$, then at least one of $a$, $b$, and $c$ is even.

   Proof: We will prove the contrapositive of this statement, namely, $\blank$. To do so, pick $\blank$. We want to show that $\blank$.

   Since $a$, $b$, and $c$ are $\blank$, we know by our result from the previous problem that $a^2$, $b^2$, and $c^2$ are $\blank$.

   Because $a^2$ and $b^2$ are $\blank$, there exist integers $p$ and $q$ such that $\blank$. This means that $a^2 + b^2 = \blank = \blank$, which means that $a^2 + b^2$ is $\blank$.

   However, as mentioned earlier we know that $c^2$ is $\blank$. Therefore, we see that $\blank$ (write your “Want to Show” statement here to announce that you’ve proved it), as required. ■

In the above proof, we expanded the definition of odd for two values that we know are odd, $a^2$ and $b^2$. However, notice that we didn’t expand out the definition of odd for $c^2$ (e.g. "Since $c^2$ is odd, we know there's an integer …"), even though we know that $c^2$ is an odd number. While factually it wouldn’t be incorrect to expand out what it means for $c^2$ to be odd, it would be have been stylistically incorrect, since doing so would violate one of the rules from the Proofwriting Checklist.

5. What rule from the Proofwriting Checklist would have been violated if we had expanded out the definition of “$c^2$ is odd” in the above proof?

Problem Six: Writing Proofs by Contradiction

We’ve just checked off direct proofs and proofs by contrapositive. That leaves us with proofs by contradiction, which are the focus of this problem.

Your task in this problem is to prove the following theorem:

Theorem: For all integers $m$ and $n$, if $mn$ is even and $m$ is odd, then $n$ is even.

When writing a proof by contradiction, in your “assume” step you’ll simply assume the negation of the theorem to prove.

1. What is the negation of the above theorem?

   Remember: The negation of an implication is not an implication! Refer back to the lecture slides for how to negate an implication. Check the appendix to Lecture 02 for more details.

Once you’ve written the “assume” state in a proof by contradiction, you won’t explicitly articulate a “want-to-show” the way you did for a direct proof or a proof by contrapositive. Rather, by simply informing the reader that you’re going to proceed by contradiction, you’re implicitly telegraphing “oh, and by the way, I’m going to find two contradictory facts that follow from this assumption.” Therefore, rather than explicitly stating a “want to show” sentence like you did in the previous proofs, you’ll simply start exploring from your assumption, then indicate once you’ve reached a contradiction.

2. Fill in the blanks below to complete this proof by contradiction. As before, the relative sizes of the blanks are not necessarily indicative of how much you need to write.

   Theorem: For any integers $m$ and $n$, if $mn$ is even and $m$ is odd, then $n$ is even.

   Proof: Assume for the sake of contradiction that $\blank$. Since $m$ is $\blank$, we know that there is an integer $k$ where $\blank$. Similarly, since $n$ is $\blank$, there is an integer $r$ where $\blank$. Then we see that

   \[\begin{aligned} mn & = \blank \\ & = \blank \\ & = \blank, \end{aligned}\]

   which means that $mn$ is $\blank$, but this is impossible because $\blank$.

   We have reached a contradiction, so our assumption must have been wrong. Therefore, if $mn$ is even and $m$ is odd, then $n$ is even. ■

Problem Seven: Proving Existentially-Quantified Statements

This problem is all about proving existentially-quantified statements, statements that claim that certain objects with certain properties exist. As a reminder, one of the most straightforward ways to prove an existential statement is simply to find an example of an object meeting the appropriate properties, then prove it indeed has those properties. Note that these proofs are often easy to write once you know what the requisite objects are, but often require some time and effort because you have to find those objects in the first place.

1. Fill in the blanks to complete this direct proof about floors and ceilings.

   Theorem: There are real numbers $a$ and $b$ where $\floor{a} \cdot \ceil{b} \ne \floor{ab}$.

   Proof: Pick $a = \blank$ and $b = \blank$. Then we see that

   \[\floor{a} \cdot \ceil{b} = \floor{\blank} \cdot \ceil{\blank} = \blank \cdot \blank = \blank,\]

   but

   \[\floor{ab} = \floor{\blank \cdot \blank} = \floor{\blank} = \blank.\]

   Thus $\blank \ne \blank$, as required. ■

2. Fill in the blanks to complete this direct proof about sums of squares.

   Theorem: There exist natural numbers $a$, $b$, $c$, and $d$ such that $a > b > c > d > 0$ and $a^2 + b^2 + c^2 + d^2 = 137$.

   Proof: Pick $a = \blank$, $b = \blank$, $c = \blank$, and $d = \blank$. Then we see that

   \[\blank > \blank > \blank > \blank > \blank\]

   and

   \[\begin{aligned} a^2 + b^2 + c^2 + d^2 &= \blank^2 + \blank^2 + \blank^2 + \blank^2 \\ &= \blank + \blank + \blank + \blank \\ &= 137, \end{aligned}\]

   as required. ■

   Trial and error is a great strategy here. So is writing a quick Python script or C++ program. 😃

Fun fact: every natural number can be written as the sum of four perfect squares of natural numbers. This is called the four square theorem. However, not all natural numbers can be written such that all those natural numbers are nonzero and different from one another.

Problem Eight: Proving Mixed Universal and Existential Statements

This problem explores a style of proof in which we mix together universally-quantified and existentially-quantified statements. To do so, we’ll explore a concept called modular congruence.

Different numbers can yield the same remainder when divided by some number. For example, the numbers $1$, $12$, $23$, and $34$ all leave a remainder of one when divided by eleven. To formalize this relationship between numbers, we'll introduce a relation $\equiv_k$ that, intuitively, indicates that two numbers leave the same remainder when divided by k. For example, we'd say that $1 \equiv_{11} 12$, since both $1$ and $12$ leave a remainder of $1$ when divided by $11$, and that $8 \equiv_3 14$, since both $8$ and $14$ leave a remainder of $2$ when divided by $3$.

To be more rigorous, we'll formally define $\equiv_k$. If $k$ is an integer, we define $a \equiv_k b$ as follows:

We say that $a \equiv_k b$ when there exists an integer $q$ such that $a = b + kq$.

We’d read the statement “$x \equiv_k y$” aloud as “$x$ is congruent to $y$ modulo $k$.” For example, $7 \equiv_3 4$, because $7 = 4 + 3 \cdot 1$, and $5 \equiv_4 13$ because $5 = 13 + 4 \cdot (-2)$.

1. Fill in the blanks to complete this direct proof about modular congruence.

   Theorem: For all integers $x$ and $y$ and any integer $k$, if $x \equiv_k y$, then $y \equiv_k x$.

   Proof: Let $x$, $y$, and $k$ be arbitrary integers where $x \equiv_k y$. We need to show that $y \equiv_k x$. To do so, we will show that there is an integer $q$ where $\blank$. (Notice that after stating our want-to-show as usual for a direct proof, we expanded the want-to-show to be more specific about what it means to show that. Now our want-to-show has the form of an existential (“… there exists an integer $q$ …”). This is an important structural trait to focus in on. It means that in the body of the proof, we are going to have to demonstrate that such a $q$ exists very concretely by proposing a specific value for $q$.)

   Because $x \equiv_k y$, we know there is an integer $r$ such that $\blank$. Now, pick $q = \blank$. (Here it is, our announcement of the value we are proposing for $q$. Next, we need to justify to the reader that our choice works. What follows is that justification. Always do it in this order: first announce the value, then justify.) Then we see that

   \[\begin{aligned} y & = \blank && \color{blue}{\textit{(Do not write } x + qk \textit { here; see below)}} \\ & = \blank \\ & = x + kq, \end{aligned}\]

   which is what we needed to show. ■

   As the note in the proof suggests, you must not start with the equation $y = x + qk$, and do algebra from there. The reason is that you do not know yet if that is true, and proofs must be a sequence of statements that are certain to be true. So you want to write something there that we already know is true, and use algebra to reach the last line as written.

2. Prove for all integers $x$, $y$, $z$, and $k$ that if $x \equiv_k y$ and $y \equiv_k z$, we have $x \equiv_k z$.

3. Prove for all integers $x$ and $k$ that $x \equiv_k x$.

   This proof will feel different from the previous problems because you aren’t assuming anything about $x$ or $k$ other than the fact that they’re integers. But the basic setup will feel the same: you’re searching for some choice of $q$ that makes some equality hold. Follow the general idea from earlier when structuring your proof: state, explicitly, what choice of $q$ you’re going to make, then prove that it has the right properties.

Problem Nine: Proof Critiques

One of the best ways to improve your proof writing is to do some proof reading. In doing so, you’ll get a much better perspective on why certain stylistic conventions matter, both in the positive sense, (“wow, that’s so easy to read!”) and in the negative sense (“I can’t make heads or tails of this!”). You’ll also get practice tracing through mathematical arguments, which will help expand your repertoire of techniques and give you a better sense of what details to focus on in your own reasoning.

We’ve curated three proofs for you to review. Read these proofs, and for each one, do the following:

• Critique its style. Our Proofwriting Checklist contains specific details to review in any proof. Go through the checklist one item at a time, identifying any style errors and explaining each.
• Critique its reasoning. Are the arguments given by these proofs correct? If there are logic errors, point them out and demonstrate why they’re incorrect. Then, determine whether the theorem being proved is even true in the first place. After all, you can prove anything using faulty logic!

Complete the critique for each of the three proofs by filling out the table below:

1. Critique this proof about parities (the parity of a number is whether it’s even or odd.)

   Theorem: The sum of an even integer and an odd integer is odd.

   Proof: This proof will talk about adding together different kinds of numbers. An even integer is an integer that can be written as $2k$ for some integer $k$. Therefore, $m = 2k$. Similarly, an odd integer is one that can be written as $2k+1$ for some integer $k$. So $n = 2k+1$. $m + n = 2k + 2k + 1 = 4k + 1$. Therefore $m + n$ is odd. ■

2. Critique this proof about natural numbers.

   Theorem: Every natural number is odd.

   Proof: Assume for the sake of contradiction that every natural number is even. In particular, that would mean that $137$ is even. Since $137 = 2 \cdot 68 + 1$ and $68$ is a natural number, we see that $137$ is odd. We know that there is no integer $n$ where $n$ is both odd and even. However, $n = 137$ is both even and odd. This is impossible. We’ve reached a contradiction, so our assumption must have been wrong. Therefore, every natural number is odd. ■

3. Critique this proof about modular arithmetic.

   Theorem: If $n$ is an integer and $n \equiv_2 0$, then $n \equiv_4 0$.

   Proof: We will prove the contrapositive of this statement and show that if $n$ is an integer where $n \equiv_4 0$, then $n \equiv_2 0$. Since $n \equiv_4 0$, we know $n = 0 + 4q$. This in turn tells us that $n = 2(2q)$, so there is an integer $m$ such that $n = 2m$. Consequently, we see that $n = 0 + 2m$, and so $n \equiv_2 0$, as required. ■

Problem Ten: All Squared Away

Let’s begin with a new definition. A natural number $n$ is called a perfect square if there’s an integer $k$ such that $n = k^2$. For example, $16$ is a perfect square because $16 = 4^2$, but $15$ is not.

For reference, the first positive perfect squares are

Your task is to prove the following theorem:

Theorem: If $n$ is an odd natural number and $n \ge 3$, then there is an $m \in \mathbb{N}$ where $m > 0$ and $m^2 + mn$ is a perfect square.

Rather than diving headfirst into the proof, let’s first take a minute to explore what the theorem says.

1. Fill in the following blanks with positive natural numbers. No justification is necessary. We’ve filled the one of the blanks for you.

   • When $n = 3$, we can write $n = 2 \cdot \blank + 1$, and one $m$ that works is $\blank$.
   • When $n = 5$, we can write $n = 2 \cdot \blank + 1$, and one $m$ that works is $\blank$.
   • When $n = 7$, we can write $n = 2 \cdot \blank + 1$, and one $m$ that works is $\blank$.
   • When $n = 9$, we can write $n = 2 \cdot \blank + 1$, and one $m$ that works is $16$.
   • When $n = 11$, we can write $n = 2 \cdot \blank + 1$, and one $m$ that works is $\blank$.

   Start by filling in the rows for $n = 3$ and $n = 5$. As a hint, the numbers in those rows are all less than five, so in the absolute worst case you can just try each of the numbers in the range to see which ones work. The value of $m$ in the row for $n = 7$ is less than ten.

   Filling in the last row may require you to make an educated guess based on the pattern that emerges and to use a calculator to check your work.

2. Fill in the following blank. No justification is required.

   When $n = 2k + 1$, pick $m = \blank$.

3. Prove the theorem.

   This isn’t the first time you’ve seen a result linking odd integers and perfect squares. Check out the first lecture on mathematical proofs for an example of how you might want to structure this.

   The fact that $n \ge 3$ is necessary here and the theorem is not true in the case where $n = 1$. So once you’ve finished writing your proof, read over it and make sure you can see a spot where you specifically cite the fact that $n \ge 3$. If you don’t do this, there has to be an error in the proof, since otherwise we could plug in $n = 1$ and the reasoning would be incorrect.

Problem Eleven: Quarter-Squares

This problem explores a fascinating group of numbers called the quarter-squares. The quarter-squares are numbers of the form $\floor{\frac{n}{2}}{\ceil{\frac{n}{2}}}\text,$ where $n$ is a natural number. For example, the first quarter-squares are

Here, 0 appears twice because it’s both $\floor{\frac{0}{2}}\ceil{\frac{0}{2}}$ and $\floor{\frac{1}{2}}\ceil{\frac{1}{2}}$

Prove for all natural numbers $n$ that if $\floor{\frac{n}{2}}{\ceil{\frac{n}{2}}}$ is odd, then $n$ is even.

Problem Twelve: Tag Your Pages

When you submit this problem set on Gradescope, you'll be asked to tag your pages (identify which pages have the answers to which problems on them). Tagging pages is immensely helpful to the TAs when grading. If you tag your pages, when the TAs go to grade a particular problem, they'll be presented with your solution automatically. Conversely, if you don't tag your pages, when the TAs go to grade a particular problem, Gradescope will tell them something to the effect of "the student might not have answered this question at all." How sad!

Please make sure to tag your pages when submitting. We'll give you credit for this problem if you do. (Aside from tagging your pages, you do not need to do anything to answer this problem.)

Optional Fun Problem: Infinite Deviation

In our first class, we sketched a proof of Cantor’s theorem. This proof assumed there was a pairing between the elements of a set $S$ and the subsets of $S$, then constructed a set that was different in at least one position from each of the paired sets.

Show that, no matter how you pair the elements of $\mathbb{N}$ with the subsets of $\mathbb{N}$, there’s always at least one set $X \subseteq \mathbb{N}$ that differs in infinitely many positions from each of the paired sets. Justify your answer, but no formal proof is necessary.