\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}