DeepT
January 30th, 2008, 03:31 PM
I ran across a puzzle the other day and it's solution made me go "Hmm" because the 'sort' is faster then any sort I know of. The question I have are not about how to solve the puzzle, but on the implications of the solution.
The puzzle is the famous 12 balls puzzle.
You have 12 balls that are all identical, except for an odd one. The odd ball is slightly heavier or lighter then the rest, but you do not know which.
You have a scale which you can use up to 3 times to figure out which ball is the odd one and if it is light or heavy. There are several solutions to this puzzle, so it can be solved in 3 'weighings'.
I am not concerned with the actual solution (http://www.curiouser.co.uk/puzzles/12ballssolution.htm), but what it implies and what I know of sorting algorithms.
First lets consider computer algorithm model with no real restrictions. You are given an array of 12 integers. 11 of the 12 are the same number. The 12th one is higher or lower then the rest. The array is populated randomly.
What in the worst case scenario, what is the least number of comparisons you can take to find the odd ball?
I would think that it would be O(n), or 12 compares. That is pretty good to find a particular item in an unsorted list of 12 numbers.
However, this 'puzzle' solves the problem in 3 compares. Even Log(12) is > 3, so it is beating that time as well.
On the surface, it would seem like this is the Holy Grail of searches. What if it could be applied to the TSP problem or any other expensive search or sort?
What I wonder about this, is how the solution was arrived at and if those mechanics are applicable to other things. For starters, I was wondering how to correlate the number of balls to the number of times you are allowed to weigh.
Is 12 balls the limit for 3 weighings? If so, why? What if you could weigh 4 times, how many balls could you 'search' then? I have not figured out the formula to why it is 12 balls with 3 weighings. I thought of a few candidates but I have no idea which ones might be right. It is kind of hard without having another similar puzzle with more weighings.
Any thoughts on this or am I barking up a tree here?
The puzzle is the famous 12 balls puzzle.
You have 12 balls that are all identical, except for an odd one. The odd ball is slightly heavier or lighter then the rest, but you do not know which.
You have a scale which you can use up to 3 times to figure out which ball is the odd one and if it is light or heavy. There are several solutions to this puzzle, so it can be solved in 3 'weighings'.
I am not concerned with the actual solution (http://www.curiouser.co.uk/puzzles/12ballssolution.htm), but what it implies and what I know of sorting algorithms.
First lets consider computer algorithm model with no real restrictions. You are given an array of 12 integers. 11 of the 12 are the same number. The 12th one is higher or lower then the rest. The array is populated randomly.
What in the worst case scenario, what is the least number of comparisons you can take to find the odd ball?
I would think that it would be O(n), or 12 compares. That is pretty good to find a particular item in an unsorted list of 12 numbers.
However, this 'puzzle' solves the problem in 3 compares. Even Log(12) is > 3, so it is beating that time as well.
On the surface, it would seem like this is the Holy Grail of searches. What if it could be applied to the TSP problem or any other expensive search or sort?
What I wonder about this, is how the solution was arrived at and if those mechanics are applicable to other things. For starters, I was wondering how to correlate the number of balls to the number of times you are allowed to weigh.
Is 12 balls the limit for 3 weighings? If so, why? What if you could weigh 4 times, how many balls could you 'search' then? I have not figured out the formula to why it is 12 balls with 3 weighings. I thought of a few candidates but I have no idea which ones might be right. It is kind of hard without having another similar puzzle with more weighings.
Any thoughts on this or am I barking up a tree here?