wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> 12 balls - variation
        
(Message started by: redPEPPER on Apr 11^th, 2003, 5:44am)

Title: 12 balls - variation
Post by redPEPPER on Apr 11^th, 2003, 5:44am

quoted from the hard riddles library:

You have 12 identical-looking balls. One of these balls has a different weight from all the others. You also have a two-pan balance for comparing weights. Using the balance in the smallest number of times possible, determine which ball has the unique weight, and also determine whether it is heavier or lighter than the others.

It's one of my fave riddles ever, maybe because it's one of the first really challenging riddles I ever tried to solve (took me years too!)

Anyway. There are probably classic solutions of this one in the forum, but I'm proposing a variation:

The balls are numbered from 1 to 12 for practical reasons. The problem is the same: use the balance the smallest number of times to find the unique ball, and wether it's heavier or lighter than the other balls. Except that this time you have to plan the weighings in advance. i.e. you can't use the results of a weighing to prepare the next weighing. You only get the results at the end of all your weighings and have to deduce the solution from these results.

How many weighings do you need?

I'm not sure this should be in hard though, but the original riddle was there, so...

Title: Re: 12 balls - variation
Post by cho on Apr 11^th, 2003, 6:47am

It can be done in [hide] 4 [/hide] weighings.

Title: Re: 12 balls - variation
Post by cho on Apr 11^th, 2003, 7:39am

My mistake. It can be done in [hide]3[/hide] weighings.

Title: Re: 12 balls - variation
Post by cho on Apr 11^th, 2003, 8:29am

[hide]The solution is extendable, so with four weighings you can easily solve for 39 balls. [/hide]

Title: Re: 12 balls - variation
Post by LZJ on Apr 12^th, 2003, 5:26am

Seriously, I don't think this question should be in the Hard Section...perhaps Medium would be more suitable...

The 1st step is to group the coins into 3 groups...

Title: Re: 12 balls - variation
Post by mistysakura on Apr 12^th, 2003, 10:42pm

on 04/12/03 at 05:26:54, LZJ wrote:

Seriously, I don't think this question should be in the Hard Section...perhaps Medium would be more suitable...

The 1st step is to group the coins into 3 groups...

Um... Are you sure you're talking about the right riddle? I don't see any coins in this one.

Title: Re: 12 balls - variation
Post by LZJ on Apr 13^th, 2003, 12:57am

