6.042/18.062J Mathematics for Computer Science May 16,2005
Srini Devadas and Eric Lehman
Final Exam
YOUR NAME,
This is an open-notes exam,However,calculators are not allowed,
You may assume all results from lecture,the notes,problem sets,and recitation,
Write your solutions in the space provided,If you need more space,write on the
back of the sheet containing the problem,
Be neat and write legibly,You will be graded not only on the correctness of your
answers,but also on the clarity with which you express them,
GOOD LUCK!
Problem Points Grade Grader
1 15
2 10
3 10
4 10
5 10
6 15
7 10
8 10
9 10
Total 100
Final Exam 2
Problem 1,[15 points] Consider the following sequence of predicates,
Q
1
(x
1
) = x
1
Q
2
(x
1
,x
2
) = x
1
x
2
Q
3
(x
1
,x
2
,x
3
) = (x
1
x
2
)? x
3
Q
4
(x
1
,x
2
,x
3
,x
4
) = ((x
1
x
2
)? x
3
)? x
4
Q
5
(x
1
,x
2
,x
3
,x
4
,x
5
) = (((x
1
x
2
)? x
3
)? x
4
)? x
5
...,.,
Let T
n
be the number of different true/false settings of the variables x
1
,x
2
,...,x
n
for
which Q
n
(x
1
,x
2
,...,x
n
) is true,For example,T
2
= 3 since Q
2
(x
1
,x
2
) is true for 3 different
settings of the variables x
1
and x
2
,
Q
2
(x
1
,x
2
)
T T
T F
F T
F F
x
1
x
2
T
F
T
T
(a) Express T
n+1
in terms of T
n
,assuming n ≥ 1,
Solution,We have,
Q
n+1
(x
1
,x
2
,...,x
n+1
) = Q
n
(x
1
,x
2
,...,x
n
)? x
n+1
If x
n+1
is true,then Q
n+1
is true for all 2
n
settings of the variables x
1
,x
2
,...,x
n
,If
x
n+1
is false,then Q
n+1
is true for all settings of x
1
,x
2
,...,x
n
except for the T
n
settings
that make Q
n
true,Thus,altogether we have,
n
T
n+1
= 2
n
+ 2? T
n
= 2
n+1
T
n
1
(b) Use induction to prove that T
n
=
3
(2
n+1
+ (?1)
n
) for n ≥ 1,You may assume
your answer to the previous part without proof,
n+1
+Solution,The proof is by induction,Let P(n) be the proposition that T
n
= (2
(?1)
n
)/3.
Base case,There is a single setting of x
1
that makes Q
1
(x
1
) = x
1
true,and T
1
=
(2
1+1
+ (?1)
1
)/3 = 1,Therefore,P(0) is true.
Inductive step,For n ≥ 0,we assume P(n) and reason as follows:
T
n+1
= 2
n+1
n
T
n
2
n+1
+ (?1)
= 2
n+1
3
n+1
2
n+2
+ (?1)
=
3
The?rst step uses the result from the previous problem part,the second uses the
induction hypothesis P(n),and the third is simpli?cation,This implies that P(n+1)
is true,By the principle of induction,P(n) is true for all n ≥ 1,
3 Final Exam
Problem 2,[10 points] There is no clock in my kitchen,However,
The faucet drips every 54 seconds after I shut off the water,
The toaster pops out toast every 87 seconds after I plug it in,
I’d like to fry an egg for exactly 141 seconds,My plan is to plug in the toaster and shut
off the faucet at the same instant,I’ll start frying when the faucet drips for the D-th time
and stop frying when the toaster pops for the P -th time,What values of D and P make
this plan work?
D = P =
Reminder,Calculators are not allowed,
Solution,The Pulverizer gives 5 · 87? 8 · 54 = 3,Multiplying by 47 gives,
235 · 87? 376 · 54 = 141
235 · 87 = 141 + 376 · 54?
Thus,I’ll start frying after at drip D = 376 and stop 141 seconds later at pop P = 87,
4 Final Exam
Problem 3,[10 points] Circle either true or false next to each statement below,Assume
graphs are undirected without self-loops or multi-edges,
1. For all n ≥ 3,the complete graph on n vertices has an Euler false
tour,
2. If a graph contains no odd-length cycle,then it is bipartite,true
3. Every non-bipartite graph contains a 3-cycle as a subgraph,false
4. Every graph with a Hamiltonian cycle also has an Euler tour,false
5. There exists a graph with 20 vertices,10 edges,and 5 con- false
nected components,
6. Every connected graph has a tree as a subgraph,true
7. In every planar embedding of a connected planar graph,the true
number of vertices plus the number of faces is greater than the
number of edges,
8. If every girl likes at least 2 boys,then every girl can be false
matched with a boy she likes,
9. If every vertex in a graph has degree 3,then the graph is 4- true
colorable,
10. There exists a six-vertex graph with vertex degrees 0,1,2,3,false
4,and 5.
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
5
C
I
L
Final Exam
Problem 4,[10 points] In the?nal round of the World Cup,16 teams play a single-
elimination tournament,
The teams are called A,B,C,.,,,P,
The tournament consists of a sequence of rounds,
– In each round,the teams are paired up and play matches,
– The losers are eliminated,and the winners advance to the next round,
– The tournament ends when there is only one team left,
For example,three possible single-elimination tournaments are depicted below,
B
A E
E
D
B
E
H
C
D
B
P
E
A
H
M
K
C
J
D
L
B
P
I
E
F
O
A
H
G
M
N
A
I
A
E
M
I
A
C
G
E
O
M
K
I
B
A
C
D
G
H
F
E
P
O
N
M
L
K
J
I
A
A
I
A
E
M
I
A
C
E
G
I
K
M
O
A
B
D
E
M
F
G
H
K
J
Two tournaments are the same if the same matches are played and won by the same teams,
For example,the?rst and second tournaments shown above are the same,but the third
is different,How many different tournaments are possible?
Solution,Suppose that we draw the tournament so that the winning team in each
game is listed above the losing team,Then the ordering of teams on the left completely
determines all matches and winners,Therefore,there are 16! single-elimination tourna-
ments,
Another approach is to use a result from earlier in the course,the number of ways
to pair up 2n people is (2n)!/n! 2
n
,In a single-elimination tournament,we must pair up
16 teams,determine who wins the 8 matches between them,then pair up the 8 winning
teams,detrmine who wins the 4 matches,and so forth,The number of ways in which this
can be done is,
16! 8! 4! 2!
2
8
2
4
2
2
2
1
= 16!
8! 2
8
· ·
4! 2
4
· ·
2! 2
2
· ·
1! 2
1
·
N
O
P
CCC
C
C
C
C
C
C
A
A
H
H
H
H
A
A
A
A
A
A
AAA
H
H
H
H
C
H
H
H
H
H
H
H
H
C
C
C
C
C
A
A
A
A
H
H
H
H
A
A
A
H
H
C
C
C
C
H
H
C
H
H
H
H
H
H
H
H
C
A
A
A
A
H
H
H
H
A
A
H
H
H
H
H
H
H
H
H
H
H
H
6 Final Exam
A?nal alternative is to use the General Product Rule,The champions can be chosen in
16 ways,the other?nalists in 15 ways,the semi-?nalist that played the champions in 14
ways,the other semi-?nalist in 13 ways,and so forth,In all,this gives 16! tournaments
again,
7 Final Exam
Problem 5,[10 points] There are 3 children of different ages,What is the probability that
at least two are boys,given that at least one of the two youngest children is a boy?
Assume that each child is equally likely to be a boy or a girl and that their genders are
mutually independent,A correct answer alone is suf?cient,However,to be eligible for
partial credit,you must include a clearly-labeled tree diagram,
Solution,Let M be the event that there are at least two boys,and let Y be the event
that at least one of the two youngest children is a boy,In the tree diagram below,all edge
probabilities are 1/2,
H
H
HB
B
G
×
×
×
×
1/2
1/2
@
@
@
H
H
H
B
G
B
G
×
×
×
1/2
1/2
A
A
A
A
A
A?
H
H
H
G
B
B
G
×
×
×
1/2
1/2
@
@
@
H
H
H
G
B
G
1/2
1/2
youngest
oldest M Y Prob
Pr(M | Y ) =
Pr(M ∩ Y )
Pr(Y )
1/2
=
3/4
= 2/3
8 Final Exam
Problem 6,[15 points] On the morning of day 1,I put a gray document on my desk,This
creates a stack of height 1,
On each subsequent morning,I insert a white document into the stack at a position se-
lected uniformly at random,For example,the stack might look like this on the evening of
day 5,
Then,on the following morning,I would insert a white document at one of the six posi-
tions indicated above with equal probability,
Let the random variable B
n
be the number of white documents below the gray docu-
ment on day n,
(a) Express Pr (B
n+1
= 0) in terms of Pr (B
n
= 0),
Pr (B
n+1
= 0) =
Solution,
n
Pr (B
n+1
= 0) = Pr (B
n
= 0)
n + 1
(b) Express Pr (B
n+1
= n) in terms of Pr (B
n
= n? 1),
Pr (B
n+1
= n) =
Solution,
n
Pr (B
n+1
= n) = Pr (B
n
= n? 1)
n + 1
9 Final Exam
(c) Express Pr(B
n+1
= k) in terms of Pr(B
n
= k) and Pr(B
n
= k? 1) assuming that
0 < k < n,
Pr(B
n+1
= k) =
Solution,
k
Pr(B
n+1
= k) =
n? k
Pr(B
n+1
= k) + Pr(B
n+1
= k? 1)
n+ 1 n+ 1
10 Final Exam
(d) Use induction to prove that B
n
is uniformly distributed on {0,1,2,...,n? 1},
You may assume your answers to the preceding problem parts without justi?cation,
Solution,We use induction,Let P(n) be the proposition that B
n
is uniformly dis-
tributed on the set {0,1,2,...,n? 1},
Base case,The random variable B
1
is always equal to 0,so it is uniformly distributed
on {0},
Inductive step,Assume that the random variable B
n
is uniformly distributed on the
set {0,1,2,...,n? 1} and consider the random variable B
n+1
,There are three cases,
n
Pr(B
n+1
= 0) = Pr(B
n
= 0)
n+ 1
n 1
= (*)
n+ 1 n
1
=
n+ 1
n
Pr(B
n+1
= n) = Pr(B
n
= n? 1)
n+ 1
n 1
= (*)
n+ 1 n
1
=
n+ 1
k
Pr(B
n+1
= k) =
n? k
Pr(B
n+1
= k) + Pr(B
n+1
= k? 1)
n+ 1 n+ 1
1 k 1
=
n? k
+ (*)
n+ 1 n n+ 1 n
1
=
n+ 1
In each case,the?rst equation comes from the preceding problem parts,We use
the induction hypotheses on the starred lines,The remaining steps are simpl?ca-
tions,This shows that B
n+1
is uniformly distributed,and the claim follows from the
principle of induction,
11 Final Exam
Problem 7,[10 points] Bubba and Stu are shooting at a road sign,They take shots in this
order,
Bubba,Stu,Stu,Bubba,Bubba,Stu,Stu,Bubba,Bubba,Stu,Stu,etc,
With each shot,
Bubba hits the sign with probability 2/5,
Stu hits the sign with probability 1/4,
What is the probability that Bubba hits the sign before Stu? Assume that hits occur mu-
tually independently,You must give a closed-form answer to receive full credit,
Solution,
2
Pr (Bubba hits?rst) = +
5
2
2
3 3 2 3 3 32
+ +
5 4 5 5 4 55
2
2
2
2
2
2
3 3 3 3 2 3 3 3 3 32
+ +
5 4 5 4 5 5 4 5 4 55
..,
2 32
∞
2i
2i?2
2i
2i?1
3 3 3 3
= + +
5 55 4 5 4 5
i=1
∞
2i?2
2 6
3
2i
3 3
= + 1 +
5 25 4 5 5
i=1
∞
i?1
2 6 8
9
i
9
= +
5 255 16 25
i=1
∞
2 6 825
9 9
i
= +
5 255 9 1625
i=1
∞
2 16
81
i
= +
5 15 400
i=1
2 16 1
=
5
+
15 1? 81/400
1
2 16 81
= +
5 15 319
214
=
319
12 Final Exam
Problem 8,[10 points] There are three types of men (A,B,and C),and three types of
women (D,E,and F),Some couples are compatible and others are not,as indicated below,
A B C
D no yes yes
E no no yes
F yes no no
Men and women with the personality types shown below attend a dance,
Men,A A B B B C C C C
Women,D D D E F F F F F
Suppose a pairing of the women and men is selected uniformly at random,
(a) What is the probability that a particular man of type Ais paired with a compatible
woman?
Solution,5/9
(b) What is the expected number of compatible couples?
Solution,Let I
k
be an indicator for the event that the k-th man is paired with a
compatible woman,Then the total number of compatible couples is,
Ex(I
1
+...+I
9
) = Ex(I
1
) +...+ Ex(I
9
)
5 5 3 3 3 4 4 4 4
= + + + + + + + +
9 9 9 9 9 9 9 9 9
35
=
9
13 Final Exam
Problem 9,[10 points] Every Skywalker serves either the light side or the dark side,
The?rst Skywalker serves the dark side,
For n ≥ 2,the n-th Skywalker serves the same side as the (n? 1)-st Skywalker with
probability 1/4,and the opposite side with probability 3/4,
Let d
n
be the probability that the n-th Skywalker serves the dark side,
(a) Express d
n
with a recurrence equation and suf?cient base cases,
Solution,
d
1
= 1
1 3
d
n+1
=
4
· d
n
+
4
· (1? d
n
)
3 1
= d
n
4
2
(b) Give a closed-form expression for d
n
,
Solution,The characteristic equation is x? 1/2 = 0,The only root is x =?1/2,
Therefore,the homogenous solution has the form d
n
= A · (?1/2)
n
,For a particular
solution,we?rst guess d
n
= c,This is indeed a solution for c = 1/2,Therefore,the
complete solution has the form d
n
= 1/2 + A · (?1/2)
n
,Since d
1
= 1,we must have
A =?1/2,Therefore,
n+1
1 1
d
n
= +
2
2
Srini Devadas and Eric Lehman
Final Exam
YOUR NAME,
This is an open-notes exam,However,calculators are not allowed,
You may assume all results from lecture,the notes,problem sets,and recitation,
Write your solutions in the space provided,If you need more space,write on the
back of the sheet containing the problem,
Be neat and write legibly,You will be graded not only on the correctness of your
answers,but also on the clarity with which you express them,
GOOD LUCK!
Problem Points Grade Grader
1 15
2 10
3 10
4 10
5 10
6 15
7 10
8 10
9 10
Total 100
Final Exam 2
Problem 1,[15 points] Consider the following sequence of predicates,
Q
1
(x
1
) = x
1
Q
2
(x
1
,x
2
) = x
1
x
2
Q
3
(x
1
,x
2
,x
3
) = (x
1
x
2
)? x
3
Q
4
(x
1
,x
2
,x
3
,x
4
) = ((x
1
x
2
)? x
3
)? x
4
Q
5
(x
1
,x
2
,x
3
,x
4
,x
5
) = (((x
1
x
2
)? x
3
)? x
4
)? x
5
...,.,
Let T
n
be the number of different true/false settings of the variables x
1
,x
2
,...,x
n
for
which Q
n
(x
1
,x
2
,...,x
n
) is true,For example,T
2
= 3 since Q
2
(x
1
,x
2
) is true for 3 different
settings of the variables x
1
and x
2
,
Q
2
(x
1
,x
2
)
T T
T F
F T
F F
x
1
x
2
T
F
T
T
(a) Express T
n+1
in terms of T
n
,assuming n ≥ 1,
Solution,We have,
Q
n+1
(x
1
,x
2
,...,x
n+1
) = Q
n
(x
1
,x
2
,...,x
n
)? x
n+1
If x
n+1
is true,then Q
n+1
is true for all 2
n
settings of the variables x
1
,x
2
,...,x
n
,If
x
n+1
is false,then Q
n+1
is true for all settings of x
1
,x
2
,...,x
n
except for the T
n
settings
that make Q
n
true,Thus,altogether we have,
n
T
n+1
= 2
n
+ 2? T
n
= 2
n+1
T
n
1
(b) Use induction to prove that T
n
=
3
(2
n+1
+ (?1)
n
) for n ≥ 1,You may assume
your answer to the previous part without proof,
n+1
+Solution,The proof is by induction,Let P(n) be the proposition that T
n
= (2
(?1)
n
)/3.
Base case,There is a single setting of x
1
that makes Q
1
(x
1
) = x
1
true,and T
1
=
(2
1+1
+ (?1)
1
)/3 = 1,Therefore,P(0) is true.
Inductive step,For n ≥ 0,we assume P(n) and reason as follows:
T
n+1
= 2
n+1
n
T
n
2
n+1
+ (?1)
= 2
n+1
3
n+1
2
n+2
+ (?1)
=
3
The?rst step uses the result from the previous problem part,the second uses the
induction hypothesis P(n),and the third is simpli?cation,This implies that P(n+1)
is true,By the principle of induction,P(n) is true for all n ≥ 1,
3 Final Exam
Problem 2,[10 points] There is no clock in my kitchen,However,
The faucet drips every 54 seconds after I shut off the water,
The toaster pops out toast every 87 seconds after I plug it in,
I’d like to fry an egg for exactly 141 seconds,My plan is to plug in the toaster and shut
off the faucet at the same instant,I’ll start frying when the faucet drips for the D-th time
and stop frying when the toaster pops for the P -th time,What values of D and P make
this plan work?
D = P =
Reminder,Calculators are not allowed,
Solution,The Pulverizer gives 5 · 87? 8 · 54 = 3,Multiplying by 47 gives,
235 · 87? 376 · 54 = 141
235 · 87 = 141 + 376 · 54?
Thus,I’ll start frying after at drip D = 376 and stop 141 seconds later at pop P = 87,
4 Final Exam
Problem 3,[10 points] Circle either true or false next to each statement below,Assume
graphs are undirected without self-loops or multi-edges,
1. For all n ≥ 3,the complete graph on n vertices has an Euler false
tour,
2. If a graph contains no odd-length cycle,then it is bipartite,true
3. Every non-bipartite graph contains a 3-cycle as a subgraph,false
4. Every graph with a Hamiltonian cycle also has an Euler tour,false
5. There exists a graph with 20 vertices,10 edges,and 5 con- false
nected components,
6. Every connected graph has a tree as a subgraph,true
7. In every planar embedding of a connected planar graph,the true
number of vertices plus the number of faces is greater than the
number of edges,
8. If every girl likes at least 2 boys,then every girl can be false
matched with a boy she likes,
9. If every vertex in a graph has degree 3,then the graph is 4- true
colorable,
10. There exists a six-vertex graph with vertex degrees 0,1,2,3,false
4,and 5.
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
5
C
I
L
Final Exam
Problem 4,[10 points] In the?nal round of the World Cup,16 teams play a single-
elimination tournament,
The teams are called A,B,C,.,,,P,
The tournament consists of a sequence of rounds,
– In each round,the teams are paired up and play matches,
– The losers are eliminated,and the winners advance to the next round,
– The tournament ends when there is only one team left,
For example,three possible single-elimination tournaments are depicted below,
B
A E
E
D
B
E
H
C
D
B
P
E
A
H
M
K
C
J
D
L
B
P
I
E
F
O
A
H
G
M
N
A
I
A
E
M
I
A
C
G
E
O
M
K
I
B
A
C
D
G
H
F
E
P
O
N
M
L
K
J
I
A
A
I
A
E
M
I
A
C
E
G
I
K
M
O
A
B
D
E
M
F
G
H
K
J
Two tournaments are the same if the same matches are played and won by the same teams,
For example,the?rst and second tournaments shown above are the same,but the third
is different,How many different tournaments are possible?
Solution,Suppose that we draw the tournament so that the winning team in each
game is listed above the losing team,Then the ordering of teams on the left completely
determines all matches and winners,Therefore,there are 16! single-elimination tourna-
ments,
Another approach is to use a result from earlier in the course,the number of ways
to pair up 2n people is (2n)!/n! 2
n
,In a single-elimination tournament,we must pair up
16 teams,determine who wins the 8 matches between them,then pair up the 8 winning
teams,detrmine who wins the 4 matches,and so forth,The number of ways in which this
can be done is,
16! 8! 4! 2!
2
8
2
4
2
2
2
1
= 16!
8! 2
8
· ·
4! 2
4
· ·
2! 2
2
· ·
1! 2
1
·
N
O
P
CCC
C
C
C
C
C
C
A
A
H
H
H
H
A
A
A
A
A
A
AAA
H
H
H
H
C
H
H
H
H
H
H
H
H
C
C
C
C
C
A
A
A
A
H
H
H
H
A
A
A
H
H
C
C
C
C
H
H
C
H
H
H
H
H
H
H
H
C
A
A
A
A
H
H
H
H
A
A
H
H
H
H
H
H
H
H
H
H
H
H
6 Final Exam
A?nal alternative is to use the General Product Rule,The champions can be chosen in
16 ways,the other?nalists in 15 ways,the semi-?nalist that played the champions in 14
ways,the other semi-?nalist in 13 ways,and so forth,In all,this gives 16! tournaments
again,
7 Final Exam
Problem 5,[10 points] There are 3 children of different ages,What is the probability that
at least two are boys,given that at least one of the two youngest children is a boy?
Assume that each child is equally likely to be a boy or a girl and that their genders are
mutually independent,A correct answer alone is suf?cient,However,to be eligible for
partial credit,you must include a clearly-labeled tree diagram,
Solution,Let M be the event that there are at least two boys,and let Y be the event
that at least one of the two youngest children is a boy,In the tree diagram below,all edge
probabilities are 1/2,
H
H
HB
B
G
×
×
×
×
1/2
1/2
@
@
@
H
H
H
B
G
B
G
×
×
×
1/2
1/2
A
A
A
A
A
A?
H
H
H
G
B
B
G
×
×
×
1/2
1/2
@
@
@
H
H
H
G
B
G
1/2
1/2
youngest
oldest M Y Prob
Pr(M | Y ) =
Pr(M ∩ Y )
Pr(Y )
1/2
=
3/4
= 2/3
8 Final Exam
Problem 6,[15 points] On the morning of day 1,I put a gray document on my desk,This
creates a stack of height 1,
On each subsequent morning,I insert a white document into the stack at a position se-
lected uniformly at random,For example,the stack might look like this on the evening of
day 5,
Then,on the following morning,I would insert a white document at one of the six posi-
tions indicated above with equal probability,
Let the random variable B
n
be the number of white documents below the gray docu-
ment on day n,
(a) Express Pr (B
n+1
= 0) in terms of Pr (B
n
= 0),
Pr (B
n+1
= 0) =
Solution,
n
Pr (B
n+1
= 0) = Pr (B
n
= 0)
n + 1
(b) Express Pr (B
n+1
= n) in terms of Pr (B
n
= n? 1),
Pr (B
n+1
= n) =
Solution,
n
Pr (B
n+1
= n) = Pr (B
n
= n? 1)
n + 1
9 Final Exam
(c) Express Pr(B
n+1
= k) in terms of Pr(B
n
= k) and Pr(B
n
= k? 1) assuming that
0 < k < n,
Pr(B
n+1
= k) =
Solution,
k
Pr(B
n+1
= k) =
n? k
Pr(B
n+1
= k) + Pr(B
n+1
= k? 1)
n+ 1 n+ 1
10 Final Exam
(d) Use induction to prove that B
n
is uniformly distributed on {0,1,2,...,n? 1},
You may assume your answers to the preceding problem parts without justi?cation,
Solution,We use induction,Let P(n) be the proposition that B
n
is uniformly dis-
tributed on the set {0,1,2,...,n? 1},
Base case,The random variable B
1
is always equal to 0,so it is uniformly distributed
on {0},
Inductive step,Assume that the random variable B
n
is uniformly distributed on the
set {0,1,2,...,n? 1} and consider the random variable B
n+1
,There are three cases,
n
Pr(B
n+1
= 0) = Pr(B
n
= 0)
n+ 1
n 1
= (*)
n+ 1 n
1
=
n+ 1
n
Pr(B
n+1
= n) = Pr(B
n
= n? 1)
n+ 1
n 1
= (*)
n+ 1 n
1
=
n+ 1
k
Pr(B
n+1
= k) =
n? k
Pr(B
n+1
= k) + Pr(B
n+1
= k? 1)
n+ 1 n+ 1
1 k 1
=
n? k
+ (*)
n+ 1 n n+ 1 n
1
=
n+ 1
In each case,the?rst equation comes from the preceding problem parts,We use
the induction hypotheses on the starred lines,The remaining steps are simpl?ca-
tions,This shows that B
n+1
is uniformly distributed,and the claim follows from the
principle of induction,
11 Final Exam
Problem 7,[10 points] Bubba and Stu are shooting at a road sign,They take shots in this
order,
Bubba,Stu,Stu,Bubba,Bubba,Stu,Stu,Bubba,Bubba,Stu,Stu,etc,
With each shot,
Bubba hits the sign with probability 2/5,
Stu hits the sign with probability 1/4,
What is the probability that Bubba hits the sign before Stu? Assume that hits occur mu-
tually independently,You must give a closed-form answer to receive full credit,
Solution,
2
Pr (Bubba hits?rst) = +
5
2
2
3 3 2 3 3 32
+ +
5 4 5 5 4 55
2
2
2
2
2
2
3 3 3 3 2 3 3 3 3 32
+ +
5 4 5 4 5 5 4 5 4 55
..,
2 32
∞
2i
2i?2
2i
2i?1
3 3 3 3
= + +
5 55 4 5 4 5
i=1
∞
2i?2
2 6
3
2i
3 3
= + 1 +
5 25 4 5 5
i=1
∞
i?1
2 6 8
9
i
9
= +
5 255 16 25
i=1
∞
2 6 825
9 9
i
= +
5 255 9 1625
i=1
∞
2 16
81
i
= +
5 15 400
i=1
2 16 1
=
5
+
15 1? 81/400
1
2 16 81
= +
5 15 319
214
=
319
12 Final Exam
Problem 8,[10 points] There are three types of men (A,B,and C),and three types of
women (D,E,and F),Some couples are compatible and others are not,as indicated below,
A B C
D no yes yes
E no no yes
F yes no no
Men and women with the personality types shown below attend a dance,
Men,A A B B B C C C C
Women,D D D E F F F F F
Suppose a pairing of the women and men is selected uniformly at random,
(a) What is the probability that a particular man of type Ais paired with a compatible
woman?
Solution,5/9
(b) What is the expected number of compatible couples?
Solution,Let I
k
be an indicator for the event that the k-th man is paired with a
compatible woman,Then the total number of compatible couples is,
Ex(I
1
+...+I
9
) = Ex(I
1
) +...+ Ex(I
9
)
5 5 3 3 3 4 4 4 4
= + + + + + + + +
9 9 9 9 9 9 9 9 9
35
=
9
13 Final Exam
Problem 9,[10 points] Every Skywalker serves either the light side or the dark side,
The?rst Skywalker serves the dark side,
For n ≥ 2,the n-th Skywalker serves the same side as the (n? 1)-st Skywalker with
probability 1/4,and the opposite side with probability 3/4,
Let d
n
be the probability that the n-th Skywalker serves the dark side,
(a) Express d
n
with a recurrence equation and suf?cient base cases,
Solution,
d
1
= 1
1 3
d
n+1
=
4
· d
n
+
4
· (1? d
n
)
3 1
= d
n
4
2
(b) Give a closed-form expression for d
n
,
Solution,The characteristic equation is x? 1/2 = 0,The only root is x =?1/2,
Therefore,the homogenous solution has the form d
n
= A · (?1/2)
n
,For a particular
solution,we?rst guess d
n
= c,This is indeed a solution for c = 1/2,Therefore,the
complete solution has the form d
n
= 1/2 + A · (?1/2)
n
,Since d
1
= 1,we must have
A =?1/2,Therefore,
n+1
1 1
d
n
= +
2
2
