Very hard problem
You have n marbles (1 weigh different) , and one balance. Find the different weight one with least try." What is the smallest number of weightings for particular n?
Thanks in advance for your responses!
I would image you would divide N marbles in two, weight them. The side that is lower, you take those marbles, divide them and two. The side that is lower always must contain the heavier marble. Keep doing so until you find the heaviest
It's probably some variation of the 12 marbles problem (3^n), so for example it takes n=3 weighings to find the different marble in a group of 27 marbles. The problem gets harder if you don't know whether the coin is heavier or lighter than the others.
http://www.creatievepuzzels.com/spel/speel1/speel2/12bcoin.htm
@"MutualMonkey"
But I don't think that you actually know that false coin is heavier, you only know that it has different weight than other coins...
goblan, great link, tnx:D! Do you maybe know solution when you have for example 10 marbles?
goblan is largely correct. the answer you're looking for is:
roundUp(logbase3(n))
@"justin88": How did you come up with this answer? Is seems to me quite correct, but I would really like to find some proof for this, or at least an idea how to prove this or some link?
Came across this in my discrete math final last year. You can find the full explanation in the comments here http://www.cseblog.com/2013/11/weighing-problem-discrete-mathematics.ht…
Any optimal strategy constructs a decision tree; the maximum depth of this decision tree is the answer.
In this case, the decision tree has a branching factor of 3 (side1 heavier, side2 heavier, side1 == side2). Therefore, the depth of the tree is logbase3(n). You round up at the end because you want a whole number; i.e. 60 or 70 balls both will require weighing four times.
Another way to look at it: each of the n balls has three potential weights: { heavy, light, normal }. You need to search this space, which you can do logarithmically via divide and conquer.
This is hardly a very hard problem; it's a classic.
Tempora ipsum aut eaque sunt et autem. Velit quos cupiditate accusantium eum est. Eum eos rerum et molestias iste voluptas. Magnam adipisci fugiat voluptas.
Rerum autem et amet cupiditate voluptates natus consectetur. Tenetur neque consequatur est maiores ullam. Voluptas et doloribus repudiandae ea totam qui.
Dolorem sequi neque autem earum ducimus. Quaerat quo sed ut illum. Nihil ullam non quo aut. Provident fugiat provident expedita repudiandae beatae qui non dicta.
See All Comments - 100% Free
WSO depends on everyone being able to pitch in when they know something. Unlock with your email and get bonus: 6 financial modeling lessons free ($199 value)
or Unlock with your social account...