Puzzle asked in interview

[Nilesh Raje]

Hi ,

My friend was asked this puzzle in a java interview. I need your help for the solution and solving technique of this.

1)You have 10 marbles and one is heavy. How many minimum iterations are needed to find the heavy marble.

2) There are two jars of capacity 5 and 3 liter. How to measure 7 liter of water using these two jars.
Ans) I guess this can be done this way.

Given : j1= 5 and j2=3

Step 1: Pour water in j1 till it fills that mean now j1 will hold 5 liters
Step 2: Now pour the remaning water in j2 so it now holds 2 liters.

Ummm is this right.?

Please help.

Thanks

[fred rosenberger]

i think you're answer to 2 is not complete. where you stopped, you have one jar (the 3-liter) holding 3 liters, and one (the 5-liter) holding 2. I don't see how that is seven liters. Of course, it's not hard to GET to 7 from here...

Do you have any idea how to answer #1? I would think the question is not well-defined. I could just say "marble #X is the heavy one", do NO weighings, and be right 10% of the time. So, it's possible that you can be right with zero weighings. The problem doesn't state if you have a balance scale or a digital "this weighs X grams" scale - which makes a difference.

Assuming it's a balance scale, i could weigh one random marble agaianst against another. If one is heavier, i've found it in one weighing, and i'll get it right with one weighing about 20% of the time.

If you want to know the minimum number required to GUARANTEE you find the heavy one... that's harder... but i'd say 3. You want to maximize the information you get with each weighing. so, i'd initally weigh 5 against 5. you can discard the 5 on the lighter side.

Can you figure out the next step? with a second weighing, I would either know the heavy one, or narrow it down to 2...

[Ulf Dittmer]

I think you're making a wrong assumption about #2. Where I've seen this question posed (most recently in the movie Die Hard With A Vengeance), you did not have "7 liters of water" available - you had an unlimited supply of water (say, from a fountain), and then you had to measure 7 liters using the two jars.

[Nilesh Raje]

Nilesh Raje wrote:Hi ,

My friend was asked this puzzle in a java interview. I need your help for the solution and solving technique of this.

1)You have 10 marbles and one is heavy. How many minimum iterations are needed to find the heavy marble.

2) There are two jars of capacity 5 and 3 liter. How to measure 7 liter of water using these two jars.
Ans) I guess this can be done this way.

Given : j1= 5 and j2=3

Step 1: Pour water in j1 till it fills that mean now j1 will hold 5 liters
Step 2: Now pour the remaning water in j2 so it now holds 2 liters.

Ummm is this right.?

Please help.

Thanks

At step to i will have 5 lts already with me in j1 and j2 would be holding 2 lts so thats total of 7 lts measured. Why are you saying its incomplete?

[Paul Yule]

Nilesh Raje wrote:

At step to i will have 5 lts already with me in j1 and j2 would be holding 2 lts so thats total of 7 lts measured. Why are you saying its incomplete?

because that doesn't make sense as a problem. If you had exactly 7 liters to begin with the size of the jar would be irrelevant as long as the combination held 7 liters. You could put any random amount you wanted to in either jar as long as you emptied your original measurement.

The objective I think is to be able to measure 7 liters with just these 2 jars not having any sort of number you started off with.

so...fill the 5 liter jar. Take the full jar and fill the smaller jar. Leaving 2 in the big one.

Dump out the smaller jar. Put the 2 liters in the smaller jar. Fill the big jar. 5+2

Alternatively

fill the small jar. Put the contents in the big jar. Fill the small jar. Fill the big jar leaving 1 in the small jar.

Dump the big jar. Put the 1 liter in the big jar. Fill the small jar. Put the contents in the big jar (it now has 4). Fill the small jar. 4+3

[Joseph Macer]

1)You have 10 marbles and one is heavy. How many minimum iterations are needed to find the heavy marble.
2) There are two jars of capacity 5 and 3 liter. How to measure 7 liter of water using these two jars.

