\documentclass[12pt]{article}
\begin{document}
\centerline{\bf Homework 2, MORALLY Due Feb 14}
\newcommand{\implies}{\Rightarrow}
\newcommand{\NSQ}{{\rm NSQ}}
\newcommand{\into}{{\rightarrow}}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\Ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\Z}{{\sf Z}}
\newcommand{\N}{{\sf N}}
\newcommand{\Q}{{\sf Q}}
\newcommand{\R}{{\sf R}}
\newcommand{\Rpos}{{\sf R}^+}
\centerline{\bf WARNING: THIS HW IS FOUR PAGES LONG!!!!!!!!!!!!!!!!!}
\begin{enumerate}
\item
(25 points)
\begin{enumerate}
\item
(10 points)
Use truth table so show that
$$\neg (p \vee q \vee r) \equiv \neg p \wedge \neg q \wedge \neg r$$
(This is called {\it DeMorgan's law on three variables}.)
\item
(15 points)
Consider the statement:
$$\hbox{ For all $n$ }[\neg (p_1 \vee \cdots \vee p_n) \equiv \neg p_1 \wedge \cdots \wedge \neg p_n]$$
Prove it. Note that you cannot use Truth Table since we want it for all $n$.
Do not use Induction (later when we learn induction we will do that).
Use reasoning about what the truth table for both sides must look like.
\end{enumerate}
\centerline{\bf GOTO NEXT PAGE}
\newpage
\item
(25 points -- 5 points each)
For each of the following statements write the negation without using any negations signs.
\begin{enumerate}
\item
$x=4$
\item
$x_1 \le x_2 \le x_3 \le x_4$
\item
$x\ge 5$ AND $x\ge 10$
\end{enumerate}
\centerline{\bf GOTO NEXT PAGE}
\newpage
\item
(35 points)
Let $n\in\N$. $\NSQ(n)$ is the least number such that $n$ can be written as the sum
of $\NSQ(n)$ squares. Clearly $\NSQ(n)\le n$ since
$$n= 1^2 + \cdots + 1^2.$$
\noindent
It is known that $\NSQ(n)\le 4$.
In this problem you will write and run two programs that will,
given $n\in\N$, find a bound on $\NSQ(n)$.
\begin{enumerate}
\item
Write a program that will, given $n$, does the following:
\begin{itemize}
\item
Find the largest $n_1$ such that $n_1^2\le n$.
If $n-n_1^2=0$ then you are done: $n=n_1^2$ so output 1. If not then goto the next step.
\item
Find the largest $n_2$ such that $n_2^2\le n-n_1^2$.
If $n-n_1^2=0$ then you are done: $n=n_1^2 + n_2^2$ so output 2. If not then $\ldots$
\item
Keep going like this until there is an output.
\end{itemize}
\item
Write a program that will, given $n$, find, for all $1\le i\le n$, a number $A[i]$
such that $i$ can be written as the sum of $A[i]$ squares.
\begin{itemize}
\item
$A[0]\leftarrow 0$ (0 can be written as the sum of 0 squares).
\item
$A[1]\leftarrow 1$ (1 can be written as the sum of 1 square).
\item
For $i\leftarrow 2$ to $n$
$$A[i]\leftarrow 1+ \min\{A[i-j^2] \colon i-j^2\ge 0\}$$
\end{itemize}
\end{enumerate}
\vfill
\centerline{\bf GOTO NEXT PAGE}
\newpage
\item
(5 points)
Run the first program on $n=1,2,\ldots, 1000$.
List out all of the $n$ where the answer was $\ge 5$.
\item
(0 points) How would you fill in the following sentence
{\it The first program on input $n$ outputs a number $\ge 5$ iff BLANK.}
\item
(5 points)
Run the second program on $n=1000$ (so we now know the answers for $1,\ldots,1000$).
List all of the $n$ where $A[n]$ differs from the first program on $n$.
\item
(0 points) How would you fill in the following sentence
{\it The first and second differ on $n$ iff BLANK.}
\item
(5 points)
List all of the $n$ such that $A[n]=4$.
\item
(0 points) How would you fill in the following sentence
{\it $A[n]=4$ iff BLANK}
\item
(Extra Credit) PROVE the following:
{\it There exists and infinite number of $x\in\N$ such that $x$ cannot be written
as the sum of $\le 3$ squares-of-naturals.}
\end{enumerate}
\end{document}