wu :: forums - Print Page


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

        riddles >> microsoft >> jars with marbles
        
(Message started by: Nox104 on Feb 11^th, 2004, 10:09am)

Title: jars with marbles
Post by Nox104 on Feb 11^th, 2004, 10:09am

Assume that you have 10 jars with unknown number of marbles in each of them. Some jars have marbles with 1g each. And some others have marbles with 1.1g each. Given a scale, how would you determine which jars have 1.1g marbles each with just 1 weighing? The weight of the jar is unspecified but should be taken into account.

Title: Re: jars with marbles
Post by towr on Feb 11^th, 2004, 2:11pm

I don't think this is possible, unless you can take the marbles from the jars, in which case the weight of the jar is completely irrelevant (and that would also make this puzzle a dublicate of one of the coin weighing problems, I think..)
If you can't remove marbles from the jars, then the jars with 1g marbles in them may all contain 11/10 times the number of marbles in the other jars, and thus they would all weigh the same.

Title: Re: jars with marbles
Post by Cathos on Feb 11^th, 2004, 8:34pm

Perhaps transfering the marbles to different jars is legal. That may at least make it possible.

Title: Re: jars with marbles
Post by Nox104 on Feb 11^th, 2004, 10:22pm

I'm sorry I forgot to mention that you are allowed to take the marbles out of the jars. There are 2 possible solutions (I think). Before I give it out, I was just looking for another person's view

Title: Re: jars with marbles
Post by towr on Feb 12^th, 2004, 1:22am

In that case, I think this puzzle is equivalent to Forged Bags' Quick Identification (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1066488387)
Which means it's important to know at least a minimum to the unknown number of marbles in each jar..

Title: Re: jars with marbles
Post by Nox104 on Feb 12^th, 2004, 8:26am

Thanks for the link! I agree that it has to be an SSD (subset-sum-distinct) sequence, but all that formula got me confused.

ref to Barukh's post on that thread, what does 'n' stand for? Is it the number of bags? Then it doesn't work out correctly.

Anyway, I've thought of 2 simple answers to this question. I appreciate your comments.

1) Using the following SSD: (assuming there are infinite marbles in each jar)
1 + 2 + 4 + 8 +... + 512

2) You may contest this one!
Since they only want us to weigh once.. would a scheme of putting all the jars on the weight hold good? If yes, then, we take multiple readings by taking out one jar at a time from the weight. There would be only two kind of differences. One for the jars with 1g marbles and one for the jars with 1.1g marbles!!

But ofcourse, this is based on the premise that you can weigh this way. I am not sure if that is correct!

Title: Re: jars with marbles
Post by Nox104 on Feb 12^th, 2004, 8:33am

I forgot to add this to the 2nd solution:
Make sure that all the jars have the same number of marbles before putting them on the scale. (say 100 each)

Are there any variations of this puzzle? For example, how would you solve this puzzle, given that the upper bound for the number of marbles is just 256 (when we actually need 512 in the scheme I showed)? If there is any other series that satisfies the above constraints, can you write it out for me??

Thanks and btw, this is a great forum!

Title: Re: jars with marbles
Post by towr on Feb 12^th, 2004, 9:54am

on 02/12/04 at 08:26:58, Nox104 wrote:

ref to Barukh's post on that thread, what does 'n' stand for? Is it the number of bags? Then it doesn't work out correctly.

What 'n' stand for depends on which post you're talking about. There are different possible SSD's and Barukh asked for the one which needs the lowest number of coins in the bags (all bags have N coins).
As he hints in reply #6, "Hint: For 10 bags, N is far less than 512"

In his last post (reply #14), n indeed stands for the number of bags. And as he says the method he describes generates a non-trivial SSD. (Powers of two would be the 'trivial' one)

Title: Re: jars with marbles
Post by Jay L on Feb 2^nd, 2005, 8:00am

Hi, i just recently browsed through this forum and saw this and found it quite interesting. Here's a solution:

Assuming there are infinite # of marbles in each jar.

Line up the jars in some fashion.
Take 1 marble from the first jar
Take 2 marbles from the second jar
Take 3 marbles from the third jar
and so forth up to the ninth jar
Don't take any from the tenth jar

Put the marbles on the scale.

If the scale reads a whole number, then the tenth jar is the jar that contains the marbles that weigh 1.1g

If the scale reads #.1 then it is the first jar that contains marbles that weigh 1.1g (1x1.1 will give you #.1)

If the scale reads #.2 then it is the second jar that contains marbles that weigh 1.1g (2x1.1 will give you #.2)

If the scale reads #.3 then it is the third jar that contains marbles that weigh 1.1g (3x1.1 will give you #.3)

and so forth

I hope this makes sense to someone

Title: Re: jars with marbles
Post by Icarus on Feb 2^nd, 2005, 3:11pm

Alas, this is not sufficient: You are told that some jars have marbles weighing 1.1g, not just one jar. So for instance, if your weight came in at 0.3g over an integer amount, you have no way of knowing if jar 3 alone has 1.1g marbles, or if jars 1 and 2 both do, while the rest do not.

By the way, that brown text in towr's 2nd post is a link to the thread he discusses, if you want to give up and read the solution.

Title: Re: jars with marbles
Post by Lak on Feb 9^th, 2005, 5:32pm

To simply the problem:

you have 3 jars. label teh jars
1
2
4
(next would be 8, 16, 32, ect, but again, to simplify the example you only have 3 jars)

You take 1 marbel from the first, 2 from the second, 4 from the third
weigh them. lets pretend jar 1 and 3 have the 1.1 marbles... then the sum would be
1*1.1+2*1+4*1.1 = 7.5
since you placed 7 marbels on the scale, you can subtract 7 from 7.5 = .5. So yo uknow that 1+4 = 5 which means jar 1 and 3 had the 1.1 marbles.

-Lak

Title: Re: jars with marbles
Post by Icarus on Feb 9^th, 2005, 8:11pm

The binary approach is conceptually the simplist solution. But it is interesting to note that there are other solutions that involve fewer coins. To see, follow the link towr gives in his second post.

Title: Re: jars with marbles
Post by aditya_agr on Nov 23^rd, 2005, 5:10am

Take 1,2 .. 10 Marble/s from each Jar.
If we put all in weight machine in one shot it should weight ,55 (1+2+..+10).
Now let suppose 3rd Marble is Defected so WEight will be 3.3.So totol weight will be 55.3.
Now subtract :
Defected Marble Jar =(Final Value-Expected Value)*10;
i.e (55.3-55)*10 = 3 rd jar contains defected Marble

Title: Re: jars with marbles
Post by Icarus on Nov 23^rd, 2005, 8:21pm

And as I told Jay L when he suggested the exact same thing above, unfortunately, your solution does not always work. You are told that some jars have the heavy marbles, not just one.

In particular, if you come up with .3 as the excess weight, you have no way of telling whether Jar #3 alone has heavy marbles, or if Jar #1 and Jar #2 both do.

However, a slight modification of your plan, such as Lak describes two posts above yours, will work. And more complicated schemes exist which use fewer coins than his (as can be seen by following the link that towr gives).