wu :: forums « wu :: forums - 12 balls - variation » Welcome, Guest. Please Login or Register. Nov 26th, 2022, 11:22am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: Eigenray, ThudnBlunder, towr, Grimbal, Icarus, SMQ, william wu)    12 balls - variation « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: 12 balls - variation  (Read 17779 times)
redPEPPER
Full Member

Posts: 160
 12 balls - variation   « on: Apr 11th, 2003, 5:44am » Quote Modify

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...
 IP Logged
cho
Guest

 Re: 12 balls - variation   « Reply #1 on: Apr 11th, 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 11th, 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 11th, 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 12th, 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 12th, 2003, 10:42pm » Quote Modify

on Apr 12th, 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 13th, 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 14th, 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 17th, 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 18th, 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
NickH
Senior Riddler

Gender:
Posts: 341
 Re: 12 balls - variation   « Reply #10 on: Apr 18th, 2003, 4:40am » Quote Modify

See The Oddball Problem and Odd Coin Problems.
 IP Logged

Nick's Mathematical Puzzles
Gerd
Newbie

Gender:
Posts: 26
 Re: 12 balls - variation   « Reply #11 on: Apr 30th, 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: 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).
 IP Logged
Rujith de Silva
Newbie

Gender:
Posts: 22
 Re: 12 balls - variation   « Reply #12 on: Jun 11th, 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
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 11th, 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 12th, 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 (#left-side
candidate balls + #right-side 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 14th, 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://tim-mann.org/
Rujith de Silva
Newbie

Gender:
Posts: 22
 Re: 12 balls - variation   « Reply #16 on: Oct 14th, 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 1-9 and A-D.  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 14th, 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 14th, 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 6th, 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 25th, 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 28th, 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: 7520
 Re: 12 balls - variation   « Reply #21 on: Oct 28th, 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 7th, 2011, 2:00pm by Grimbal » IP Logged
RiddleGenius
Newbie

Posts: 9
 Re: 12 balls - variation   « Reply #22 on: Feb 23rd, 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 23rd, 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 8th, 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 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.
 IP Logged
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »