\documentclass[11pt]{exam}
\usepackage{graphicx}
\usepackage{anysize}
\usepackage{dsfont}
\usepackage{fullpage}
\usepackage{verbatim}
\usepackage{url,amsfonts, amsmath, amssymb, amsthm,color, enumerate, multicol}
\usepackage{placeins}

\printanswers
%\noprintanswers

\begin{document}

\title{ EECS 203: Discrete Mathematics \\
        Group Homework 6 (Spring 2016)}
\date{Due: June 2, 2016}
\author{Answer Key}

\maketitle

\begin{questions}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[5] Each face of a six-sided die is randomly painted red or blue with equal probability.  What is the probability that there is at least one corner of the die where all three sides that make up that corner are of the same color?  Clearly show your work.
%%
\begin{solution}
There are two different approaches we can take: we can do a direct count of how many cubes have a 1-color corner or we can instead invert the problem to compute the number of cubes without a 1-color corner.  Either way, it tends to be much easier to get an accurate count if we split it up by how many sides of a given color there are.

Direct:\\
6 red sides: only 1 cube and it has a 1-color corner.\\
5 red sides: 6 ways to pick the blue side.  All 6 cubes have a 1-color corner.\\
4 red sides: The 2 blue sides can either be next to each other or across from each other.  If they are next to each other, there is a 1-color red corner, while if they are across, there is not.  To count the number of ways we can pick them making them adjacent, we pick a side (6 ways), pick an adjacent side (4 ways), and then note that we counted everything twice (/2) so we have 6*4/2=12 1-color corner cubes\\
3 red sides: After some reasoning, we can conclude that the 3 red sides will either be wrapped around a corner or stretched out in a line.  If they are in a line, there is no 1-color corner, while if they are around a corner, there is.  To count this, we can just pick which corner to wrap the red sides around, giving 8 options.\\
2 red sides: By symmetry this is the same as 4 red sides, 12\\
1 red side: By symmetry this is the same as 5 red sides, 6\\
0 red sides: By symmetry this is the same as 6 red sides, 1\\
In total, this gives 1+6+12+8+12+6+1=46 cubes with a 1-color side out of $2^6=64$, so the probability is $46/64=0.71875$

Indirect: In order to guarantee there is no 1-color corner, we need a pair of opposite sides to be red and another pair of opposite sides to be blue.  When there are only 0 or 1 of a given color, this is therefore impossible, so we need only consider the case of 4 and 2, 3 and 3, and 2 and 4.\\
4 red sides: In order to have the 2 blue sides be opposite each other, we pick one axis of the cube for them to be on.  There are 3 ways to do this, so there are 3 cubes without a 1-color corner.\\
3 red sides: If we have 1 opposite pair of red sides and 1 opposite pair of blue sides, the other pair will be 1 red 1 blue, meaning all 3 can be told apart.  To count this, we pick one pair for red (3), 1 pair for blue from what's left (2), and the remaining pair can be either BR or RB (2), so in total, there are 3*2*2=12 cubes without a 1-color corner\\
2 red sides: By symmetry this is the same as 4 red sides, 3\\
In total this gives 3+12+3=18 cubes with a 1-color side out of $2^6=64$, so the probability is $1-18/64=1-0.28125=0.71875$
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[10] Biased coins:
\begin{enumerate}[a)]
\item Say you have a coin that comes up heads 3/4 of the time and tails only 1/4 of the time. What’s the probability that if you flip the coin 3 times, you’ll get at most 2 heads? [2]
\item Let’s say you have two coins like the one in part “a” of this problem. Flip both of them, one after the other. If they’re the same, forget the result and flip the two coins again. Continue in this fashion until you get two different results. 
\begin{enumerate}[i)]
\item What is the probability that on the first flip where the coins are different, the first of the two coins comes up heads?  Show your work. [4]
\item Use this to explain how you can use any biased coin to simulate a fair coin flip. [1]
\item For the biased coin in part “a”, what is the expected number of flips you must make before you get two different results? [3]
\end{enumerate}
\end{enumerate}
%%
\begin{solution}
\begin{enumerate}[a)]
\item The only way to not get at most 2 heads is to get 3 heads.  This happens $(3/4)^3$ of the time, so the desired probability is $1-(3/4)^3=37/64=0.578125$.
\item \begin{enumerate}[i)]
\item If we want to find x, the probability of getting heads first when the two coins fall differently, we first note $(3/4)(1/4)=3/16$ of the time, we will flip heads then tails, which is a success.  Next, we see that $(1/4)(3/4)=3/16$ of the time, we flip tails then heads, which is a failure.  The remaining $(1/4)^2+(3/4)^2=1/16+9/16=10/16$ of the time, we flip again, which has the same probability of success as when we started, x.  This means $x=3/16*1+3/16*0+10/16*x$.  If we solve for x, we find $x=1/2$.  Alternately, we could just notice we keep throwing out the cases where they are the same, so we can just use the smaller sample space where we have flipped different sides.  This would give $\frac{3/16}{3/16+3/16}=1/2$
\item Given any unfair coin, we can use this procedure of flipping in pairs and discarding cases where they are the same to get the equivalent of a fair coin, an even that happens exactly 1/2 of the time.
\item If I get different results on the first pair of flips, we are done and the number of flips is just 2.  Otherwise, we are basically starting over, but with 2 more flips counted.  This means a clever way to compute the expected value is $E(x)=6/16*2+10/16*(E(x)+2)=32/16+10/16E(x)=2+5/8E(x)$.  Moving all the E(x) to the left, we have $3/8E(x)=2$, and multiplying by 8/3, we get $E(x)=16/3$.

