\documentclass[12pt]{article}

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

\newcommand{\D}{{\mathbb D}}
\newcommand{\G}{{\mathbb G}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\succc}{{\rm succ}}
\newcommand{\pred}{{\rm pred}}

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

\begin{document}


\centerline{Homework 11, MORALLY Due May 5} 

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

\begin{enumerate}
\item
(0 points)
What is your name.

\vfill 

\centerline{\bf GO TO THE NEXT PAGE}

\newpage

\item
(30 points) 
There are two coins. 

\begin{itemize}
\item
One is fair so the probability of H and T are both $\frac{1}{2}$. 
\item
One is biased so the probability of H is $\frac{1}{3}$ and the probability of T is $\frac{2}{3}$. 
\end{itemize}

Bill will take one not-quite-at-random!
Here is what Bill does: He picks the fair coin with probability $\frac{9}{10}$
and the biased coin with  probability $\frac{1}{10}$. 

\begin{enumerate}
\item
(15 points)
Bill flips the coins $n$ times and they are all H. 
What is the the probability that the coin is biased (as a function of $n$)? 
\item s
(15 points)
(You might want to write a program for this one.) 
We want a table of $n$ and the probability of bias if there are $n$ H's. 
We want the table to go from $n=1$ to $n=20$. 
The format of the table should be as follows (we only give the first
3 rows and the numbers are made up.).
Real numbers should be to 4 places. 

\begin{tabular}{|c|l|}
\hline
$n$ & the probability of Bias given $H^n$ \cr 
\hline
1   & 0.5101\cr
2   & 0.631 \cr
3   & 0.6799 \cr
\hline
\end{tabular} 
\end{enumerate}

\vfill 

\centerline{\bf GO TO THE NEXT PAGE}

\newpage


\item 
(30 points) 
\begin{enumerate}
\item
(15 points) 
Fill in the following sentence and prove it using the Pigeon hole Principle:
{\it Let $A$ be a subset of $\{1,\ldots,1000\}$ such that $|A|=300$. 
Then there are at least XXX subsets of $A$ that have the same sum.
(Give XXX both as a combinatorial thing like $\ceil{\frac{2^{100}}{87}}$ (thats not
the answer!) and as an actual number like 55 (thats not the answer, or if it is then
thats an accident).} 

\item
(15 points) 
Fill in the following sentence and prove it using the Pigeon hole Principle:
{\it Let $A$ be a subset of $\{-500,\ldots,500\}$ such that $|A|=300$. 
Then there are at least YYY subsets of $A$ that have the same sum.
(Give XXX both as a combinatorial thing like $\ceil{\frac{2^{100}}{87}}$ (thats not
the answer!) and as an actual number like 55 (thats not the answer, or if it is then
thats an accident).} 

\item
(0 points) 
Which is bigger XXX or YYY? Is there an intuition for that? 
\end{enumerate}


\vfill 

\centerline{\bf GO TO THE NEXT PAGE}

\newpage

\item 
(40 points)
Let $a,b,c\ge 2$. 

Let $R_2(a,b)$ be the least number $n$ so that, no matter how you 2-color
(with R,B) the edges of $K_n$ you will either get a RED $K_a$ or a BLUE $K_b$.
(This was called $R(a,b)$ in the lecture.)


Let $R_3(a,b,c)$ be the least number $n$ so that, no matter how you 3-color
(with R,B,G) the edges of $K_n$ you will either get a RED $K_a$ or a BLUE $K_b$
or a GREEN $K_c$. 

\begin{enumerate}

\item
(20 points)
Show that, for all $a,b,\ge 2$, $R_3(a,b,2)=R_2(a,b)$.

\item
(20 points)
Show that, for all $a,b,c\ge 3$, 

$R(a,b,c) \le R(a,b,c-1) + R(a,b-1,c) + R(a-1,b,c)$. 

\end{enumerate}

\item
(0 points but its extra credit)

This problem depends on the Muffin Lecture. 

\begin{enumerate}
\item
Show that $f(22,13)\le \frac{21}{52}$. 
(Uses Half Method)
\item
Show that $f(33,20)\le \frac{41}{100}$. 
(Uses Interval Method) 
\end{enumerate}

MAKE YOUR PROOFS READABLE: use interval diagrams. 

\end{enumerate}

\end{document}