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