wood burning stoves 2.0*
The moose likes Programming Diversions and the fly likes Solve this puzzle. Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Solve this puzzle." Watch "Solve this puzzle." New topic
Author

Solve this puzzle.

Himanshu Gupta
Ranch Hand

Joined: Aug 18, 2008
Posts: 598

I dont know that is this the right place to post this. In case if we have a suitable place please shift this thread.

At the National Games, the athletic officials have discovered that amongst their pile of 12 shotput balls, one of them has a manufacturing fault - it is not the same weight as the others. They need to determine which is the faulty shotput ball, but the only scales they can find are a set of pan balances. The charge is 500 Rs for every weighing. What is the minimum number of weighings that they need to make to determine which shotput ball is faulty?

My answer is 3

My Blog SCJP 5 SCWCD 5
Vinod Tiwari
Ranch Hand

Joined: Feb 06, 2008
Posts: 459
    
    1
My answer is 3 too..


Vinod Tiwari | Twitter
Dave Trower
Ranch Hand

Joined: Feb 12, 2003
Posts: 86
Look at this way.
There are 12 differant balls that could be faulty and the faulty ball could be be either be too heavy or too light.
Thus there are 24 differant combinations of what the which ball # is faulty and if it is too heavy or too light.

With each scale weighing, three differant things could happen:
1) The left side of the scale goes down.
2) The right side of the scale goes down.
3) The two sides are equal.

So in 3 weighings there are 3X3X3 = 27 differant outcomes.
Three weighing will work if you carefully come with a plan on how to weigh the balls.
I solved a puzzle like this a few years ago. The puzzle I solved was how ot determine the faulty ball in 3 weighings.
The answer is a flow chart since depending on what happens on the first weighing determines what you do at the second weighing.
Greg Charles
Sheriff

Joined: Oct 01, 2001
Posts: 2840
    
  11

This is usually called the 12 Coins Problem, and is presented as a problem of trying to find the counterfeit coin. The generalized solution is that you can figure out the heavier or lighter object in n weighings for (3^n - 3) / 2 objects. For the case of n = 3, that means 12 objects, and the weighings you need to do are:

1 2 3 10 vs. 4 5 6 11
1 2 3 11 vs. 7 8 9 10
1 4 7 10 vs. 2 5 8 12

That's thanks to this site. I can never remember it or derive it myself.

It's fairly easy to work out that out of the 27 outcomes that Dave mentioned, 3 are impossible, and the 24 remaining each correspond to one of the objects being heavier or lighter.
Riley Thomas
Greenhorn

Joined: Aug 08, 2009
Posts: 13
Assuming there is no limit to the amount of balls that can be placed on the scale, the answer is 3 weighs.

1: Weigh 6 balls on each side. The heavier side (obviously) contains the irregular ball.
2: Of those 6, weight 3 on each side. Again, the heavier side has the irregular ball.
3: Of those 3, weigh any 2. If they're equal, the third ball is the irregular.
Ninad Kulkarni
Ranch Hand

Joined: Aug 31, 2007
Posts: 787

My answer is 3 too.


SCJP 5.0 - JavaRanch FAQ - Java Beginners FAQ - SCJP FAQ - SCJP Mock Tests - Tutorial - JavaSE7 - JavaEE6 -Generics FAQ - JLS - JVM Spec - Java FAQs - Smart Questions
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 2995
    
    9
Riley Thomas wrote:1: Weigh 6 balls on each side. The heavier side (obviously) contains the irregular ball.

Not necessarily. Reread the problem statement. No one said the irregular ball is heavier, just that it's different in weight. It could just as easily be lighter.

There are numerous solutions possible, but the minimum number of weighings required is three. And the first weighing will always have to be 4 balls vs 4 balls, with 4 left over. Otherwise information theory shows you can't possibly get enough information in 2 more weighings to resolve all the possibilities.
Roger Rammer
Greenhorn