The first question gives incomplete data. If you assumed one marble is of weight X and the other nine are of weight <X, the question is about search efficiency; in this case I suspect they are looking for someone to do a binary-like search: comparing 5 marbles to the other five, discarding the lighter pile, comparing two of those to another two, and either selecting the odd marble out if both sets of two or equal, or comparing one of those sets. This gives you a minimum of 2 iterations (for best-case; 3 iterations to select the heaviest marble no matter the situation). If the marbles are of arbitrary weight and you need to find the heaviest, then the answer is completely different.
To clarify:
1) Compare 5 marbles to another 5. The heavier pile contains the heavy marble. Discard the lighter pile.
2) From the heavy pile, compare any 2 marbles with any other 2.
IF the same piles are the same weight, the heavy marble is the one you're not holding. The end.
3) ELSE, compare the two marbles from the heavier set found in step 2. The end.

The second question has already been answered, assuming infinite supply of water:
-Fill 5 liter jar to capacity
-From the 5 liter jar, fill the 3 liter jar to capacity
-Empty the 3 liter jar
-From the 5 liter jar, transfer the remaining 2 liters to the 3 liter jar
-Fill the 5 liter jar to capacity
You now have 5L in a five liter jar, and 2L in a three liter jar.

[Thillakan Saba]

I will go for grouping by 3.
Lets say, 10 marples as follows
ABC, DEF, GHI, J

weight attempt 1) Compare ABC and DEF.
weight attempt 2) From the heavy group, compare any 1 marbles with any other 1.
If both are the same weight, the heavy marble is not on the balance. The end.

weight attempt 2) else , compare ABC and GHI
weight attempt 3) From the heavy pile, compare any 1 marbles with any other 1.
If both are the same weight, tthe heavy marble is not on the balance. The end.

else J . The end

[Bert Bates]

I believe the more advanced version of the marble problem is this:

You have 12 marbles and one of them is either heavier or lighter than all the rest. Given a balance, and three weighings, determine which marble is different, and whether it's heavier or lighter.

This one took me a loooong time to solve

[Michael Ernest]

Bert Bates wrote:I believe the more advanced version of the marble problem is this:

You have 12 marbles and one of them is either heavier or lighter than all the rest. Given a balance, and three weighings, determine which marble is different, and whether it's heavier or lighter.

This one took me a loooong time to solve

Ten marbles, right? So you weigh five and five, and take the heavier batch. Then you weigh two and two, leaving one off the scale. If the pairs balance, the one off the scale is the heavy one. If they don't balance, split the heavier pair and weigh them against each other. So, if you're lucky, two weighings. Otherwise three, is that right?

I don't check into this forum much, so if providing a solution is bad form, please forgive me.

That 12-marble scenario is interesting. I'll have to think about that one.

[Venkata Kumar]

The solution to 12 marbles is. As Thillakan said marbles can be grouped by 3 1-3, 4-6,7-9,10-12.
suppose the 12th marble is heavier one.

It takes two weighings to find the group that has heavier marble. In the third weighing 10 and 11 can be compared and they are of same weight. So 12th marble is heavier than rest.

[Michael Ernest]

Venkat Divvela wrote:The solution to 12 marbles is. As Thillakan said marbles can be grouped by 3 1-3, 4-6,7-9,10-12.
suppose the 12th marble is heavier one.

It takes two weighings to find the group that has heavier marble. In the third weighing 10 and 11 can be compared and they are of same weight. So 12th marble is heavier than rest.

If you know one marble is heavier to begin with, it is a simple problem. In this case, however, you have to isolate and characterize the difference, which makes it a little stickier.

You need three marbles -- two uniform, one odd -- and two weighings to isolate and characterize the odd marble. Put any two marbles in the balance. If they balance, you know the odd marble is the remaining one. Now balance it against either of the first two. If it raises in the balance, it's lighter; otherwise, it's heavier.

If the first weighing yields an imbalance, you know a the remaining marble is a uniform one. Replace the "heavy" marble on the scale with it. Two things can happen. If there is now a balance, then the odd marble was removed, and it is heavier than the other two. If there is no change, then a uniform marble was removed, and the odd one is lighter. If the imbalance shifts from one side to the other, then no marbles can have the same weight.

You can build successive strategies as you add marbles and weighings, but I haven't figured the way to 12 marbles and 3 weighings just yet.

[teja dharma]

