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