Joined: Apr 19, 2010
Posts: 21
Superb! great minds think alike ;-)

Riley Thomas wrote:Assuming there is no limit to the amount of balls that can be placed on the scale, the answer is 3 weighs.

1: Weigh 6 balls on each side. The heavier side (obviously) contains the irregular ball.
2: Of those 6, weight 3 on each side. Again, the heavier side has the irregular ball.
3: Of those 3, weigh any 2. If they're equal, the third ball is the irregular.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 2995
    
    9
Hmmm... so, did you reread the problem statement?
Roger Rammer
Greenhorn

Joined: Apr 19, 2010
Posts: 21
I have-I can see a slight flaw in the logic....
subhash kumar
Ranch Hand

Joined: Jul 14, 2010
Posts: 63
These balls can be compared with the 12 coins and proceeds as follows:

Four coins are put on each side. There are two possibilities:
1. One side is heavier than the other. If this is the case, remove three coins from the heavier side, move three coins from the lighter side to the heavier side, and place three coins that were not weighed the first time on the lighter side. (Remember which coins are which.) There are three possibilities:
1.a) The same side that was heavier the first time is still heavier. This means that either the coin that stayed there is heavier or that the coin that stayed on the lighter side is lighter. Balancing one of these against one of the other ten coins will reveal which of these is true, thus solving the puzzle.
1.b) The side that was heavier the first time is lighter the second time. This means that one of the three coins that went from the lighter side to the heavier side is the light coin. For the third attempt, weigh two of these coins against each other: if one is lighter, it is the unique coin; if they balance, the third coin is the light one.
1.c) Both sides are even. This means the one of the three coins that was removed from the heavier side is the heavy coin. For the third attempt, weigh two of these coins against each other: if one is heavier, it is the unique coin; if they balance, the third coin is the heavy one.
2. Both sides are even. If this is the case, all eight coins are identical and can be set aside. Take the four remaining coins and place three on one side of the balance. Place 3 of the 8 identical coins on the other side. There are three possibilities:
2.a) The three remaining coins are lighter. In this case you now know that one of those three coins is the odd one out and that it is lighter. Take two of those three coins and weigh them against each other. If the balance tips then the lighter coin is the odd one out. If the two coins balance then the third coin not on the balance is the odd one out and it is lighter.
2.b) The three remaining coins are heavier. In this case you now know that one of those three coins is the odd one out and that it is heavier. Take two of those three coins and weigh them against each other. If the balance tips then the heavier coin is the odd one out. If the two coins balance then the third coin not on the balance is the odd one out and it is heavier.
2.c) The three remaining coins balance. In this case you know that the unweighed coin is the odd one out. Weigh the remaining coin against one of the other 11 coins and this will tell you whether it is heavier or lighter.

Subhash Kumar
Attitude is everything
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38020
    
  22
Welcome to the Ranch subhash kumar
Orton K Randy
Ranch Hand

Joined: Aug 12, 2011
Posts: 41

I was asked the same question in my interview months ago. I am surprised no one in here mentioned the log/exponentiation? After trying out for several no. of balls, you'd have noticed a pattern. Ya don't even think twice. Min no. of weighings(in a physical balance of course) required is
log n to the base 2
where 'n' is the no. of balls.

So if the no. of balls is 4, you need 2 weighings, for 8 you need 3, for 16 you need 4 and so on. Note that for 12 you need 3 and NOT 4. Likewise for 5,6,7 you need only 2 and NOT 3. So in programming terms, it's floor(log n to the base 2).

You might well be aware of this, still this one's for those trying to work out everytime.


Coderanch, best ever forum on the net. Hands down.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 2995
    
    9
Considering that each weighing has 3 possible outcomes (left tray heavier, right tray heavier, or both equal) it doen't make much sense to take a log base 2 here. I suggest you consider base 3.
Orton K Randy
Ranch Hand