Alternately, we can write it out as a sum.  6/16 of the time, we use 2 flips.  10/16*6/16 of the time, we get the same side first and different sides next, using 4 flips.  $(10/16)^2(6/16)$ of the time we use 6 flips.  Noticing the pattern, we can write the infinite sum as $\sum_{i=1}^\infty (10/16)^{i-1}(6/16)2i=2(6/16)\sum_{i=1}^\infty i(10/16)^{i-1}$.  This is now in the form of one of our known formulas.  We know this is just $2(6/16)(\frac1{(1-10/16)^2})=2(6/16)\frac1{(6/16)^2}=2*16/6=16/3$.
\end{enumerate}
\end{enumerate}
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[7] A couple has twins. The doctor comes into the room after the delivery and places a baby girl into the arms of the mother. He tells her that the other twin is also female. What is the probability that the twins are identical? (Identical twin births are always of the same gender)

Assume:
\begin{enumerate}
\item 20 in 1000 pregnancies result in twins 
\item 3.5 in 1000 pregnancies are of identical twins.  
\item 52.5\% of all children born are males (the rest female)
\end{enumerate}
%%
\begin{solution}
Let T be the event that this pregnancy results in twins, I be the event that this pregnancy results in identical twins, $F_1$ be the event that the first child is female, and $F_2$ be the event that the second child is female.  This means we are given $P(T)=0.02$, $P(I)=0.0035$, and in general, $P(F)=1-0.525=0.475$.  We want to find $P(I|T\cap F_1\cap F_2)$
$$P(I|T\cap F_1\cap F_2)=\frac{P(T\cap I\cap F_1\cap F_2)}{P(T\cap F_1\cap F_2)}=\frac{P(F_1\cap F_2|T\cap I)\cdot P(T\cap I)}{P(T\cap F_1\cap F_2)}$$
$P(T\cap I)=P(T|I)\cdot P(I)=1\cdot 0.0035=0.0035$.  $P(F_1\cap F_2|T\cap I)$ can be thought of in one of two ways: either as picking the gender of the first child, and the second is the same (intended answer) or as a conditional probability where we know they are the same gender.  In the first case, it is just $P(F)=0.475$.  In the second, it comes out to $\frac {P(F)^2}{P(F)^2+(1-P(F))^2}\approx0.45$.
This makes the numerator either $\approx 0.00166$ or $\approx 0.00158$.  I will call this quantity $x$ so I can use it generically and only plug them in at the end.

