Good puzzle: 12 balls, 1 a diff weight, find in 3 uses of pan balance

http://theincidentaleconomist.com/wordpress/the-twelve-balls-problem/

by gronkie • 15 years ago

16 30 15 years ago

phamilton• 15 years ago

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?

russell2• 15 years ago

Two. And now you know I know. ;-)

Shamiq• 15 years ago

Method two? Two methods? I'm so lost.

TomasSedovic2• 15 years ago

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.

shasta2• 15 years ago

Bzz. You can't do what you claim in two weighings (gauranteed)

TomasSedovic2• 15 years ago

Sigh, you're right. Thank's for the correction. I guess it's true that nothing good happens after 2AM (my local time).

tomp2• 15 years ago

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.

sigilyph• 15 years ago

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.

underwater• 15 years ago

Once you realize you can separate the balls/coins into three groups then both problems are pretty easy to solve.

russell2• 15 years ago

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.

seabee3• 15 years ago

If I was HR I'd think you failed the test. (see the comment about 12 balls completed in three weightings, at least)

scotty79• 15 years ago

Two weightings are sufficient to find heavier ball among nine.

StavrosK• 15 years ago

I don't know, 81 balls?

imurray2• 15 years ago

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.

tomp2• 15 years ago

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

imurray2• 15 years ago

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.)

shasta2• 15 years ago

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.

shaggyfrog• 15 years ago

This is also called a "non-adaptive" solution.

16s2• 15 years ago

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.

omnigoat• 15 years ago

That is a different and far easier question. Try and work out the stated question, "heavier or lighter".

thisisfmu4• 15 years ago

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.

seabee3• 15 years ago

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?

16s2• 15 years ago

Odd. I think it's correct... which step is incorrect?

incorrigible• 15 years ago

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.

michaeldhopkins• 15 years ago

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.

strags• 15 years ago

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).

Good puzzle: 12 balls, 1 a diff weight, find in 3 uses of pan balance

Related Stories