A friend of mine recently accepted a job offer from a financial firm in New York City. As a friend, I was happy for him! As a senior in college still searching for a job after graduation, I was jealous. But most importantly, as a math major, I was interested in the brain teasers he was asked during his interview. We discussed two brain teasers–the first of which, I will touch on briefly, the second of which, I will discuss in greater detail.
The first question: You are given two ropes and unlimited matches. You cannot fold the ropes in any way–they must stay straight. It takes a rope 15 minutes to burn a quarter of the way through, 30 minutes to burn halfway through, and 60 minutes to burn all the way through, however it may or may not burn uniformly in other areas of the rope. How can you tell when 45 minutes has passed?
Solution: This question was fairly simple and I’ll state the answer. (Somehow) Burn both ends of one rope and one end of the second rope at the same time. When the rope with both ends burning becomes all ash, light the other end of the second rope. When the second rope is all ash, 45 minutes will have passed.
Proof: By the information given, it will clearly take 30 minutes for the rope burning at both ends to turn to ash. Additionally, the second rope will be half gone at the 30 minute mark. Lighting the other end of the second rope when there is only half of it left will mean that the rope will be fully disintegrated within the next 15 minutes. 30 + 15 = 45 minutes.
The second question: You are given 9 stones of equal color, size, shape, texture, etc. However, whereas 8 of the stones are of equal weight, the 9th stone is heavier. You can only measure the difference in weight by using a scale. You are also given a two-pan balance to weigh the stones. You are only able to use this balance twice. Determine the heaviest stone.
Solution: I initially thought a binary-search type algorithm would solve this one. That is, you could take eight of them, put four on one pan, and four on the other. If they show equal balance, then the stone not weighed is the heaviest. If one pan is heavier than the other, toss the other 5 stones and split the remaining four: two on one pan, two on the other. But here is the mistake: when one balance sinks further than the other, you have two stones left and cannot weigh again–how do you tell which one is heavier?
I figured then that the key is in analyzing the last step. We want to get to a point where we measure one stone on each pan. So, let’s analyze the situation a little differently: We have a two pan scale and a table where the stones wait to be weighed. Suppose we have three stones where one is heaviest and we want to find the heaviest one. Place a stone on each of these three places (the left pan, the right pan, and the table). The left pan can either sink lower, or the right pan could, or the pans can stay balanced in which case the heaviest stone is on the table. Therefore, we can find the heaviest of 3 stones with 1 use of the scale. Notice that . Notice further that (clearly). So, with 9 stones and two uses of the scale, place three stones on the left pan, three on the right, and leave three on the table. It is clear that you will be able to decide which six to toss out. Then we are left with three, among which lies that heaviest stone. We know that we can find the heaviest stone in a batch of three with one weigh (described above); we have found the heaviest stone within two weighs!
Now here is where it gets cool. What if we generalized the problem?
Question: Given an -balance pan (I am not sure if these actually exist, but when I say -balance pan, I mean that there are pans to place the stones. Upon placing these stones on the pans, the balance will reveal which stone is heavier) and times we can use the scale, what is the maximum number of stones we can have, among which lies one heavy stone, such that upon using this -balance scale and the scale-use restriction we are guaranteed the ability to find the heaviest stone.
Answer: The maximum number of stones is .
Proof by induction on : Suppose . Then, we can place one stone on each of the pans and leave one stone on the table. If we are to place one more stone on the scale, it would only make sense to also add stones to the remaining pans to increase our chances of finding the one heaviest stone in the lot. But then upon deciding among which bundle of stones the heaviest lies, we then are out of scale-uses and cannot distinguish which is the heaviest stone. Additionally, if we had one stone on each of the pans, and multiple stones resting on the table, we run the risk of having the heaviest stone remain on the table. In this case, we could not distinguish between the different stones. Therefore, we are not guaranteed to find the heaviest stone. Therefore, is truly maximal.
Suppose and that the maximum number of stones we can measure for -scale-uses of an -balance pan is . Place stones on each of the n pans and on the table. Then, we will be able to see which batch of stones has the heaviest. Moreover, we will then have weighs remaining to measure stones, which we know from our induction hypothesis is the maximal number of stones you can have to find the heaviest in uses of the scale. If we were to use any more than stones, it is clear that we would then either not guarantee our ability to find the stone, or try to find the heaviest stone in a pile greater than with -weighs remaining with places to put the stones, which contradicts our induction hypothesis.