6. Optional extra credit: trophy testing. (This is a good problem for those who want a challenge. It will be graded with high standards and not much partial credit, and no regrades will be done.) This past weekend, during the National Championship Celebration at Crisler Center, J.J. Mc- Carthy decided to toss the AFCA Coaches' Trophy to Mike Sainristil. Luckily, Mike caught it (as he does with most footballs that come in his vicinity), but the Michigan athletic depart- ment was very concerned, since this trophy is made of Waterford Crystal and valued at more than $34,130. As a result, it has asked researchers at the University's Materials Science and Engineering department to conduct research on Waterford Crystal. To test its strength, blocks of Waterford Crystal will be dropped from various heights between 1 and n inches (inclusive), for some n of interest. Waterford Crystal is said to have least breaking height (LBH) k if a block of it will break when dropped from a height of k inches or more, but will not break if dropped from any fewer number of inches. If it does not break even when dropped from a height of n inches, we say that the LBH is "more than n," denoted ">n" for convenience. All blocks have the same LBH; the LBH is a property of the material itself, and doesn't vary from block to block. Your task is to determine the LBH of Waterford Crystal. Since it's a very expensive material, you are given just two blocks. Fortunately, any two blocks of Waterford Crystal have the same LBH. Unfortunately, once a block breaks, it is unusable for future testing. It is easy to see that if you had only one block, you would have no choice but to drop the block from 1 inch, then from 2, and so on, until the block breaks (or it doesn't even break from a height of n inches). This is because if you were to skip some height, then you would risk prematurely breaking the block without knowing the exact height from which it would have first broken. But, with two blocks, you can do better! In this problem you will determine the best way to utilize two blocks to determine the LBH, using the fewest number of drops. Instead of expressing the solution as "if I want to determine the LBH among the n+1 possibilities, I can find it using at most d = d(n) drops," it will be cleaner to express the solution inversely, as: "With d drops, I can determine the LBH among n(d) +1 different possibilities, where n = = n(d) is a function of d. (Recall that >n is the extra case representing greater than n.) (a) Suppose you are given two blocks of Waterford Crystal and allowed no more than d drops, from heights of your choice (which can depend on the results of previous drops). What is the largest value of n = n(d) for which you can determine the LBH among the n+1 different possibilities? Describe your method clearly and concisely in English, give a recurrence and base case for n(d), and give an exact (not asymptotic) closed-form solution. Your algorithm should be a recursive divide-and-conquer one, inspired by the following reasoning. When you first drop a block from a certain height, this will effectively divide the problem into two cases: if the block breaks, the LBH is at most that height (and you have only one block left); otherwise, the LBH is strictly larger than that height (and you still have two blocks). So, the first drop serves to divide the problem, and then subsequent drop(s) conquer either lesser heights or greater heights. Solution: (b) Give a short explanation why your algorithm is optimal; i.e., why any algorithm that uses 2 blocks and at most d drops cannot be guaranteed to work for a value larger than n = n(d), for the n(d) you gave in the previous part. A few sentences of intuitive but logically valid explanation suffice here, but if you wish, you're welcome to prove this rigorously. Solution: