\documentclass[12pt]{article}
\usepackage{comment}
\usepackage{bm}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{url}
\begin{document}
\centerline{\bf Homework 11 Due May 9 at 9:00AM. NO DEAD CAT}
\centerline{\bf Emily will go over the HW in Recitation on Monday May 9}
\newcommand{\Prob}{{\rm Pr}}
\newcommand{\MOD}{{\rm MOD}}
\newcommand{\PRIMES}{{\rm PRIMES}}
\newcommand{\NSQ}{{\rm NSQ}}
\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}^+}
\newcommand{\NCU}{{\rm NCU}}
\newcommand{\NCUZ}{{\rm NCUZ}}
\begin{enumerate}
\item
(0 points but please DO IT)
What is your name?
\item
(30 points)
In this problem we look at the problem of
dividing 8 muffins for 7 people so that everyone gets $\frac{8}{7}$.
Recall that $f(8,7)$ is the size of the smallest piece in an optimal protocol.
\begin{enumerate}
\item
(5 points)
Use the Floor-Ceiling Formula to get an upper bound on $f(8,7)$.
Express as both a fraction and in decimal up to 3 places.
\item
(15 points)
Use the HALF method to show that $f(8,7)\le \frac{5}{14}$.
You can assume that each muffins is cut into 2 pieces so that there are
16 pieces.
You can assume that nobody gets just 1 share (if they did then they would have
1 muffins, but they should get $\frac{8}{7}>1$).
\item
(10 points)
Give a PROTOCOL that achieves the bound $\frac{5}{14}$.
We give the format we want for the $f(5,3)$ problem.
Do a similar format.
$f(5,3)\ge\frac{5}{12}$:
\begin{enumerate}
\item
Divide 1 muffins $(\frac{6}{12},\frac{6}{12})$.
\item
Divide 4 muffins $(\frac{5}{12},\frac{7}{12})$.
\item
Give 2 students $\{\frac{6}{12}, \frac{7}{12}$, $\frac{7}{12}\}$.
\item
Give 1 students $\{\frac{5}{12}, \frac{5}{12}$, $\frac{5}{12}\}$.
\end{enumerate}
\end{enumerate}
\vfill
\centerline{\bf GOTO NEXT PAGE}
\newpage
\item
(30 points)
Let $ZAN$ be the set
$$\{ a + b\pi \colon a,b\in \Q \}.$$
Let $ZAN[x]$ be the set of polynomials with coefficients in $ZAN$.
Is $ZAN[x]$ countable or uncountable? Justify your answer.
\vfill
\centerline{\bf GOTO NEXT PAGE}
\newpage
\item
(30 points)
Let $BILL$ be the set of functions $f$ such that
\begin{enumerate}
\item
The domain is $\N$
\item
The co-domain is the primes.
\item
The function is strictly increasing.
\end{enumerate}
Is $BILL$ countable or uncountable? Justify your answer.
\vfill
\centerline{\bf GOTO NEXT PAGE}
\newpage
\item
(10 points)
\begin{enumerate}
\item
(0 points)
Listen to {\it Muffin Math} by Bill Gasarch and Lance Fortnow on You Tube:
\url{https://www.youtube.com/watch?v=4xQFlsK7jKg}
or as much of it as you can stand- though its short.
\item
(0 points)
Listen to {\it The Bolzano-Weirstrauss Rap} by {\it The great Steve Sawin}
\url{https://www.youtube.com/watch?v=eM3S74kchoM}
or as much of it as you can stand. The students in Ramsey largely did not get to the end.
How do I feel about that? I am down with that, yes I am down with that.
There are two versions of this song on You Tube- they differ only on graphics.
This one has pictures that help with the math.
\item
(0 points)
Here is my collection of funny songs (at least I think they are funny).
\url{http://www.cs.umd.edu/~gasarch/FUN//funnysongs.html}
One of the categories is math.
Pick three or more songs at random in that category and listen to them.
\item
(10 points)
Are all three better than the Bolzano-Weirstrauss Rap?
(Hint: YES!)
For at least one of the songs give me your thoughts on it.
Tell me your favorite math song from my collection that you listened to.
\end{enumerate}
\end{enumerate}
\end{document}