Joined: Aug 12, 2011
Posts: 41

Could easily go wrong. You can try that with 8 balls. The outcomes left/right tray being heavier have no particular significance. It's all about
* one tray being heavier than the other,
* or both being equally heavy.

See my point? You could place a set of balls in the left tray and the rest in the right. If the left is heavier than the right, the conclusion is that the culprit is in the set we placed in the left tray(assuming we're looking for 1 ball that's heavier than the rest). If you placed that particular set in the right tray instead of left, you still zero in on the ball the very same way. So there are only 2 significant outcomes although there are 3 possible outcomes.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 2995
    
    9
Orton K Randy wrote:If the left is heavier than the right, the conclusion is that the culprit is in the set we placed in the left tray(assuming we're looking for 1 ball that's heavier than the rest).

That particular conclusion only makes sense if we know, in advance, that the ball we're looking for is heavier than the rest. You're making an assumption not present in the problem statement - one I've pointed out previously in this thread.

But that's OK. The problem you're discussing is simpler than the one in this thread, and your formula is still incorrect. So I'll discuss that problem instead.

If you know that the one ball is heavier than the others, then with 2 weighings you can handle up to 9 balls. With 3 weighings you handle up to 27 balls. With 4 weighings, 81 balls. It's a simple power of 3.

How does this work? Let's say there are 81 balls. We can solve this in 4 weighings. Put 27 on the left, 27 on the right, and 27 left over. Weigh them. If one side goes down, the heavier ball is among those 27 (whether it's on the left or right). If neither side goes down, the heavier ball is among the 27 left over.

So now you know the heavier ball is one of a group of 27, and you have 3 weighings left. Put 9 on the left, 9 on the right, and 9 left over. Weigh them. If one side goes down, that group of 9 (left or right) contains the heavier ball. Otherwise, the heavier ball is among the 9 left over.

Now you know the heavier ball is among a group of 9, and you have 2 weighings left. Put 3 on the left, 3 on the right, and 3 left over. Weigh them. If a side goes down, that group of 3 contains the heavier ball. Otherwise the heavier ball is among the 3 left over.

Now you know the heavier ball is one of 3 balls, and you have 1 weighing left. Put 1 on the right, 1 on the left, and 1 left over. Weigh them. If a side goes down, that 1 is the heaviest ball. Otherwise, the 1 left over is the heaviest ball.

So, in 4 weighings you can easily handle 81 balls.

More generally, in N weighings you can handle 3 to the power of N balls. And if we solve this for N, the number of weighings required is equal to the log base 3 of the number of balls. Rounded up.

Of course, we could have used nearly the same solutions if we had been told that one ball was lighter than the others. As long as we know that in advance.

If you don't know in advance whether the one ball is heavier or lighter than the others, it's harder. But the general solution still involves a base or power of 3, rather than 2.
Orton K Randy
Ranch Hand

Joined: Aug 12, 2011
Posts: 41

Mike Simmons wrote:
Orton K Randy wrote:If the left is heavier than the right, the conclusion is that the culprit is in the set we placed in the left tray(assuming we're looking for 1 ball that's heavier than the rest).

That particular conclusion only makes sense if we know, in advance, that the ball we're looking for is heavier than the rest. You're making an assumption not present in the problem statement - one I've pointed out previously in this thread.


I DID notice that only after I posted. The rest of your post makes perfect sense as to why it's log with a base of 3 and not 2. My bad, I choose no. of balls per weighing in a not so wise manner. Cheers for the clarification.
Tariik el berrak
Greenhorn

Joined: Jan 23, 2009
Posts: 9
My answer is at the end of the explanation:

Algorithm :

Step 1:
=======

Firt of all, we need to know by how much a ball is different from the other balls.

Take 1 ball from each shoot ball and put all of them in the scale and note the weight.

It should be 12 * 500 Rs = 6000 Rs

