\documentclass[12pt]{article}

\begin{document}

\centerline{\bf Untimed Midterm. Morally Due Feb 28, 9:00AM}
\newcommand{\implies}{\Rightarrow}
\newcommand{\NSQ}{{\rm NSQ}}
\newcommand{\NCU}{{\rm NCU}}
\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 MIDTERM IS FOUR PAGES LONG!!!!!!!!!!!!!!!!!}


\begin{enumerate}


\item 
(10 points) 
In this problem $L_n$ is the linear order on $n$ points. 
In this problem you may assume that, 

{\it for all $n$ there is a $k$ such that DUP wins the DUP-SPOILER game with 
$L= L_n$ and $L'= \N + \N^*$.  (In class we agreed that $k$ was roughly $\log n$.
For this problem it does not matter what $k$ is.)}
(Recall that $\N^*$ is $\N$ backwards $\ldots, 4,3,2,1,0$. 

\begin{enumerate}
\item
Give a strategy for Duplicator to win the DUP-SPOILER game with

$L= \N$

$L'= \N+\Z$

Any value of $k$

\item
Give a strategy for Duplicator to win the DUP-SPOILER game with

$L= \Z$

$L'= \Z+\Z$

Any value of $k$. 

(You may use the last part in this part.) 


\end{enumerate}

\vfill

\centerline{\bf GOTO NEXT PAGE}

\newpage


\item
(20 points)
In this problem you will write a program that, given $n,m$, outputs a formula on
$n$ variables that has {\it exactly} $m$ satisfying assignments. That is an informal
description which I formalize soon. 

You will be outputting boolean formulas in DNF form. We illustrate the format we want with an
examples.

If your formula is

$$(x_1 \wedge x_2 \wedge \neg x_3) \vee (\neg x_1 \wedge x_7)$$

you output

$$(1,2,n3)(n1,10).$$

The {\it length} of a formula is the sum of the following (and we give
examples from the above formula). 

The number of parenthesis: 4.

The number of commas: 3.

The number of $n$'s: 2.

The number of occurences of numbers: 5. This is 1,2,3,1,10. Note that we don't count the 10 as
two characters. 

The length of the above formula is $4+3+2+5=14$. 

\vfill

\centerline{\bf GOTO NEXT PAGE}

\newpage


\begin{enumerate}
\item
(0 points but you need it for the next part)
Write a program that will, on input $n,m$ output one of the following:
\begin{itemize}
\item
If $m=0$ then output the formula $x \vee \neg x$. (Note that this has 0 satisfying assignments.) 
\item
If $m\ge 2^n+1$ then output THERE IS NO SUCH FORMULA. (Note that there really is no such formula.) 
\item 
If $1\le m\le 2^n$ then output a DNF formula on $n$ variables that has exactly $m$ satisfiying assignments.
(There may be many, just output one of them.) Also output the formulas length. 
\end{itemize} 
\item
(5 points) 
Run your program on  (2,2), (3,3), (4,4), $\ldots$ (10,10) and plot the graph of $n$ vs. the length
of what you get on input $(n,n)$. Hand in your data and the graph.
\item
(0 points)
Speculate what the function $n$ goes to length of the formula for $(n,n)$ roughly is. 
\item
(15 points) Email Emily your code. She will run it on many values so make sure that it is correct. 
\end{enumerate}

\vfill

\centerline{\bf GOTO NEXT PAGE}

\newpage

\item 
(20 points)
Let $n\in\N$. $\NCU(n)$ is the least number such that $n$ can be written as the sum
of $\NCU(n)$ cubes. Clearly $\NCU(n)\le n$ since 

$$n= 1^3 + \cdots + 1^3.$$

\noindent
It is known that $\NCU(n)\le 9$. 

In this problem you will write one programs that will,
given $n\in\N$, find a bound on $\NCU(n)$. 

\vfill

\centerline{\bf GOTO NEXT PAGE}

\newpage

\begin{enumerate}
\item 
(0 points but you need to do this for the next part.) 
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]$ cubes. 
\begin{itemize}
\item
$A[0]\leftarrow 0$ (0 can be written as the sum of 0 cubes).
\item
$A[1]\leftarrow 1$ (1 can be written as the sum of 1 cube).
\item 
For $i\leftarrow 2$ to $n$

$$A[i]\leftarrow 1+ \min\{A[i-j^3] \colon i-j^3\ge 0\}$$

(We are speculating that if we used $j^3$ there is $i-j^3$ left.) 

\end{itemize}


\item
(4 points- 1 points each)
Run the program on $n=1,2,\ldots, 1000$. 
\begin{enumerate}
\item
How many required 9 cubes? List them all. (23 should be one of them.) 
\item
How many required 9 cubes? List all that are $\le 100$.  (50 should be one of them.) 
\item 
Write 50 as the sum of 8 cubes.
\item
Prove that 50 cannot be written as the sum of 7 cubes.
(You may use that 23 cannot be written as the sum of 8 cubes.) 
\end{enumerate} 

\item
(16 points) Email your code to Emily. She will run it on many numbers so
make sure it is correct 


\end{enumerate}
\end{enumerate}
\end{document}