Math 425-4, Fall 1997
Prof. Hochster
EC#16. This problem revisits EC#12.} Let G(n) denote the
number of ways to insert
parentheses described in EC#12}. Show that
G(n+1) = G(1)G(n) + G(2)G(n-1) + ... + G(n)G(1) for n geq 1.
E.g., G(2) = G(1)G(1) = 1(1) = 1, G(3) = G(1)G(2) + G(2)G(1) = 1 + 1 =2,
G(4) = G(1)G(3) + G(2)G(2) + G(3)G(1) = 2 + 1 + 2 = 5,
G(5) = G(1)G(4) + G(2)G(3) + G(3)G(2) + G(4)G(1) = 5 + 2 + 2 + 5 = 14, etc.
Form a power series by using the G(n)'s as coefficients:
f(x) = G(1) + G(2)x + G(3)x^2 + G(4)x^3 + ... .
The function f is called a generating function for the sequence G(1), G(2), G(3), ... . Show that the series converges for |x| < 1. Try to figure out what the function f is, and then use the information to figure out what G(n) is. [No deadline yet]
EC#17. You are a robot with a positronic brain. Your directives are:
(1) Probability rules.
(2) The survival of the species outweighs individual considerations.
(3) Except where (2) is involved, ensure the survival of
human individuals and their quality of life as much as possible.
After a cataclysm the last two hundred and two survivors of the human race have left on two boats. One of the boats contains two hundred people. The other contains only two. Unfortunately, both are sinking in waters so dangerous that there is no chance of survival, and there is only time for you to rescue the occupants of one of the boats. Ordinarily you would rescue the boat containing two hundred people, according to directive (3). However, you believe that all of the people on that boat are men, while the other boat contains one man and one woman. Therefore, directive (2) indicates that you should save the boat with this couple. However, to make things just a bit more complicated, you are only 99% certain of your gender information. That is, for each of the two hundred and two people you have observed, the probability that you are correct about that person's gender is .99, and these probabilities are independent. Moreover, you are concerned about infertility rates. While you know that the people on the boats are all young and healthy, the infertility rate among men and among women is 6%. Assume that if you can rescue a man and a woman from the population of the boats and if they are both fertile, then you will have saved the human race. What is your chance of saving the human race if you save the boat with 200 people? What is your chance if you save the boat with two people? You can then make your decision on the basis of directive (1).
In solving this problem, first give unsimplified answers that are exact, and then calculate answers correct to four decimal places. [10/13]