Three problems sent to me by Stephen Johnson Hi Stuart, My coworker has a son attending the Massachusetts Institute of Technology. My coworker's son brings him fun programming and math problems, and here I'd like to share two of them with you. Feel free, if you wish, to share these with others. ================================================= First - Egg Dropping. You are given two fresh, uncooked eggs, and a 100-story building. (Assume you have very sturdy eggs, or else you're on a moon with very low gravity.) Your challenge is to identify exactly what is the highest floor from which an egg can be dropped, without breaking. For example, if an egg breaks when dropped from floor 73 but not from floor 72, you need to distinguish between the two and tell me the highest floor is 72. Rules - you have only two eggs. Once an egg breaks, it can never be used again to test another floor. If an egg doesn't break, it is just as sturdy as it was to begin with. (They don't wear out - they are binary eggs - either perfectly whole or completely broken.) You are asked to complete this task with the minimum number of drop tests. Not knowing ahead of time which is the threshold floor, what should your strategy be, to minimize the "worst case" number of drops, and still identify the highest floor for a safe drop? Finally, generalize the problem - for any number of floors, and also for any number of eggs. The strategy is markedly different if you have 3 eggs, or 4, etc. =================================================== Second - Marble Picking. You are given a bag containing N green marbles, and N red marbles. You cannot look inside the bag, but you are assured there are exactly N of each color. You are allowed to pick out marbles from the bag one at a time and look at them, without replacing them. Once a marble is out, it stays out. For each green marble you pick, you get a point. For each red, you lose a point. What is the strategy for picking out marbles to maximize your number of points? Should you play at all? And second, if you should, at what point should you stop? The answer is different depending on N - when to stop depends on how many points you have (if any), and what the total N is. =================================================== This last one is not from my friend's son - it was in an old pile of my papers. I probably copied it from Dudeney or some other publisher of such puzzles. Sorry I cannot tell you the source. Third - Maximum Quadrilateral Area. Given that the lengths of the 4 sides of a quadrilateral are in arithmetic progression, say S, S+U, S+2U, and S+3U - what is the maximum area that can be enclosed? I have this problem written down, but I have not solved it yet. I ran a few specific examples that seem to indicate there is a single unique solution. I.e. if my examples are correct, it doesn't seem to matter what order the sides are placed. That surprised me. I have to work on it some more. =====================================================