diff = (6000Rs - mesuredWeight) , this is fault wight in a ball from the faulty machine (we dont know yet which machine )

Step 2 :
========

identify the the faulty machine

- take 1 ball from the shoot ball 1
- take 2 ball from the shoot ball 2
- take 3 ball from the shoot ball 3
.
.
.
.
- take 12 ball from the shoot ball 12

The total is 1 + 2+ 3 + ........+ 12 = 12*11/2 = 66 balls

the total weight should be 66 * 500 Rs = 33000 Rs expected weight if there is no faulted machine

Now pout the 66 balls in the scale and note the weight totFaultyWeith.

totalDiff = 33000 - totFaultyWeith

if totalDiff = diff ==> only one ball is faulty and means the first machine is faulty
if totalDiff = 2*diff ==> 2 balls are faulty and means the second machine is faulty
if totalDiff = 3*diff ==> 3 balls are faulty and means the third machine is faulty
.
.
.
.
.
if totalDiff = 12*diff ==> 12 balls are faulty and means the 12d machine is faulty

Answer : 2 weighting are required if we don't know by how much a ball is fault
1 weighting is required if we know by how much the ball is faulty (skip of step 1)


Thank you
Deepak Lal
Ranch Hand

Joined: Jul 01, 2008
Posts: 507

which is the correct answer?


When The Going Gets Tougher,The Tougher gets Going
Tariik el berrak
Greenhorn

Joined: Jan 23, 2009
Posts: 9
The problem didn't state by how much the ball is faulty, so it's 2 weightings.

ex :
If customer who let's say has bought the ball and found out that the ball is faulty by let's say (1Rs) and brought it to the factory, only the step 2 is needed by the factory manager to identify the faulty machine.
If the customer said the ball is faulty without saying by how much then you need 2 steps (IDENTIFY BY HOW MUCH AND THEN WHICH MACHINE)
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1006
    
    3
Tariik, are you solving the original problem for this thread or some other problem?

You seem to be solving a puzzle that was posted in another thread some time ago.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 2995
    
    9
Deepak Lal wrote:which is the correct answer?

The actual puzzle in this thread requires 3 weighings to solve. Dave Trower, Greg Charles, and Subhash Kumar seem to have good explanations above - there are many different solutions possible. I haven't studied most of these solutions really carefully, so there may be a flaw somewhere, but the ones I named look right to me . You can also find many past discussions on this site and elsewhere by searching for either "12 balls puzzle" or "12 coins puzzle".
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1006
    
    3
Tariik el berrak wrote:My answer is at the end of the explanation:

Algorithm :

Step 1:
=======
...


You seem to be answering this version of the puzzle.
Tariik el berrak
Greenhorn

Joined: Jan 23, 2009
Posts: 9
Sorry for that:-)
simi selva
Greenhorn

Joined: Nov 18, 2011
Posts: 2
nice riddles..
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4340
    
    2

i fail to see what it matters how much different the ball weighs. i agree it would be a much simpler problem if we knew if the defective ball was heavier or lighter.


SCJP
Visit my download page
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 2995
    
    9
Randall Twede wrote:i fail to see what it matters how much different the ball weighs..

For this problem, it doesn't matter; it's useless information. Tariik was apparently thinking of a different version of the problem, in which we have a scale (which reports the total weight) rather than a balance (which only reports which of the two sides is heavier). In that case, it's possible to solve the puzzle more quickly by a completely different technique. But that's not really relevant to the problem that was actually posted.
Ravi Vakka
Greenhorn

Joined: Nov 06, 2006
Posts: 6
Roger Rammer wrote:Superb! great minds think alike ;-)

Riley Thomas wrote:Assuming there is no limit to the amount of balls that can be placed on the scale, the answer is 3 weighs.

1: Weigh 6 balls on each side. The heavier side (obviously) contains the irregular ball.
2: Of those 6, weight 3 on each side. Again, the heavier side has the irregular ball.
3: Of those 3, weigh any 2. If they're equal, the third ball is the irregular.