first you take 5litres in jar 1 then remove 3 litres from it by using 3 litre jar.now there is only 2 litre in 5 litres jar.
then take the 2 litres from 5 litres jar to 3 litres jar.Now take 5 litres in to 5 litres jar .now j5=5litres,j3=2litres total 7 litres

[Bert Bates]

Man Michael,

I hope you solve it or I'm going to have to re-create my old solution...

Go Michael go!

[aditee sharma]

Bert Bates wrote:I believe the more advanced version of the marble problem is this:

You have 12 marbles and one of them is either heavier or lighter than all the rest. Given a balance, and three weighings, determine which marble is different, and whether it's heavier or lighter.

This one took me a loooong time to solve

Divide the 12 marbles into 3 groups of 4 each (say A,B and C).
Weighing 1: Put any 2 groups on either sides of the balance (say A and B).
Scenario 1: The unique marble is not amongst the weighed and the balance is equal.
This means the different marble is in the 3rd group (C) not weighed yet.
Weighing 2: divide C into 2 each and weigh.
One of the pans will go down and the other will go up.
Weighing 3: From the heavier side, exchange 1 marble with a marble from the lighter side. Mark the marbles.You should know which is which.
Scenario 1.1: The balance doesn't shift.This means that the one left in the heavier side that you did not touch is the unique marble and it is heavier than the rest.
Scenario 1.2: The balance is reversed.This means that the marble that you moved from the lighter side in weighing 3 is unique and it is lighter than the rest.
Scenario 1.3: The balance is equalized? Not possible.

Scenario 2: The unique marble is amongst the weighed and one pan goes up while the other goes down.
This means that C has ordinary marbles only because at this point it is clear that either A or B has the unique marble.
Remove 3 marbles from the heavier side and keep them aside.Again, mark the marbles.You should know which is which.
Weighing 2: Now, move 3 marbles from lighter side to heavier side and then take 3 marbles from C and put them on the lighter side.Weigh.
Scenario 2.1: The balance doesn't shift.This means that the one left in the heavier side that you did not touch is the unique marble and it is heavier than the rest.
Scenario 2.2: The balance is equalized.This means that the 3 marbles that you kept aside from the heavier side have the heavier marble amongst them.
Weighing 3: Weigh any 2 marbles from the step above against each other.If they are equal, then the marble you are left with is the heavier one, otherwise the weighing itself will show you which is the unique heavier marble.

Scenario 2.3: The balance is reversed.This means that the 3 marbles that you moved from lighter to heavier side have the unique lighter marble amongst them.
So, we have an altered version of 3rd weighing in this case.
Weighing 3: Weigh any 2 marbles from the step above against each other.If they are equal, then the marble you are left with is the lighter one, otherwise the weighing itself will show you which is the unique lighter marble.

[Michael Ernest]

I don't think this is completely correct.

In the first scenario, the first weighing yields a balance, so you know the odd marble is in group C. You divide C into two equal groups and weigh again. There must be an imbalance. If you switch a marble from each side and see no change in balance, however, you only know that you switched two uniform marbles. In this case, there are now two marbles that could be odd, but you don't know if the odd one is lighter or heavier.

My son was up waaay too late last night finishing homework, and so I had some time to work on this. I am confident I discovered all the dead ends.

Here's the problem. Whether you get eliminate 4 or 6 marbles after one weighing, you run into a case where two more weighings won't be enough to isolate and characterize the odd marble.

If you start with four groups of 3, you can solve almost all cases in three weighings. I leave that as an exercise to other interested puzzlers. You eliminate six marbles by binary process. Then the fun begins.

If you start with three groups of 4, it comes to the same thing. You can eliminate one group in the first weighing, and four more marbles in the second weighing. What you can't do in all cases is isolate and characterize the odd marble in one more weighing.

Or maybe you can! I was so cross-eyed last night I couldn't see it. I would love some prime brain time to put this problem to bed, but it ain't happenin' for me today.

[aditee sharma]

Michael Ernest wrote:I don't think this is completely correct.

In the first scenario, the first weighing yields a balance, so you know the odd marble is in group C. You divide C into two equal groups and weigh again. There must be an imbalance. If you switch a marble from each side and see no change in balance, however, you only know that you switched two uniform marbles. In this case, there are now two marbles that could be odd, but you don't know if the odd one is lighter or heavier.