Oops, I meant balls, of course, but when I first did this puzzle, it was coins instead of balls... :-[

Title: Re: 12 balls - variation
Post by redPEPPER on Apr 14^th, 2003, 7:04am

Balls or coins, aren't you replying to the original riddle? My variation doesn't particularly call for grouping balls, although I guess you could...

Title: Re: 12 balls - variation
Post by mistysakura on Apr 17^th, 2003, 4:45pm

Here's what I found.
[hide] L denotes left, R denotes Right (obvious)
Weighing 1 - L. 5, 11, 6, 7 vs. R. 8, 10, 9, 12
Weighing 2 - L. 2, 4, 12, 9 vs. R. 3, 8, 10, 11
Weighing 3 - L. 1, 6, 10, 12 vs. R. 4, 3, 7, 9

(L: Left side is heavier, R: Right side is heavier, E: Both sides are even, h: Ball is heavier, l: ball is lighter0)
Weighings Ball
EEL 1h
EER 1l
ELE 2h
ERE 2l
ERR 3h
ELL 3l
ELR 4h
ERL 4l
LEE 5h
REE 5l
LEL 6h
RER 6l
LER 7h
REL 7l
RRE 8h
LLE 8l
RLR 9h
LRL 9l
RRL 10h
LLR 10l
LRE 11h
RLE 11l
RLL 12h
LRR 12l

First, list all possibilities.
I realized EEE couldn’t be used because you couldn’t find out whether the ball was heavier or lighter if it never went on the scales. For the rest, I paired them up with their reversal (e.g. ERL – ELR), and assigned a random number and heavy/light value for each one in the pair.
i.e. EEL 1h EER 1l ELE 2h etc. I had a 13th pair, RRR/LLL, that I numbered 13.
Then I put them onto the scales, and realized every single time there were more balls on one side than the other, and there were an odd number of balls in each weighing anyway. So, I took off 13 (just for convenience), did a few heavy/light swaps by brute force, and came up with the above answer. [/hide]

Title: Re: 12 balls - variation
Post by redPEPPER on Apr 18^th, 2003, 3:58am

That works, Mistysakura. Well done!
Now:
[hide]
There are three possibilities that you didn't use. You explained why you didn't use EEE. But you didn't use LLL nor RRR. Could you use these to identify a 13th ball in the set?

If yes, how?

If no, why not? And what would you need to be able to do it?[/hide]

Title: Re: 12 balls - variation
Post by NickH on Apr 18^th, 2003, 4:40am

See The Oddball Problem (http://www.cut-the-knot.com/blue/OddballProblem1.shtml) and Odd Coin Problems (http://www.cut-the-knot.com/blue/OddCoinProblems.shtml).

Title: Re: 12 balls - variation
Post by Gerd on Apr 30^th, 2003, 4:25am

I think there's a way to make LLL and RRR possible. But then you will miss 2 other combinations (in this case RLR and LRL).

Here are the 3 weighings:

A: 5-2-8-11 --- 10-6-3-4
B: 5-4-12-11 --- 1-6-7-8
C: 1-2-3-4 --- 9-11-6-7

With No. 6 three times on the right side you get RRR (heavier) and LLL (lighter).
Because you miss 2 other weighing-results, you are not able to weigh 13 balls (overall you only have 24 possible results). :)

Title: Re: 12 balls - variation
Post by Rujith de Silva on Jun 11^th, 2003, 8:53am

Three weighings, each with three outcomes, can distinguish among 3^3 =
27 different situations. With twelve balls, there are 2 x 12 + 1 = 25
situations, which is eminently doable. With thirteen balls, there
would be 2 x 13 + 1 = 27 situations, which also looks like it should
be doable in three weighings. But it cannot, for the following
reason. The three possible outcomes of the first weighing must
partition the 27 possibilities into equal size groups, each with nine
possibilities, for each group to be further disambiguated in two
additional weighings. Suppose the first weighing had four balls on
each side. The weighing would partition the 27 different
possibilities into {8, 8, 11}, where 11 is obtained if the weighing
balanced. So that doesn't work. Similarly, suppose the first
weighing had five balls on each side. This would yield the partition
{10, 10, 7}, so that doesn't work either. In fact, the first weighing
would always yield a partition whose size is (2 x #balls weighed). So
there is no way to obtain the desired partition of {9, 9, 9}.
- Rujith.

Title: Re: 12 balls - variation
Post by redPEPPER on Jun 11^th, 2003, 3:24pm

Nice demonstration.

Actually there's a way to obtain the desired partition {9,9,9} but you need something. It's obvious now.

Title: Re: 12 balls - variation
Post by Rujith de Silva on Jun 12^th, 2003, 7:42am

Hi redPepper, that's a nice extension to the problem! So the size of
a partition is NOT (2 x #balls weighed), but rather (#left-side
candidate balls + #right-side candidate balls), and that can be made
equal to nine, given the "something" to which you referred. - Rujith.

Title: Re: 12 balls - variation
Post by TimMann on Oct 14^th, 2003, 1:13am

I notice Icarus listed the extension to this puzzle under "unsolved," presumably because no one was explicit about what the "something" is. It is [hide]a 14th ball that is known to be of standard weight[/hide]. Well, or if it's something other than that, please tell me! :)

Trivia: I independently invented this variant some time before 1987, but none of my friends thought it made a nice puzzle (nor did I), so I don't think I ever posted it anywhere public.

Title: Re: 12 balls - variation
Post by Rujith de Silva on Oct 14^th, 2003, 8:38am

Yes, the necessary addition is [hide] a fourteenth ball of known good weight. Then the following three weighings work:
12349 5678x
12569 3ABDx
167Dx 258BC
Where x denotes the known good ball, and the thirteen unknown balls are numbered 1-9 and A-D. Note that every weighing must include the x ball. [/hide] I found this solution by trial and error with a little Perl program to evaluate each attempt, and tell me which balls failed to be disambiguated.

Title: Re: 12 balls - variation
Post by Icarus on Oct 14^th, 2003, 7:57pm

Thanks. When I made my list, I did not have the time to study each problem in detail, so it was easy to miss even "obvious" answers. (Besides which, I have been given to some mental laziness of late. :P)

Title: Re: 12 balls - variation
Post by vsmurali on Oct 6^th, 2005, 6:17am

The main twist to the puzzle could be, we dont know if the odd ball/coin is heavier or lighter. Then we would need this "additional" weighing to confirm our solution.
Here's mine within three weighings

a) In a balance weigh 3 coins either side
case 1:
both pans are same. so remaining 6 has the odd coin.

case 2:
one of the pans go up/down. Even now we dont know which three is correct because the odd coin might be lighter or heavier

Replace one pan with other set of 3 coins from the remaining 6.
Case 1:
If both pans are still same , then the three coins unweighed has the odd coin
if not the new set of coins in the pan has the odd coin.

Case 2:
If pans are same the 3 coins replaced the previous time has the odd coin. If there is a shift of balance set of coins on the pan from previous weighing has the odd coin.

Either way we have nailed down the three coins with odd coin with 2 weighings. Also depending on the behaviour of the new coin pan we can also gauge if the odd coin is lighter or heavier.(it is important to deduce this )

Now with this defective set, weigh one coin against each other. shift of balance would point to the coin (based on our earlier deduction of if the odd coin is heavy or light) or the unweighed coin is the odd one

Title: Re: 12 balls - variation
Post by Nigel_Parsons on Oct 25^th, 2005, 12:23am

VSMURALI:
Your system fails to complete the problem.
If the two pans balance after the first weighing, you know that the odd coin/ball is in the remaining 6.
You then go on to replace 3 of the originals with 3 of the remaining six. If this balances, you are left with three coins/balls, one of which is the odd one, but as you don't yet know whether the odd one is heavy/light you cannot identify it on a third weighing.
i.e. if the pans balance then the remaining coin/ball is the the odd one (whether heavy/light) but if the pans do not balance, one of the balls/coins on the balance is the odd one, but you don't know which, nor whether heavy/light

Nigel

Title: Re: 12 balls - variation
Post by Raja Reddy on Oct 28^th, 2005, 1:31pm

I noticed someone has a solution, but it looks like they brute forced it so I thought I would post my solution too, and the proof.

The key insight is that if you have X unknown coins, then you CANNOT eliminate more than cieling(2X/3) coins on any given weighing. Further, using information theory, you need to eliminate at least floor(2X/3) possibilities on each weighing. I.e. 24 to 8. From 8 to either 2 or 3. And 2,3 to 1.

My solution:

A. 1,2,3,4 vs 5,6,7,8
B. 9,10,11,1 vs 2,3,5,6
C. 9,7,5,2 vs 10,12,8,6

Here is the proof:

Assume you have coins 1,2,3,4,5,6,8,9,10,11, and 12.

WLOG your first weighing is 1,2,3,4 vs 5,6,7,8.

1. If they were equal, then you are left with 9,10,11,12, but do not know whether the misfit is light or heavy (leaving you 8 possibilities and having to eliminate at least 5 on the next weighing).

The only way to determine the misfit is in the following manner:

9,10,11,N vs N,N,N,N (where N means normal)
9,N,N,N vs 10,12,N,N

From this, we know that the second weighing is

9,10,11,? vs ?,?,?,? (without using 12)

and the third weighing is

9,?,?,? vs 10,12,?,?

2. The first weighing was unequal. WLOG, assume 1,2,3,4 were light and 5,6,7,8 were heavy.

At this point, you have 8 possible misfits again. Information theory tells you that you have to eliminate at least 5 coins on the next weighing.

To do this, weigh

N,N,N,1 vs 2,3,5,6

2.1 N,N,N,1 = 2,3,5,6. Then either 4 is light, or 7,8 are heavy. Notice that we have eliminated 5 coins! The next weighing is:

N,N,N,7 vs N,N,N,8

2.2 N,N,N,1 < 2,3,5,6. Then 1 is light or 5,6 are heavy. Again, we have eliminated 5 coins and the next weighing is:

N,N,5,N vs N,N,6,N

2.3 N,N,N,1 > 2,3,5,6. Then 2 or 3 is light. Here we have eliminated 6 balls and the next weighing is:

N,N,N,2 vs N,N,N,N

If you combine everything above, you get the following weighings:

A. 1,2,3,4 vs 5,6,7,8
B. 9,10,11,1 vs 2,3,5,6
C. 9,7,5,2 vs 10,12,8,6

Title: Re: 12 balls - variation
Post by Grimbal on Oct 28^th, 2005, 2:23pm

Here is my solution:

There is a trick to discriminate 3 equal groups in 2 weighings, finding which group has a wrong weight and which direction is the bias. Just rotate the groups.

First weigh A vs B leaving C
then weigh B vs C leaving A.

If either weighing balances, the third group has the bad ball and the other weighing tells in which direction, heavy or light. If both weighings balance, B is wrong and the direction of the weighings tell in which direction.

So, start with 3 groups A, B, C of 3 balls and 3 groups a, b, c of 1.

1st weighing: Aa vs Bb leave Cc.
(rotate A,B,C)
2nd weighing: Ba vs Cb leave Ac.

If something changes, the bad ball was moved: it is among A,B,C and you can tell if it is heavy or light. You have 1 more weighing to find the wrong weigh among the 3.
3rd weighing: A1 vs A2 leaving A3
(or the same with the B' s or C's, whichever was bad)

If nothing changes, the wrong weigh is among a,b,c. The result of weighing a vs b (leaving c) is known since A,B,C all have equal weight. You can rotate a,b,c and find which of a,b,c is wrong.
3rd weighing: b vs c, leaving a on the side.

The second trick is that for the 3rd weighing you can just combine all the 3rd weighings because for each case we need to do, the other cases will balance. If you know the bad ball is among a,b,c, you can add balls from A,B,C on the pans, it won't change the result.

So, here is a program for 3 weighings:
balls are labeled A1 A2 A3 B1 B2 B3 C1 C2 C3 a b c
1. A1 A2 A3 a vs B1 B2 B3 b (leave C1 C2 C3 c)
2. B1 B2 B3 a vs C1 C2 C3 b (leave A1 A2 A3 c)
3. A1 B1 C1 b vs A2 B2 C2 c (leave A3 B3 C3 a)

You can of course extend this to 39, 120, 363

Title: Re: 12 balls - variation
Post by RiddleGenius on Feb 23^rd, 2008, 7:58am

It takes three tries, and you find out which ball it is.

Example 1

you weigh balls

1234 vs 5678 ......if equal then you know the odd ball is in 9,10,11,12. So for your second weigh in you weigh balls 9, 10 vs 1,2(knowing that 1 & 2 are normal weight) if balanced then you for your third and final weigh in you weigh 11 vs 1, if balanced again then we know its ball 12. If in that last weigh in it wasn't balanced the we know its 11. In the weigh in prior to that one if it wasn't even then you weigh 9 with 1, if its balanced then you know its 10 if it isn't then you know its 9.......Alright lets suppose in you initial weigh in it wasn't even. Then you can safely assume that the side that goes up has the potential light ball or the side that goes down has the potential heavy ball. For example purposes only lets say that 1234 went up, meaning 5678 went down. Our second weigh in will be balls 1237 vs 3 normal balls( 9,10,11,12) and ball 4. It should look like this 1237 vs 9, 10, 11, 4. If the left side went up we can safely assume it is b/c of balls 1,2,3. So we would have to weigh 1 vs 2, if equal then ball 3 is the odd ball, if uneven then the side that goes up is the odd ball because these were potentially lighter balls. But if the scale had gone down on the left side then it went down because ball 7 was heavy or ball 4 is lighter, so you compare one of those with a normal ball and then you can get your answer. But if in your second weigh in the scale was balance then you are left with balls 5,6, & 8. These are potentially heavy balls. So you compare one with another for instance 5 vs 6. If even its ball 8, if uneven then its the side that went down.

Title: Re: 12 balls - variation
Post by Icarus on Feb 23^rd, 2008, 12:03pm

You've got the wrong thread, RiddleGenius. This thread is for a variation of the problem:

You have to plan out your weighings in advance. You only get the outcomes after all weighings are finished.

Title: Re: 12 balls - variation
Post by Victor_YS_Cheung on Jul 8^th, 2009, 11:23pm

I worked out the answer alone, when I was 14. It took 3 trials, to identy the odd ball out of the 12 balls, and tell whether it is heavier or lighter. To start as 1st step, balls are assigned to 1st-step groups with equal number of balls. When proceeding further, next steps groups are formed with smaller number of balls. There are 2 key skills, as hints. First one is partial removal of balls from a group so as to form next steps groups. Second one is to select some balls from groups and swap across sides of the balance pans so as to form the next step groups. ::)