Good puzzle: 12 balls, 1 a diff weight, find in 3 uses of pan balance(theincidentaleconomist.com)
theincidentaleconomist.com
Good puzzle: 12 balls, 1 a diff weight, find in 3 uses of pan balance
http://theincidentaleconomist.com/wordpress/the-twelve-balls-problem/
9 comments
I got a variant in an online interview: You have nine balls, one of which is heavier. How many weightings does it take to find the heavy one. I wrote back, "What is the maximum number of balls among which you can find he heavy one in four weightings? If you know the answer to that,then you know I know the answer to your problem." I didn't hear back. I guess HR didnt have a sense of humor.
A better variation. Same problem, but there are 6 balls, 3 colors (red, white and blue), and each pair of a color has one heavy and one light ball, ie there is a set of 3 heavy balls which are red, white, and blue, and a set of 3 light balls which are red, white, and blue. All heavy balls are the same weight, all light balls are the same weight.
What method results in the fewest uses of the balance to separate them properly?
What method results in the fewest uses of the balance to separate them properly?
I recall that the puzzle says "one ball is heavier than the others" not "one ball is a different weight". That being the case, here is the solution:
1. Split the 12 balls into 2 groups. Place the groups on the scale. The heavier group has the heavy ball.
2. Split the 6 balls from the heavy group into 2 groups. Place the groups on the scale. The heavier group has the heavy ball.
3. Take 2 of the remaining 3 balls, place them on the scale. If the scales are even, the heavy ball was left off the scale. If one side of the scale is heavier, that's the heavy ball.
1. Split the 12 balls into 2 groups. Place the groups on the scale. The heavier group has the heavy ball.
2. Split the 6 balls from the heavy group into 2 groups. Place the groups on the scale. The heavier group has the heavy ball.
3. Take 2 of the remaining 3 balls, place them on the scale. If the scales are even, the heavy ball was left off the scale. If one side of the scale is heavier, that's the heavy ball.
That is a different and far easier question. Try and work out the stated question, "heavier or lighter".
this is incorrect. the sum of n>1 balls each of some non-maximum weight needs not be less than another set including the max-weight one.
But if the cardinality of the sets are equal, as is the case in each step of the solution, the set containing the max-weight ball is necessarily heavier. Can you explain further?
consider the following example where the condition "one ball is heavier than the others" holds true but your method yields the wrong solution: {1,10} vs {6,6}
when it is further specified that all remaining balls are of equal weight then your solution cannot be optimal since comparing two thirds yields the required information about the remaining third.
when it is further specified that all remaining balls are of equal weight then your solution cannot be optimal since comparing two thirds yields the required information about the remaining third.
downvoter dumb. no hire.
I didn't downvote you, but I think they object to your overly literal interpretation of "one ball is heavier than the others" given it was contrasted with the original phrasing "one ball is a different weight". This is a math puzzle, not a lateral thinking puzzle.
Not to draw this out further but I do think variations of these make for good interview questions for entry-level people. Here is why:
First, it is trivial to communicate the problem and any moderately competent person will find a solution within a short time frame. Second, it tests how precisely someone takes a problem definition. (In my experience, the kind of person who glances over such details will also tend to make trivial programming mistakes like off-by-ones.) Third, by varying a well-known question slightly you can easily filter out those who have simply learned the "correct" solution from the internet rather than thinking it through.
First, it is trivial to communicate the problem and any moderately competent person will find a solution within a short time frame. Second, it tests how precisely someone takes a problem definition. (In my experience, the kind of person who glances over such details will also tend to make trivial programming mistakes like off-by-ones.) Third, by varying a well-known question slightly you can easily filter out those who have simply learned the "correct" solution from the internet rather than thinking it through.
Odd. I think it's correct... which step is incorrect?
Another variation was presented in my psych class. There are eight coins of unknown weight each. Using a scale twice, identify which one is the false coin. The false coin is lighter than the regular coins, which are all of the same weight.
I found this one less intuitive; if you use the same algorithm as the 12 balls problem, it requires using the scale three times, which is one over the amount of times you're allowed to use the scale.
I found this one less intuitive; if you use the same algorithm as the 12 balls problem, it requires using the scale three times, which is one over the amount of times you're allowed to use the scale.
Once you realize you can separate the balls/coins into three groups then both problems are pretty easy to solve.
Hmm. I solved this a slightly different way. The first step was the same, (ABCD v EFGH), but all subsequent stages were different (for instance, if the scale tilts left, I'll then weight ABCEF against IJKLD). I'm sure there are multiple solutions.
The key is that given there are 24 possibilities, and 3 possible outcomes from the scale, at each stage you must choose balls in order to maximize the amount of information gained.
After the first weighing, you've reduced the possibilities to 8 (whatever the outcome). Since, on the final weighing there are only 3 possible outcomes, you need to devise a second weighing that ensures that the 8 possibilities are split into 3,3,2 - (ie. no result of the second weighing can yield an outcome where more than 3 possibilities remain).
The key is that given there are 24 possibilities, and 3 possible outcomes from the scale, at each stage you must choose balls in order to maximize the amount of information gained.
After the first weighing, you've reduced the possibilities to 8 (whatever the outcome). Since, on the final weighing there are only 3 possible outcomes, you need to devise a second weighing that ensures that the 8 possibilities are split into 3,3,2 - (ie. no result of the second weighing can yield an outcome where more than 3 possibilities remain).
Solution: Give the balls each a different variation in where/when you weight them. eg, Left pan, right pan, not weighed (LRN) for the first ball; LLN for the second ball, LLL for the third ball, and so on. The only exception to the pattern is you must make sure that no pattern mirrors another.
Having read the title, I thought "hey, all you need is 2 measures".
So the final constraint (not mentioned in the title) is to find out whether the anomalous ball is heavier or lighter than the rest.
That's where the third measure comes in.
So the final constraint (not mentioned in the title) is to find out whether the anomalous ball is heavier or lighter than the rest.
That's where the third measure comes in.
No way.
Each experiment gives has 3 possible outcomes: left, right, and balanced. So in 2 experiments you can a maximum of 9 = 3*3 different outcomes. That's not enough to pick one ball out of 12.
If you have 3 experiments, you have 27 outcomes. You need 24 to tell which ball, + heavier/lighter, and 3 outcomes are impossible.
Edit: impossible or redundant, depending of your strategy.
Each experiment gives has 3 possible outcomes: left, right, and balanced. So in 2 experiments you can a maximum of 9 = 3*3 different outcomes. That's not enough to pick one ball out of 12.
If you have 3 experiments, you have 27 outcomes. You need 24 to tell which ball, + heavier/lighter, and 3 outcomes are impossible.
Edit: impossible or redundant, depending of your strategy.
Bzz. You can't do what you claim in two weighings (gauranteed)
Sigh, you're right. Thank's for the correction. I guess it's true that nothing good happens after 2AM (my local time).
Fun fact: it's possible to solve this puzzle even if you have to declare which balls you want weighed against each other in each of the three experiments before you get any results in.
as in: I will weight 'CDEF' against 'ABHI' in the second experiment regardless of what is the result of the first experiment?
If yes, care to give a hint? :P
If yes, care to give a hint? :P
Hint: after your initial weighing, tape some of the balls together (with weightless tape). Bigger hint, label the balls: aaa aab aba abb baa bab bba bbb caa cab cba cbb.
Yes. I'm afraid I'm heading off and can't think of a good way to hint Right Now.
(It's Exercise 4.13 in http://www.inference.phy.cam.ac.uk/mackay/itila/book.html ... and there is a solution and other related weighing problems in there.)
(It's Exercise 4.13 in http://www.inference.phy.cam.ac.uk/mackay/itila/book.html ... and there is a solution and other related weighing problems in there.)
This is also called a "non-adaptive" solution.
My first thought was that the pan was balanced on its center point, so one could solve it in two. Place the balls at the twelve points of the clock, note which way the balls rolled off (e.g., along the 3:00/9:00 axis), and then put those two balls and a normal ball at 12:00, 4:00 and 8:00 to see which way the pan tips and whether the abnormal ball falls off first (heavier) or last (lighter.) However, I see from these comments and the solution on the site that it's actually a scale with two pans so this method does not work.