Thanks for pointing this out. Here's the corrected version :
---------------------------------------------------------------------------------
Divide the 12 marbles into 3 groups of 4 each (say A,B and C).
Weighing 1: Put any 2 groups on either sides of the balance (say A and B).
Scenario 1: The unique marble is not amongst the weighed and the balance is equal.
This means the different marble is in the 3rd group (C) not weighed yet.
<correction goes here>
Weighing 2: Take 3 marbles out of C and put on one side of the balance.On the other side, put 3 marbles taken out from A or B(We know that the latter are of equal weight). Again, mark and identify the marble that you kept aside from C.

Scenario 1.1: The C-side pan goes up.Now you know that 1 marble in the 3 on the C-side is unique and lighter.
Weighing 3: Take any 2 from the C-side pan and weigh against each other. If they are equal, then the one you are left with is unique and lighter than the rest.
Otherwise, the one that goes up is the unique and lighter one (Mind you, we already figured from weighing 2 that this can only be lighter.).

Scenario 1.2: The C-side pan goes down.Now you know that 1 marble in the 3 on the C-side is unique and heavier.
Weighing 3: Take any 2 from the C-side pan and weigh against each other. If they are equal, then the one you are left with is unique and heavier than the rest.
Otherwise, the one that goes down is the unique and heavier one (Mind you, we already figured from weighing 2 that this can only be heavier.).

Scenario 1.3: The balance is in equilibrium.This means that the marble that you are left with in weighing 2 is the unique one.However, you still don't know that whether it is lighter or heavier.
Weighing 3: Weigh this marble against any other.If it is heavy, it will go down.If it is lighter, it will go up.
</end of correction>



Scenario 2: The unique marble is amongst the weighed and one pan goes up while the other goes down.
This means that C has ordinary marbles only because at this point it is clear that either A or B has the unique marble.
Remove 3 marbles from the heavier side and keep them aside.Again, mark the marbles.You should know which is which.
Weighing 2: Now, move 3 marbles from lighter side to heavier side and then take 3 marbles from C and put them on the lighter side.Weigh.
Scenario 2.1: The balance doesn't shift.This means that the one left in the heavier side that you did not touch is the unique marble and it is heavier than the rest.
Scenario 2.2: The balance is equalized.This means that the 3 marbles that you kept aside from the heavier side have the heavier marble amongst them.
Weighing 3: Weigh any 2 marbles from the step above against each other.If they are equal, then the marble you are left with is the heavier one, otherwise the weighing itself will show you which is the unique heavier marble.

Scenario 2.3: The balance is reversed.This means that the 3 marbles that you moved from lighter to heavier side have the unique lighter marble amongst them.
So, we have an altered version of 3rd weighing in this case.
Weighing 3: Weigh any 2 marbles from the step above against each other.If they are equal, then the marble you are left with is the lighter one, otherwise the weighing itself will show you which is the unique lighter marble.

-------------------------------------------------------------------------------------
I believe the 2nd scenario and its solution should be fine.

Michael Ernest wrote:
If you start with four groups of 3, you can solve almost all cases in three weighings. I leave that as an exercise to other interested puzzlers. You eliminate six marbles by binary process. Then the fun begins.

If you start with three groups of 4, it comes to the same thing. You can eliminate one group in the first weighing, and four more marbles in the second weighing. What you can't do in all cases is isolate and characterize the odd marble in one more weighing.

Or maybe you can! I was so cross-eyed last night I couldn't see it. I would love some prime brain time to put this problem to bed, but it ain't happenin' for me today.

I think the reverse is proved now.Please correct me again if you think otherwise.Together, we can.

[Michael Ernest]

Not a rigorous check on my part, but I believe you've got it. I knew there had to be a transition somewhere from a 4-marble test to a 3-marble test like you showed here, but hadn't figured it out. Well done!

[Ryan McGuire]

Weighing Problems

With each double-pan weighing of groups of marbles, you can one of three states. Left side goes down, right side goes down, neither side goes down. That means each digit gives you one trinary digit of information, allowing you differentiate between 3 possible situations. Two weighings would enable you to differentiate between 3^2 or 9 possible situations. For this problem, where there are ten marbles and thus ten different possible situations, two weighings wouldn't be sufficient. Therefore you have to go up to 3 weighings, which would allow you to differentiate between 3^3 or 27 different situations. Since exactly one marble must be heavier than the rest, you could actually solve this problem for 27 marbles in just 3 weighings:

