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