%  Homework assignment 7
%  21-110: Problem Solving in Recreational Mathematics, spring 2010
%  Assigned: Monday, April 5, 2010. Due: Monday, April 12, 2010.
%  Brian Kell <bkell@cmu.edu>

\pdfpagewidth=8.5truein \pdfpageheight=11truein
\hsize=6truein \vsize=9truein
\pdfhorigin=1.25truein \pdfvorigin=1truein

% MetaPost stuff
\input supp-pdf
\def\fig#1{\convertMPtoPDF{#1}{1}{1}}
\def\midfig#1{{%
	\setbox0=\hbox{\fig{#1}}%
	\dimen0=0.5\ht0%
	\advance\dimen0 by-0.3\ht\strutbox
	\lower\dimen0\box0%
}}

\font\titlefont=cmbx12
\font\smfont=cmr8

\headline={\hfil}
\footline={\hfil}
\topskip=20pt plus2pt

\newcount\pno  \pno=0
\def\problem{\goodbreak\advance\pno by1 \noindent{\bf Problem~\the\pno.} }
\def\problemno#1. {\goodbreak\noindent{\bf Problem~\hbox{#1}.} }
\def\noskiphint#1\par{\nobreak{\hyphenpenalty=10000\noindent{\it Hint:\/}\enspace#1\par}}
\def\hint#1\par{\nobreak\medskip\noskiphint#1\par}
\def\itemhint#1\par{\nobreak\smallskip\item{}{\it Hint:\/}\enspace#1\par}
\def\solution{\nobreak\medskip\noindent{\bf Solution.} }
\def\part#1{\goodbreak\medskip\indent\llap{#1\enspace}\ignorespaces}
\def\firstpart#1{\nobreak\medskip\indent\llap{#1\enspace}\ignorespaces}

% Pilfered from an example on page 106 of the TeXbook
\def\qed{{\unskip\nobreak\hfil\penalty50
	\hskip1em\hbox{}\nobreak\hfil\hbox{\vrule\vbox to6pt{\hrule\hbox to5.2pt{\hss}\vfil\hrule}\vrule}
	\parfillskip=0pt \finalhyphendemerits=0 \par}}

\def\ipmod#1{\;({\rm mod}\,\,#1)}  % looks better inline than \pmod does

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

\centerline{\titlefont 21-110: Problem Solving in Recreational Mathematics}
\smallskip
\centerline{\bf Homework assignment~7}
\smallskip
\centerline{Assigned Monday, April~5, 2010. Due Wednesday, April~14, 2010.}

\bigskip

\noindent Work at least {\bf FOUR} of the following problems, at least one of
which must be from Part~B. All problems are of equal weight. If you submit
solutions for more than four problems, you will get credit for your best four
(with the proviso that you will get credit for at most three problems from
Part~A).

You are welcome to work with other students, but the solutions you hand~in
should be written in your own words. You are not allowed to see the paper
another student is going to hand~in. If you do collaborate with other students,
list their names. If you use other sources, cite them. Give credit where credit
is due. See the syllabus for more information about academic integrity.

Hints are encrypted with a {\it Caesar cipher}, in which each letter is
replaced by the letter three places ahead in the alphabet, wrapping around to
the beginning if necessary. For example, the letter~{\it A\/} is encrypted
as~{\it D}, and {\it Y\/}~is encrypted as~{\it B}. To decrypt the hints, move
each letter backward three places.

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\centerline{\bf--- Part~A ---}

\nobreak\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem An urn contains five red balls and three yellow balls. Two balls are
drawn from the urn at random, without replacement.

\nobreak\smallskip

\item{(a)} In this scenario, what is the experiment? What is the sample space?

\nobreak\smallskip

\item{(b)} What is the probability that the first ball drawn is red?

\nobreak\smallskip

\item{(c)} What is the probability that at least one of the two balls drawn is
red?

\nobreak\smallskip

\item{(d)} What is the (conditional) probability that the second ball drawn is
red, given that the first ball drawn is red?

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Suppose you and a friend play a game. Two standard, fair, six-sided
dice are thrown, and the numbers appearing on the dice are multiplied together.
If this product is even, your friend gives you a quarter, but if this product
is odd, you must give your friend one dollar.