Label your marbles 1-9A-R
Weigh them like this:
123456789 vs. JKLMNOPQR
123ABCJKL vs 789GHIPQR
147ADGJMP vs 369CFILOR

Note which pan went down for each weighing.  Find the corresponding row in the table below.
(For instance, if the balance was [B]E[/B]ven for the first weighing, then the [B]L[/B]eft side went down for the second, and the [B]R[/B]ight side went down for the third, look on the ELR line and find that marble C is the heavy one.

LLL 1
LLE 2 
LLR 3
LEL 4 
LEE 5 
LER 6 
LRL 7
LRE 8 
LRR 9
ELL A 
ELE B 
ELR C
EEL D 
EEE E 
EER F 
ERL G
ERE H 
ERR I 
RLL J
RLE K 
RLR L
REL M 
REE N 
RER O 
RRL P
RRE Q 
RRR R

If you have exactly ten marbles without any extra known good ones to fill out the pans, it shouldn't be too hard to pick a subset of the 27 marbles so that there are always an equal number of marbles in each pan.

But how do you decide which labeled marbles to keep?
You can pair up the marbles by swapping Rs and Ls For instance marble K corresponds to the RLE line. The other one in that pair is on the LRE line, which is marble 8. Notice that marble E on the EEE line is paired with itself. To reduce 27 to some other number remove pairs of marbles (including E if you need to remove and odd number) until you get the specified number.

To get from 27 down to 10, we have to remove 17 (an odd number) marbles.
Remove E, 1,R, 2,Q, 3,P, 4,O, 5,N, 6,M, 7,L, 8 and K.
Now just remove any mention of the removed marbles from the "code" above:

Label your marbles 9,A-D,F-J
Weigh them like this:
9 vs. J
ABCJ vs 9GHI
ADGJ vs 9CFI

Note which pan went down for each weighing.  Find the corresponding row in the table below.
(For instance, if the balance was [B]E[/B]ven for the first weighing, then the [B]L[/B]eft side went down for the second, and the [B]R[/B]ight side went down for the third, look on the ELR line and find that marble C is the heavy one.

LRR 9
ELL A 
ELE B 
ELR C
EEL D 
EER F 
ERL G
ERE H 
ERR I 
RLL J

(Of course, you could rework the labels to make more sense. I left them kinda goofy so you could see how the 10 marble problem relates to the 27 marble problem.)

Cool?

[Michael Ernest]

Cool, but if you're following Bert's variation of the problem, you don't know there's one heavy marble. You know one is "odd," i.e., heavier or lighter.

Before your explanation, however, I inferred that 12 was the maximum one could handle with an odd marble in three weighings. Is that the case?

[Mike Simmons]

I believe Ryan is referring to the version of the problem at the beginning of this thread. Not to the more common version that Bert brought up.

Michael Ernest wrote:Before your explanation, however, I inferred that 12 was the maximum one could handle with an odd marble in three weighings. Is that the case?

12 is the max for three weighings, if the ball may be heavier or lighter, and you need to both identify which ball is different, and whether it's heavier or lighter.

13 is the max if you need to identify which ball is different, but don't actually need to know if it's heavier or lighter.

[eswar kumar]

Here is the Ans for 1

Minimum iterations are 2.
First separate 10 marbles into two groups (5+5)
1. Weigh both, you ll find one group(5 marbles) is heavier than other(5 marbles), take the heavier( so here you filtered 5 marbles from out of 10) Now you have 5 marbles.
Again separate 5 into 2+2+1
2. Again weigh by taking 2+2 marbles in pans. If both sides same weight the other one which is not weighed is the heavy one.
3. If the heavier marble is in either of 2+2, weigh 2+2 marbles and take out the lighter two and the marble which is not weighed (so now you filtered 5+2+1(not weighed marble))marbles, so now you have two marbles. Again separate two marbles and weigh, now you can find which is heavier.
So minimum 2 iterations required.

Thanks & Regards,
Eswar