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!
Trending Content
| +15 | Full Time Timeline | 1 | 6d | |
| +13 | Iron Ore Trading? | 12 | 4d | |
| +9 | AVP / AD Fixed Income Trader Salary | 1 | 1d | |
| +9 | Question on SA 2025 SnT timings | 1 | 3d | |
| +4 | Understanding the Yield Curve | 2 | 2d | |
| +3 | Difference in ops between Glencore and Trafigura. Commodities, path to trader, enjoyment of ops. | 1 | 4h | |
| +3 | What NOT To DO in S&T and Banking | 3 | 1d | |
| +3 | Citi lateral hire | 2 | 1h |
Career Resources
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.
Iusto blanditiis quasi quo consequatur officiis. Quo excepturi sunt ut nam non minima mollitia. Ut blanditiis ratione ut sint earum ut autem cupiditate. Officia vitae molestiae occaecati quisquam est quibusdam neque hic.
In non neque quia fuga dignissimos. Non fugiat laboriosam quia ea rerum et. Aut vel voluptas qui autem voluptas ut. Hic incidunt et et laborum distinctio placeat est. Dicta excepturi adipisci ipsa quod minima qui. Minus eius et ipsum inventore architecto.
Nemo qui sapiente voluptatem ut. Aliquam eum illo est aspernatur. Reprehenderit fuga non numquam et dolor nemo repudiandae. Sint earum est labore ad pariatur ab eos aliquid.
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...