Author 
Topic: 12 balls  variation (Read 17508 times) 

redPEPPER
Full Member
Posts: 160


12 balls  variation
« on: Apr 11^{th}, 2003, 5:44am » 
Quote Modify

quoted from the hard riddles library: You have 12 identicallooking balls. One of these balls has a different weight from all the others. You also have a twopan 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...


IP Logged 



cho
Guest


Re: 12 balls  variation
« Reply #1 on: Apr 11^{th}, 2003, 6:47am » 
Quote Modify
Remove

It can be done in 4 weighings.


IP Logged 



cho
Guest


Re: 12 balls  variation
« Reply #2 on: Apr 11^{th}, 2003, 7:39am » 
Quote Modify
Remove

My mistake. It can be done in 3 weighings.


IP Logged 



cho
Guest


Re: 12 balls  variation
« Reply #3 on: Apr 11^{th}, 2003, 8:29am » 
Quote Modify
Remove

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


IP Logged 



LZJ
Junior Member
Gender:
Posts: 82


Re: 12 balls  variation
« Reply #4 on: Apr 12^{th}, 2003, 5:26am » 
Quote Modify

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


IP Logged 



mistysakura
Junior Member
Gender:
Posts: 121


Re: 12 balls  variation
« Reply #5 on: Apr 12^{th}, 2003, 10:42pm » 
Quote Modify

on Apr 12^{th}, 2003, 5:26am, 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.


IP Logged 



LZJ
Junior Member
Gender:
Posts: 82


Re: 12 balls  variation
« Reply #6 on: Apr 13^{th}, 2003, 12:57am » 
Quote Modify

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


IP Logged 



redPEPPER
Full Member
Posts: 160


Re: 12 balls  variation
« Reply #7 on: Apr 14^{th}, 2003, 7:04am » 
Quote Modify

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


IP Logged 



mistysakura
Junior Member
Gender:
Posts: 121


Re: 12 balls  variation
« Reply #8 on: Apr 17^{th}, 2003, 4:45pm » 
Quote Modify

Here's what I found. 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.


IP Logged 



redPEPPER
Full Member
Posts: 160


Re: 12 balls  variation
« Reply #9 on: Apr 18^{th}, 2003, 3:58am » 
Quote Modify

That works, Mistysakura. Well done! Now: 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?


IP Logged 



Gerd
Newbie
Gender:
Posts: 26


Re: 12 balls  variation
« Reply #11 on: Apr 30^{th}, 2003, 4:25am » 
Quote Modify

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: 52811  10634 B: 541211  1678 C: 1234  91167 With No. 6 three times on the right side you get RRR (heavier) and LLL (lighter). Because you miss 2 other weighingresults, you are not able to weigh 13 balls (overall you only have 24 possible results).


IP Logged 



Rujith de Silva
Newbie
Gender:
Posts: 22


Re: 12 balls  variation
« Reply #12 on: Jun 11^{th}, 2003, 8:53am » 
Quote Modify

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.


IP Logged 



redPEPPER
Full Member
Posts: 160


Re: 12 balls  variation
« Reply #13 on: Jun 11^{th}, 2003, 3:24pm » 
Quote Modify

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


IP Logged 



Rujith de Silva
Newbie
Gender:
Posts: 22


Re: 12 balls  variation
« Reply #14 on: Jun 12^{th}, 2003, 7:42am » 
Quote Modify

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


IP Logged 



TimMann
Senior Riddler
Gender:
Posts: 330


Re: 12 balls  variation
« Reply #15 on: Oct 14^{th}, 2003, 1:13am » 
Quote Modify

I notice Icarus listed the extension to this puzzle under "unsolved," presumably because no one was explicit about what the "something" is. It is a 14th ball that is known to be of standard weight. 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.


IP Logged 
http://timmann.org/



Rujith de Silva
Newbie
Gender:
Posts: 22


Re: 12 balls  variation
« Reply #16 on: Oct 14^{th}, 2003, 8:38am » 
Quote Modify

Yes, the necessary addition is 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 19 and AD. Note that every weighing must include the x ball. 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.

« Last Edit: Oct 14^{th}, 2003, 8:43am by Rujith de Silva » 
IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: 12 balls  variation
« Reply #17 on: Oct 14^{th}, 2003, 7:57pm » 
Quote Modify

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


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



vsmurali
Newbie
Gender:
Posts: 1


Re: 12 balls  variation
« Reply #18 on: Oct 6^{th}, 2005, 6:17am » 
Quote Modify

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


IP Logged 



Nigel_Parsons
Junior Member
Gender:
Posts: 63


Re: 12 balls  variation
« Reply #19 on: Oct 25^{th}, 2005, 12:23am » 
Quote Modify

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


IP Logged 



Raja Reddy
Guest


Re: 12 balls  variation
« Reply #20 on: Oct 28^{th}, 2005, 1:31pm » 
Quote Modify
Remove

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


IP Logged 



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7517


Re: 12 balls  variation
« Reply #21 on: Oct 28^{th}, 2005, 2:23pm » 
Quote Modify

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

« Last Edit: Apr 7^{th}, 2011, 2:00pm by Grimbal » 
IP Logged 



RiddleGenius
Newbie
Posts: 9


Re: 12 balls  variation
« Reply #22 on: Feb 23^{rd}, 2008, 7:58am » 
Quote Modify

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.


IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: 12 balls  variation
« Reply #23 on: Feb 23^{rd}, 2008, 12:03pm » 
Quote Modify

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.


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



Victor_YS_Cheung
Newbie
Posts: 1


Re: 12 balls  variation
« Reply #24 on: Jul 8^{th}, 2009, 11:23pm » 
Quote Modify

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 1ststep 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.


IP Logged 



