Midterm Exam I

Due Sunday, October 17 at 2:30 pm Pacific

---

Instructions

You have the full 48 hours to work on the midterm. There are no time limits on the exam other than that it has to come in before the deadline. That means that it’s fine to start working on the exam, take a break, go for a walk or hike in the area, get a good night’s sleep, come back, pick up where you left off, etc. Although you have the full 48 hours to complete the exam, the exam itself is designed to take around three hours to complete.

Please type your answers the way you type up your problem sets. There’s a $\LaTeX$ template available here if you’d like to use it, though it’s not required and you can us MS Word or Google Docs if you'd like.

🖋 M1 $\LaTeX$ Template

Exam-specific note: If you are using Overleaf to typeset your solutions, make sure your problem set partners are not shared on the document you use.

This exam includes one problem in which you will type your solutions up in Qt Creator and submit online. The starter files are available here:

📦 M1 Starter Files

Once you’re finished, submit your written and coding answers on Gradescope. As with the problem sets, you will submit the written and coding components separately. Please leave appropriate buffer time to ensure your submission comes in by the deadline. As with the problem sets, we’ll grade the last version you submit before the deadline, so feel free to periodically submit what you have just in case something comes up.

Honor Code Policies

This exam is open-book and open-note, so you are free to make use of all course materials on the course website and on Canvas, including lecture slides and lecture videos. You are also permitted to search online for conceptual information (for example, by visiting Wikipedia). However, the midterm exam must be completed individually. It is a violation of the Stanford Honor Code to communicate with any other humans about the exam, to solicit solutions to the exam, or to share your solutions with others.

You are not permitted to communicate with other humans about the exam or to solicit help from others. For example, you must not communicate with other students in the course about the exam, and you must not ask questions on sites like Chegg or Stack Overflow.

If you have questions about this exam, you are welcome to post them in EdStem. We will not be able to offer much support other than clarifying questions about what is being asked of you in each problem. If you do post in EdStem, you must post privately; posting publicly violates the "do not communicate with other humans" rule.

All work done with the assistance of any material in any way (other than provided CS103 course materials) must include a detailed citation (e.g., “I visited the Wikipedia page for $X$ on Problem 1 and made use of insights $A$, $B$, and $C$”). Copying solutions is never acceptable, even with citation, and is always a violation of the Honor Code. If by chance you encounter solutions to a problem, navigate away from that page before you feel tempted to copy. If you’re worried you’ve done something you probably shouldn’t have and aren’t sure what to do, email the course staff before you submit and we’ll figure out how to proceed.

Words of Encouragement

Problem One: Quarter-Squares (8 Points)

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

\[0, 0, 1, 2, 4, 6, 9, 12, 16, 20, 25, 30, 36, 42, 49, 56, 64, 72, 81, 90, \dots\]

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

Prove the following using a proof by contrapositive: for all natural numbers $n$, if $\ceil{\frac{n}{2}}\floor{\frac{n}{2}}$ is odd, then $n$ is even.

Problem Two: Translating Into Logic (6 Points)

In each of the following, write a statement in first-order logic that expresses the indicated sentence. Your statement may use any first-order construct (equality, connectives, quantifiers, etc.), but you must only use the predicates $Person$, $Robot$, $Cat$, and $Loves$.

To submit your answers, edit the file res/TranslatingIntoLogic.fol with your formulas. There’s information in that file about the expected format for your answers.

1. (2 Points) Write a statement that says "there's a cat that loves all people and a person who loves all cats."

2. (2 Points) Write a statement that says "if there are no cats, then there are no robots either."

3. (2 Points) Write a statement that says "no two people love the same cat."

If you run the program that's included with the starter files, it will let you check the syntax of your answers (are the parentheses balanced? are all variables in scope? etc.). However, since this is a midterm, it will not allow you to run tests to check if your answers are correct. Similarly, when you upload your answers to Gradescope, you will not be able to see your score until after the midterm comes due.

You may submit online to the autograder as many times as you'd like. We'll only take the last submission.

Problem Three: Tower of Power (4 Points)

Consider the sequence of sets $A_0, A_1, A_2, \dots$ defined as follows:

\[A_0 = \emptyset \qquad A_{n+1} = \wp\left(A_n\right)\text.\]

That is, $A_0 = \emptyset$, $A_1 = \wp(\emptyset)$, $A_2 = \wp(\wp(\emptyset))$, $A_3 = \wp(\wp(\wp(\emptyset)))$, etc., and more generally $A_n$ is formed by taking the $n$th-order power set of $\emptyset$.

Answer each of the following questions. No justification is required.

1. (1 Point) Is there a natural number $n$ where $\Set{\emptyset, \Set{\emptyset}} \subseteq A_n$? If so, give the smallest natural number $n$ with this property. If not, just answer "no."

2. (1 Point) Is there a natural number $n$ where $\Set{\emptyset, \Set{\emptyset}} \in A_n$? If so, give the smallest natural number $n$ with this property. If not, just answer "no."

3. (1 Point) Is there a natural number $n$ where $\Set{\Set{\Set{\Set{\Set{\emptyset}}}}} \subseteq A_n$? If so, give the smallest natural number $n$ with this property. If not, just answer "no."

4. (1 Point) Is there a natural number $n$ where $\Set{\Set{\Set{\Set{\Set{\emptyset}}}}} \in A_n$? If so, give the smallest natural number $n$ with this property. If not, just answer "no."

Problem Four: A Clever Little Equation (8 Points)

Consider the following equation, which depends on three variables $m$, $n$, and $p$:

\[\left(1 + \frac{1}{m+1} \right)\left(1 + \frac{1}{n+1} \right)\left(1 + \frac{1}{p+1} \right) = 5\text.\]

In what follows, we’re going to assume that $m \in \naturals$, that $n \in \naturals$, and that $p \in \naturals$. (As a reminder, we consider zero to be a natural number.)

There are infinitely many ways to pick three natural numbers $m$, $n$, and $p$. Of those infinitely many choices, how many solve the above equation? In this problem, you'll find out.

1. (3 Points) Using a proof by contradiction, prove for all natural numbers $m$, $n$, and $p$ that if $m$, $n$, and $p$ satisfy the above equation, then at least one of $m$, $n$, and $p$ is equal to zero.

   We are asking you to do this proof by contradiction, not contrapositive.

   As a hint, how big can $\left(1 + \frac{1}{m+1} \right)$ get when $m \ne 0$?

2. (4 Points) Using a proof by contradiction, prove for all natural numbers $m$, $n$, and $p$ that if $m$, $n$, and $p$ satisfy the above equation, then at least two of $m$, $n$, and $p$ are equal to zero.

   This is a great place to use the phrase "without loss of generality." If you know something is true about one of $m$, $n$, and $p$ but aren't sure which one it is, you can always say something like

   "Assume, without loss of generality, that $m$ [has some specific property]"

   to avoid writing out cases for all three variables.

3. (1 Point) List all the solutions to the above equation where $m$, $n$, and $p$ are natural numbers. No justification is required.