To divide up the denominator, we will introduce the options that the twins are either identical or not identical:
$$=\frac{x}{P(T\cap I\cap F_1\cap F_2)+P(T\cap \neg I\cap F_1\cap F_2)}=\frac{x}{x+P(F_1\cap F_2|T\cap \neg I)\cdot P(T\cap \neg I)}$$
$P(F_1\cap F_2|T\cap \neg I)$ is not hard, as this is the chance that a pair of fraternal twins are both female.  Each gender is chosen separately, so it is just $P(F)\cdot P(F)\approx 0.226$.  $P(T\cap \neg I)$ is somewhat harder.  The less rigorous (and much less messy) way to do this is to suppose you have 1000 pregnancies in front of you.  of these, 980 are not twins, 3.5 are identical twins, and the remaining 16.5 are fraternal twins.  This means the probability of nonidentical twins is $16.5/1000=0.0165$.  We can plug these values into the equation to get:
$$=\frac{x}{x+0.226\cdot 0.0165}=\frac x{x+0.00372}$$
If you use $x\approx 0.00166$, this comes out to $0.308$, or $30.8\%$.  If you use $x\approx 0.00158$, you get $0.298$, or $29.8\%$.
\end{solution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\question[8] Recurrence relations
\begin{enumerate}[a)]
\item Find a recurrence relation for the number of binary strings of length “n” that do not contain three of the same number in a row.  What is/are the initial conditions? [3]
\item Find a recurrence relation for the number of ternary strings of length “n” that do not contain three of the same number in a row. What is/are the initial conditions? [3]
\item For a and b above, how many strings are there of that type of length 7 or less? [2]
\end{enumerate}
%%
\begin{solution}
\begin{enumerate}[a)]
\item We can break the strings of length n satisfying this requirement into two types: those ending in a double digit and those ending in a single digit (e.g. 011011 ends in a double, while 011001 ends in a single).  The first type can be counted by noting everything up until the last 2 digits must still have no triple in it (there are $a_{n-2}$ of these), and this pair at the end must be opposite to the old last digit (1 choice).  Similarly, we can count all strings ending in a single by noting the first $n-1$ digits must have no triples ($a_{n-1}$ of these) and the new last digit must be opposite the old one (1 option).  Every string satisfying the condition falls into exactly 1 of these categories, so the recurrence relation is just $a_n=a_{n-1}+a_{n-2}$.  The initial conditions are $a_1=2$ and $a_2=4$ (and optionally $a_0=1$)
\item This question is very similar to part a), with the only difference being when we pick a new last digit, it can be either of the digits not equal to the old last digit.  This means there are $2a_{n-1}$ appropriate strings ending in a single and $2a_{n-2}$ appropriate strings ending in a double.  In total, we now have $a_n=2a_{n-1}+2a_{n-2}$.  The initial conditions are $a_1=3$ and $a_2=9$ (and optionally $a_0=1$)
\item This is just $a_7+a_6+a_5+a_4+a_3+a_2+a_1+a_0$.  You could argue whether to include $a_0$ or not, particularly considering it doesn't follow the recurrence relation, but either answer is accepted.  For part a, we have: $a_0=1, a_1=2, a_2=4, a_3=6, a_4=10, a_5=16, a_6=26, a_7=42$, so the total is $42+26+16+10+6+4+2+1$ with the final 1 optional, giving 106 or 107.\\
For part b, we have: $a_0=1, a_1=3, a_2=9, a_3=24, a_4=66, a_5=180, a_6=492, a_7=1344$, so the total is $1344+492+180+66+24+9+3+1$ with the last 1 optional, giving 2118 or 2119.
\end{enumerate}
\end{solution}

\end{questions}

\end{document}