\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{comment} 

\newcommand{\IS}{{\rm ISAAC}}
\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{\goes}{\rightarrow}
\newcommand{\nth}{n^{th}}
\newcommand{\N}{\sf{N}}
\newcommand{\Q}{\sf{Q}}
\newcommand{\R}{\sf{R}}
\newcommand{\C}{\sf{C}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\es}{\emptyset}
\newcommand{\st}{\mathrel{:}}
\newcommand{\e}{\varepsilon}
\usepackage{tikz}
\usetikzlibrary{automata,positioning,arrows}


\begin{document}

\centerline{\bf Homework 6 Morally Due March 12 at 3:30PM}

\begin{enumerate}
\item
(0 points, but if you actually miss the midterm without telling Dr. Gasarch ahead of time, you will lose 100 points on this homework)
When will the midterm be (give date and time)?

\newpage


\item 
(25 points)
In class I showed a protocol for EQ that used $O(\log n)$ bits but
had an error of $\sim \frac{1}{n}$. 

\begin{enumerate}
\item 
(10 points) 
Sam DEMANDS that we get a protocol that has error of $\sim \frac{1}{n^2}$
and still uses $\ll n$ bits. Give such a protocol. 
Prove that the error rate is $\sim \frac{1}{n^2}$.
State how many bit are used. 
Use big O notation.

\item 
(15 points) 
Let $k(n)$ be a very slow growing function of $n$ (so perhaps $k=\log\log n$).
Now Sam DEMANDS that we get a protocol that has error of $\sim \frac{1}{n^{k(n)}}$
and still uses $\ll n$ bits. Give such a protocol. 
Prove that the error rate is $\sim \frac{1}{n^{k(n)}}$.
State how many bit are used. 
Use big O notation. 


\end{enumerate}

\newpage

\item
\newcommand{\ob}[1]{\frac{#1}{78}}
(25 points) 

In this problem we guide you the the proof that 
$f(45,26)\le \ob{32}$.

Assume, by way of contradiction, that there is a $(45,26)$-procedure with smallest piece
$>\ob{32}$.

By the usual techniques, we can assume that every muffins is cut into 
exactly 2 pieces. Hence there are 90 pieces. 

\noindent
{\bf Case 1:} Alice gets $\ge 5$ shares. SHOW HOW THIS LEADS TO SOME SHARE BEING
of size $<\ob{32}$. 

\noindent
{\bf Case 2:} Bob gets $\le 2$ shares. 
SHOW HOW THIS LEADS TO SOME SHARE BEING of size $<\ob{32}$. 

In the subsequent cases we assume the negation of Cases 1 and 2. 
Hence every student either gets 3 shares 
or 4 shares.


A student who gets 3 shares is called a 3-student.

A student who gets 4 shares is called a 4-student.

A share that is given to a 3-student is called a 3-share.

A share that is given to a 4-student is called a 4-share.

Let $s_3$ (resp. $s_4$) be the number of
3-students (resp. 4-students). SHOW HOW YOU DEDUCE 
there are 14 3-students and 12  4-students. 
Note that there are 42 3-shares, and 48 4-shares.

We now look at intervals.

\noindent
{\bf Case 3:} Alice has a 4-share $\ge \ob{39}$. 
SHOW HOW THIS LEADS TO SOME SHARE BEING of size $\le \ob{32}$. 

\noindent
{\bf Case 4:} Bob has  a 3-share $\le \ob{43}$. 
SHOW HOW THIS LEADS TO SOME SHARE BEING of size $\le \ob{32}$. 

\noindent
{\bf Case 5:} The following picture captures the negation of cases 1,2,3, and 4.

\medskip
\[
 \begin{array}{ccccccc}
( & \hbox{48 4-shs} & )[ & 0 & ]( & \hbox{42 3-shs} & ) \cr
\ob{32} & & \ob{39} & & \ob{43} & & \ob{46} \cr
\end{array}
\]
\medskip

\noindent
SHOW HOW WE GET A CONTRADICTION.  {\it Hint:} Note $\ob{39}=\frac{1}{2}$. 

END OF PROOF


\newpage

\item 
(25 points)
\begin{enumerate}
\item
(10 points) 
Proof without using the Floor-Ceiling theorem that
any protocol that 
takes 10 muffins and divides them for 3 people so that
everyone gets $\frac{10}{3}$ 
has to have a piece of size $\le \frac{4}{9}$. 
(So $f(10,3)\le \frac{4}{9}$.)
You can assume that in any such protocol every muffins is cut into
exactly 2 pieces. 
\item
(15 points) 
Give a protocol that 
takes 10 muffins and divides them for 3 people
so that everyone gets $\frac{10}{3}$, and every  piece is of size $\ge \frac{4}{9}$ .
(So $f(10,3)\ge \frac{4}{9}$.) 
\end{enumerate}


\newpage

\item 
(25 points)
\begin{enumerate} 
\item
(15 points) 
Consider the formula


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

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


$
(x_3 \vee \neg x_4)  \wedge 
$

$\vdots$

$
(x_{n-1}\vee \neg x_n)  \wedge
$

$
(x_n \vee \neg x_1)
$


How many satisfying assignments does this formula have? Justify!
(Note that it may be a function of $n$.) 


\item
(10 points) 
Let $n\ge 4$. 
Give an example of a 2CNF formula which uses $n$ variables and is NOT satisfiable. 
(You may assume $n$ is even or odd or anything of that sort to make the answer
smoother.) 


\end{enumerate}




\end{enumerate}

\end{document}