\nobreak\smallskip

\item{(a)} What is the expected value of this game for you? Round to the
nearest cent.

\nobreak\smallskip

\item{(b)} What is the expected value of this game for your friend? Round to
the nearest cent.

\itemhint Zkdw grhv brxu dqvzhu wr wkh suhylrxv sduw phdq?

\nobreak\smallskip

\item{(c)} Is this game fair? Why or why not?

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Suppose you roll a fair six-sided die six times and record the results
of the rolls in order. What is the probability that you roll a~``3'' at least
five times in a row?

\hint Wkhuh duh wzr zdbv wklv fdq kdsshq. Rqh dssurdfk lv wr wklqn ri lw dv wkh
xqlrq ri wzr hyhqwv dqg xvh lqfoxvlrq--hafoxvlrq.

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (From {\it The Colossal Book of Short Puzzles and Problems\/} by
Martin Gardner.)\enspace A secretary types four letters to four people and
addresses the four envelopes. If she inserts the letters at random, each in a
different envelope, what is the probability that exactly three letters will go
into the right envelopes?

\hint Lq krz pdqb zdbv fdq wklv kdsshq?

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (From {\it The Colossal Book of Short Puzzles and Problems\/} by
Martin Gardner.)\enspace Bill, a student in mathematics, and his friend John,
an English major, usually spun a coin on the bar to see who would pay for each
round of beer. One evening Bill said: ``Since I've won the last three spins,
let me give you a break on the next one. You spin {\it two\/} pennies and I'll
spin one. If you have more heads than I have, you win. If you don't, I win.''

``Gee, thanks,'' said John.

On previous rounds, when one coin was spun, John's probability of winning was,
of course, $1/2$. What are his chances under the new arrangement?

\hint Olvw wkh srvvleoh rxwfrphv.

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\centerline{\bf--- Part~B ---}

\nobreak\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Alice has three fair six-sided dice, colored green, red, and blue, but
these dice are not numbered in the standard way. Instead, they are numbered
like this:
$$\vbox{\halign{\hfil\strut#&&\enspace#\hfil\cr
Green:&5&5&5&2&2&2\cr
Red:&4&4&4&4&4&1\cr
Blue:&3&3&3&3&3&6\cr}}$$
In other words, the green die has three faces labeled~``5'' and three
labeled~``2''; the red die has five faces labeled~``4'' and one labeled~``1'';
and the blue die has five faces labeled~``3'' and one labeled~``6.''

Alice proposes to Bob that they play a little game. ``Here's how it will
work,'' explains Alice. ``In each round, we will each choose one die and
discard the third one. Then we will simultaneously roll our chosen dice.
Whoever rolls the higher number will win a dollar from the other player. (Note
that there can never be a tie.) And since I'm such a nice person, I will let
you choose your die first, before I choose mine.''

\nobreak\smallskip

\item{(a)} Suppose Bob chooses the red die and Alice chooses the green die.
Show that the probability that Alice wins is greater than~$1/2$.

\nobreak\smallskip

\item{(b)} After using the red die for a while and losing more often than not
to Alice's green die, Bob begins to suspect that the odds are not in his favor.
So he chooses the blue die instead, and Alice chooses the red die. Show that
the probability that Alice wins is still greater than~$1/2$.

\nobreak\smallskip

\item{(c)} Bob continues to lose when he plays the blue die against Alice's red
die. He reasons, ``The green die is better than the red die, and the red die is
better than the blue die. So, clearly, I should choose the green die, because
it must be the best of all.'' He takes the green die, and Alice takes the blue
die. Show that the probability that Alice wins is {\it still\/} greater
than~$1/2$.

\nobreak\smallskip

\item{(d)} Alice's dice are an example of {\it nontransitive dice}. How is this
dice game similar to the game of Rock, Paper, Scissors?