But do we know already that the faulty one is heavier or lighter, in order to come to above conclusion ?
Lets say if the faulty ball is lighter then the above logic does not work right ?
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 2995
    
    9
Ravi: you are correct; Riley did not read the original post carefully enough, and his solution is incorrect. This is what I hinted at to Riley, and then to Roger. Roger realized his error, but Riley has never returned to correct his answer. Note that these posts are mostly from over a year and a half ago, and it's unlikely that Riley will return at this point to answer your question.
Tanveer Ahmad
Ranch Hand

Joined: Sep 20, 2005
Posts: 33
Here is the solution...
1. Divide the balls in 3 goups of 4 balls each.
2. weigh any 2 sets.
2a. If you are lucky they will be of same weight the you can easily figure out the faulty one in next two weigh from the third set of 4 balls.
2b. If they are not of same weight then read on...
3. number the ball... say 1, 2, 3, 4 be the one which was lighter and 5, 6, 7, 8 are the ones which are heavier. (lets call the other four as 9, 10...)
4. take one ball from each side (no 4 & no 8) and put it out.
5. move two balls (2 & 3) to the set of 5, 6, & 7 and take 4 balls of the third set (9, 10..) and put it in the lighter set (1, 9, 10, 11, 12) now weigh
case 1 - No change in the balance - faulty is ball no 1 (and faulty is light weight)
case 2 - change in the tilt... then faulty is among 2 & 3 (since 2 & 3 were lighter then the faulty is light weight)
case 3 - Equal weight... Faulty among 4 & 8
At this point you still have one option to weigh and two faulty balls...
With this you can solve the case when you have two chances to weigh and 4 balls to filter (2a)...
John Simer
Greenhorn

Joined: Dec 19, 2011
Posts: 16
Orton K Randy wrote:I was asked the same question in my interview months ago. I am surprised no one in here mentioned the log/exponentiation? After trying out for several no. of balls, you'd have noticed a pattern. Ya don't even think twice. Min no. of weighings(in a physical balance of course) required is
log n to the base 2
where 'n' is the no. of balls.

So if the no. of balls is 4, you need 2 weighings, for 8 you need 3, for 16 you need 4 and so on. Note that for 12 you need 3 and NOT 4. Likewise for 5,6,7 you need only 2 and NOT 3. So in programming terms, it's floor(log n to the base 2).

You might well be aware of this, still this one's for those trying to work out everytime.



I do believe you can solve 8 balls in two weighings

Leave any two out(7 and 8)
Weigh (1,2,3) with (4,5,6)
1. if one side is heavier than the other i.e.(1,2,3), weigh two of them (2 and 3)
- if 2 ==3, then 1 is the heavier
- if 2 != 3, then the heavier one is heavier
2. if (1,2,3)==(4,5,6), weigh 7 and 8.

Wait this only works if you know the odd one is either heavier or lighter - not if it could be either, so nevermind...
----------------
Matthew 1:23 - “Behold, the virgin shall be with child, and bear a Son, and they shall call His name Immanuel,” which is translated, “God with us.”
Merry Christmas (or Happy Holidays) and God Bless you all.
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1006
    
    3
Since this is the Programming Diversions forum...

Is there an algorithm for determining the sets of balls to use in each weighing? I DON"T want a prgram that that has the weighings hard-coded (e.g Weighing 1: A+B+C+D against E+F+G+H). I'm looking for a program that can create that strategy/algorithm -- a meta-algorithm, if you will.

Ideally, I should be able to set an input parameter to N=25 and have it tell me the way to find the faulty ball in 4 (or is it 5?) weighings.

 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
 
subject: Solve this puzzle.
 
Similar Threads
Passing an interface reference to a method expecting an "interface implementor"
help with tcp causing lag in ping pong game
Probability question.
logical question
MS Word to XML conversion