\documentclass[12pt]{article}

\newcommand{\I}{\mathbb{I}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\D}{\mathbb{D}}


\usepackage{comment}
\usepackage{amsmath}
\usepackage{amssymb}  % for \nmid
\begin{document}


\centerline{Homework 02, MORALLY Due Feb 17}

\newif{\ifshowsoln}
\showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks.

\begin{enumerate}


\item
(40 points)
For this problem FIRST write the program and make conjectures THEN
look up whats true. 

\begin{enumerate}
\item
(0 points) 
Write a program that does the following:
For every $1\le n\le 900$:
\begin{itemize}
\item
Using the greedy method (Leo will tell you about that in class)
determine natural numbers $(x_1,x_2,\ldots,x_k)$ such that 
$x_1^3 + \cdots + x_k^3=n$. 
Using brute force (Leo will tell you about that in class)
determine natural numbers $(x_1,x_2,\ldots,x_L)$ such that 
$x_1^3 + \cdots + x_L^3=n$ with $L$ minimum. 
\item
Below I have the first 9 rows of the output. We use Gr-$k$ and Br-$L$ so the table fits on the page.
\end{itemize}

    

\hspace{-10em}\begin{tabular}{|l|l|l|l|l|}
\hline
 $n$ & Gr-$k$ & Greedy-$x_i$'s & Br-$L$ & Brute-$x_i$'s \cr
\hline
1   & 1         & $1=1^3$            & 1         & $1=1^3$       \cr
2   & 2         & $2=1^3+1$          & 2         & $2=1^3+1^3$       \cr
3   & 3         & $3=1^3+1^3+1^3$    & 3         & $3=1^3+1^3+1^3$   \cr
4   & 4         & $4=1^3+1^3+1^3+1^3$   & 4      & $4=1^3+1^3+1^3+1^3$   \cr
5   & 5         & $5=1^3+1^3+1^3+1^3+1^3$   & 5  & $5=1^3+1^3+1^3+1^3+1^3$   \cr
6   & 6         & $6=1^3+1^3+1^3+1^3+1^3+1^3$   & 6  & $6=1^3+1^3+1^3+1^3+1^3+1^3$   \cr
7   & 7         & $7=1^3+1^3+1^3+1^3+1^3+1^3+1^3$   & 7  & $7=1^3+1^3+1^3+1^3+1^3+1^3+1^3$   \cr
8   & 1         & $8=2^3$   & 1  & $8=2^3$   \cr
9   & 2         & $9=2^3+1^3$   & 2  & $9=2^3+1^3$   \cr
\hline
\end{tabular}

\bigskip

DO NOT hand in the program or the output. 

\vfill

\centerline{\bf GO TO NEXT PAGE FOR THE REST OF THIS PROBLEM}

\newpage

\item
(30 points)\begin{enumerate}
    \item (15 points)
Create a table that shows how many numbers $\leq 900$ require 1 cube, 2 cubes, 3 cubes, and so on for both the Greedy and Brute Force solutions. Below is a sample table (THIS DOES NOT CONTAIN THE CORRECT ANSWER):
\begin{center}
    \begin{tabular}{|c|c|c|}
     \hline  $\# $ of Cubes & Greedy & Brute Force  \\ \hline
        1 & 3 & 8 \\
        2 & 4 & 2 \\
        3 & 28 & 17 \\
        \vdots & \vdots &\vdots \\ \hline
    \end{tabular}
\end{center}
\item (15 points) Based on this data make conjectures of the following forms:

\begin{enumerate}
\item 
Every $n$ is the sum of $\le XXX$ cubes. 
Write your conjecture in quantifiers. 
\item
All but a finite number of $n$ is the sum of $\le XXX$ cubes. 
Write your conjecture in quantifiers. 
\item
For large $n$, the Greedy algorithm gives the same answer as brute force for approximately XXX fraction of $\{1,...,n\}$. 
(Note that brute force gives the {\it correct} answer so we are wondering how often Greedy gives the
correct answer.) 
\end{enumerate}
\end{enumerate}
\item
(10 points) 
Look on the web and/or use AI to determine what is known and what is conjectured
about these problems.
\end{enumerate}

