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