\nobreak\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Ten mathematicians are captured by pirates. The pirate captain tells
them, ``I have an unusual custom for dealing with prisoners on my ship.
Tomorrow at dawn I will put all ten of you in a line, blindfolded and facing
the same direction. I will assign each of you either a black hat or a white
hat, depending on the outcome of the flip of a fair coin. (Since there are ten
of you, I will flip the coin ten times, once for each of you.)

``After you have each been given a hat, I will remove your blindfolds. Each of
you will then be able to see the colors of the hats of all the people standing
in front of you in the line, but you will not be able to see your own hat, nor
will you be able to see the hats of the people behind you.

``Then I will begin my questioning. I will start with the person at the back of
the line (who can see all nine of the other hats). I will ask him what color
his hat is. He must announce his guess, either black or white, in a flat,
monotone voice, but loudly enough for all the rest of you to hear. If his guess
is correct, I will allow him to go free. If his guess is incorrect, however, he
will be killed.

``Next, I will move to the second-to-last person in line (who can see eight
other hats), and I will repeat the procedure, moving up the line, until I have
dealt with each of you in turn. By the way, once the hats have been
distributed, you will not be allowed to pass any information among yourselves
except your guesses.

``Well, I suppose it's getting pretty late, and we have a big day tomorrow.
Sleep well, and I'll see you in the morning!''

That night the mathematicians get together and decide that they must devise a
strategy to maximize the expected number of them who will go free. What
strategy should they adopt?

\hint Wkhuh lv dq hdvb vwudwhjb iru zklfk wkh hashfwhg qxpehu ri pdwkhpdwlfldqv
vhw iuhh lv~7.5, exw wkhuh lv d ehwwhu vwudwhjb wkdq wklv.

\hint Wklqn derxw doo wkh lqirupdwlrq d pdwkhpdwlfldq kdv zkhq lw lv klv wxuq
wr jxhvv. Kh nqrzv wkh froruv ri doo wkh kdwv lq iurqw ri klp dqg wkh jxhvvhv
ri doo wkh shrsoh ehklqg klp.

\hint Wub vlpsoliblqj wkh sureohp: Vwduw zlwk mxvw wzr sulvrqhuv, wkhq wkuhh.
Fdq brx hawhqg wkhvh vwudwhjlhv?

\hint Wkhuh lv d vwudwhjb wkdw lv jxdudqwhhg wr vdyh hyhubrqh hafhsw srvvleob
wkh iluvw shuvrq wr jxhvv.

\hint Wkh iluvw shuvrq wr jxhvv pxvw vrphkrz surylgh xvhixo lqirupdwlrq wr
hyhubrqh hovh.

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Suppose the disease diauropunctosis afflicts 1 out of every 5,000
people in the United States. (Assume that the occurrence of the disease is
completely random, so that each person has a 1/5,000 probability of having the
disease, independently of everyone else.) Fortunately, there is a test for
diauropunctosis, which is 99\%~accurate, meaning that 1\% of the people who are
tested receive incorrect results. (Assume that the accuracy of the test is
independent of the occurrence of diauropunctosis; in other words, assume the
test is 99\%~accurate for people who have the disease and 99\%~accurate for
people who do not have the disease.) The city of Pierce, population~1,000,000,
has received a government grant to test all of its citizens for
diauropunctosis.

\nobreak\smallskip

\item{(a)} About how many people in Pierce have diauropunctosis?

\nobreak\smallskip

\item{(b)} Out of the people who have diauropunctosis, about how many will test
positive for the disease? About how many will test negative?

\nobreak\smallskip

\item{(c)} Out of the people who do {\it not\/} have diauropunctosis, about how
many will test positive? About how many will test negative?

\nobreak\smallskip

\item{(d)} Out of all the people who test positive for diauropunctosis, what
percentage actually have the disease?

\nobreak\smallskip

\item{(e)} Think about what your answer to part~(d) means. Suppose you are
tested for diauropunctosis, and the test results come back positive. What is
the (conditional) probability that you actually have diauropunctosis, given
that you tested positive? Explain why receiving a positive result from a test
that is 99\%~accurate does not mean that you have a 99\%~probability of having
the disease.

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

\bye