\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item
(30 points) 
In this problem I will give a property of a domain $\D$ and I want 
you to give me both: \begin{itemize}
    \item That property expressed as quantifiers.
    \item Either a domain $\D$, $\D \subseteq \R$, that has that property or the statement (without proof) that there is no such domain.
\end{itemize}

I give an EXAMPLE:

$\D$ has a least element

Expressed as quantifiers: $(\exists x\in \D)(\forall y\in \D)[x\le y]$.

Domain that works: $\N$ or you could write $\{0,1,2,\ldots\}$. 

\begin{enumerate}
\item
(10 points)
$\D$ is infinite and has both a least element and a greatest element.

\item 
(10 points)
Every element $x\in \D$ has both a successor  element $y$ (so $x<y$ and there is nothing inbetween)
and also a predecessor element $w$ (so $w<x$ and there is nothing inbetween). 

\item
(10 points)
$\D$ satisfies all the following properties
\begin{enumerate}
    \item $\D$ has a least element.
    \item $\D$ has a greatest element.
    \item Every element in $\D$ except the least has a predecessor.
    \item Every element in $\D$ except the greatest has a successor.
\end{enumerate} (So the question here is to determine
if such a $\D$ exists, and either give me the $\D$ or state, without proof, there is no $\D$.)
\end{enumerate}


\ifshowsoln



\fi 

\vfill

\centerline{\bf GO TO NEXT PAGE} 

\newpage

\item
(30 points)
In this problem the only symbols you can use are 

\begin{itemize}
\item 
The usual logical ones: $\forall$, $\exists$ $\wedge$, $\vee$, $\neg$.
\item 
Variables that range over the domain: $x_1,x_2,x_3,\ldots$.
\item
These math symbols: $<$, $\le$, $>$, $\ge$, $=$, $\ne$.
\end{itemize}

For each of the following either give me the sentence I want OR
state (without proof) that there is no such sentence. 

\begin{enumerate}
\item
(15 points)
A sentence which is true with domain $\Z$ but false with domain $\Q$. 
\item 
(15 points)
($(0,1)$ is the set of all reals between 0 and 1 but not including 0 or 1.)
A sentence which is true with domain $(0,1)$ but false with domain $\Q$. 
(Warning: You can't use $(\exists x)[x^2=\frac{1}{2}]$ since this cannot be
stated just using $<$.) 
\end{enumerate}


\vfill

\centerline{\bf GO TO NEXT PAGE} 

\newpage
\item 
{\bf Honors HW 2} This is graded separately as Honors HW02.

Let $\I$ be the set of irrationals. As usual $\Q$ is the set of rationals.

\begin{enumerate}
\item 
(0 points, nothing to hand in)
Find someone in the class to play the DUP-SPOILER game $(\I,\Q,5)$.

\item
(100 points)
Determine which of the following statements is true and give an informal proof of it:

\begin{itemize}
\item 
There is a $k$ such that SPOILER wins $(\I,\Q,k)$.
The informal proof is a value $k\in\N$ and a strategy
for SPOILER to win $(\I,\Q,k)$. 
You DO NOT have to prove that
the strategy works, which is why I called it an {\it informal proof}.
BUT the strategy has to be well enough written so that I could carry
it out if asked to play the game.

\item
There is no $k$ such that SPOILER wins $(\I,\Q,k)$. 
The informal proof is to give, for all $k\in\N$, a strategy
for DUP to win $(\I,\Q,k)$. 
You DO NOT have to prove that
the strategy works, which is why I called it an {\it informal proof}.
BUT the strategy has to be well enough written so that I could carry
it out if asked to play the game.
\end{itemize}


\end{enumerate}
\end{enumerate}

\end{document}

