Few Puzzles and Their Analysis
These are a few puzzles from IISC Summer School 2013 which I accidentally stumbled up on. The original PDF can be found here. There may be many other ways of solving the same problem so if you have a better solution to the same problem do comment below and let me know.
You are given a basket of 80 identical balls, out of which all except one have the same weight. What is the minimum number of times you will have to use a given weighing balance before finding the odd ball in the basket?
Here we have to remember that they have not given if the defective ball is lighter or heavier than the rest of the balls. So we have to find out if the ball is heavier or lighter too! Lets split the balls into 3 sections say A = 30, B = 30, and C = 20 and weigh A and B on the weighing balance. This is the first trail and has 3 different outcomes.
Condition when A = B when A == B we can confirm that the defective ball isn’t part of either A or B. Then we can go on and test the section C by splitting it further into three sections and repeat similar process. And finally when you arrive at two balls add them to a section of known balls and weigh them to find the one that isn’t equal.
Condition when A > B or A < B we need to first find which section has the defective ball, so we split C into two and add balls from A and B separately to form new sections. Since we know that the balls from section C do not contain the defective ball we can now shortlist the number of balls to be weighed from this step.
These two conditions can be looped to obtain the final answer. Based on the solution provided by Charles Naumann, and the number of balls in our problem, there are almost 160 possible correct combinations. This problem will be solved later in another post.
Find all integers \(x \neq y\), such that \(x^y = y^x\)
The solution is quite simple and can be obtained by trial and error method. This condition is satisfied only for \(x = 2\) & \(y = 4\) or \(x = 4\) & \(y = 2\)
You are given two identical eggs and have access to a 100-storey building. If an egg does not break on being dropped from a given floor of the building, it will survive a fall from all lower floors; similarly, if an egg breaks on being dropped from a floor, it will break when dropped from all higher floors. You are required to find the highest floor from which an egg on being dropped will not break. Note that an egg once broken cannot be reused; however, an egg which survives a fall can be used again. What will be your strategy to find a solution to this problem? Note that your strategy should require minimum number of egg drops; if there are n floors, what will be the number of egg drops required by your strategy in the worst case.
When I first read this problem the first idea that struck me was a binary tree. The idea was to first test it at half the height and if it breaks the answer must be lower else its on the top half of the building. The problem with this strategy was that there aren’t enough eggs to test it.The solution should use minimum number of eggs drops using two eggs!
For this lets assume that we drop the egg on every 10th floor, so that if the egg breaks on the 10th floor, we can start from the first floor and drop the second egg at every floor from then on. This way we will have a worst case number of drops as 19.
A better solution for this problem can be found here where the worst case number of drops is just 14!