3
$\begingroup$

Suppose there are $N$ marbles and a two-pan balance used to compare the weight of 2 things. All of the marbles weigh the same except for one, which is heavier than all of the others. How would you find the heaviest marble in minimum number of comparisons.This link explains for $N=12$ .I have tried solving for $N$ but haven't come up with any solution.How it be can generalised for $N$ marbles? Explain in detail.

$\endgroup$
  • $\begingroup$ The link is for a similar problem, where you don't know whether the odd marble is heavier or lighter. I think that takes $\log_3\lceil2N+3\rceil$ weighings. $\endgroup$ – Empy2 Nov 19 '15 at 15:18
  • $\begingroup$ @DCoder can you please indicate what additional details you would like? $\endgroup$ – Ian Miller Nov 24 '15 at 6:26
4
+50
$\begingroup$

Each weighing can reduce the number of possibilities to $1/3$ of that from before, using the same argument as in the example you linked. If you have $3^n$ marbles, then you need at least $n$ weighings to find the heavier marble. If you have $3^n < N \leq 3^{n+1}$ marbles you should need $n+1$ weighings--since $N$ is not a power of three, some weighings are not as 'efficient' as possible. (i.e. don't eliminate exactly $2/3$ of possibilities since possibilities are no longer divisible by 3. In the worst case scenario, $\lceil N/3 \rceil$ possibilities remain after an 'inefficient' weighing.) Thus the number of weighings needed is

$$\lceil \log_3(N) \rceil $$

$\endgroup$
2
$\begingroup$

Divide your marbles into three groups. Compare group 1 vs group 2. If they are the same then you know the heavier marble is in group 3. If group 1 is heavier then the heavier marble is in group 1. If group 2 is heavier then the heavier marble is in group 2. Repeat this process until you are comparing individual marbles. If you have a situation where you can not divide them evenly by three use marbles that have already been identified as normal to make up the difference. If the initial number of marbles doesn't evenly divide by 3 then make group 3 have one more or one less marble in it.

Each step will reduce the number of remaining (unidentified) marbles to a third (rounded up). So if there are N marbles after the $x^{th}$ weighing you will have only $\lceil\frac{N}{3^x}\rceil$ left. You want to continue until you get down to one. In the base case you'll have $N=3^x$. In the worst case $N=3^{x+1}-1$. So you will require $\lceil\log_3N\rceil$ weighs.

$\endgroup$
0
$\begingroup$

Sometimes, depending on the value of N, one can indirectly glean more info by combining multiple weighings.

For example, I was recently given this very problem as a tech test for N = 25, with the requirement to identify the heaviest in no more than 3 weighings.

After much pencil chewing, I came up with the following solution.

First note that if we know the heavier marble is one of a set of 3 marbles, then it can be easily determined by a single weighing of 1 against 1, which indicates either the heavier marble directly or, if these balance, indicates that the 3rd marble is the heavier one.

  1. Put aside 9 marbles, and weigh the remaining marbles 8 against 8.

  2. If this 8-by-8 weighing is balanced then the heaviest is among the 9 marbles, and in that case weigh 3 of these against another 3. If this is also balanced then the heavier is one of the remaining 3. Otherwise it is among the heavier 3 weighed, and in either case the heavier marble can be determined by one further weighing (see preliminary note above).

  3. If the 8-by-8 weighing is not balanced then remove 3 marbles from each side, and weigh the remaining 5-by-5 pair.

  4. If the 5-by-5 weighing is balanced then the heaviest is among a known one of the pair of triplets removed. So again (see preliminary note) it can be determined in one further weighing.

  5. If the 5-by-5 weighing is not balanced then remove one marble from each side, and make a third and final 4-by-4 weighing.

  6. If the 4-by-4 weighing is now balanced then the heavier marble is a known one of the pair removed.

  7. If the 4-by-4 weighing is still not balanced, then we're stuffed. Or are we?! ..

Note that in the latter case, in retrospect, none of the marbles removed or discounted are the heavier one, and the heavier one must be among the pair of 4 marbles just weighed.

So the final twist is to choose at the outset a fixed set of 4 marbles on either side of the 8-by-8 pair, and not remove these but between weighings swap pairs of these preassigned marbles judiciously to opposite sides of the balance so that each marble, were it the heavier, would give a unique "signature" of whether (say) the left hand side of the balance is heavier (H) or lighter (L), and as luck would have it there are 8 possible combinations for the 8 marbles LLL, LLH, LHL, .. HHH

Expressing this another way, treat the successive 4 preassigned pairs of marbles as follows:

  • leave the 1st pair unswapped for all 3 weighings
  • swap the 2nd after the 2nd weighing
  • swap the 3rd after the 1st weighing and back after the 2nd weighing
  • swap the 4th after the 1st weighing and leave unchanged for the 3rd weighing

Then if the result of the three unbalanced weighings is HLH we can deduce that it must be a known one of the 3rd pair.

$\endgroup$
  • $\begingroup$ This is needlessly complicated. Just take the approach you outlined in step 2 (if you know it's in the group of 9)—you can also apply this if you know it's in one of the groups of 8. (Which is what the other answers say.) Thus it takes $\lceil \log_3(25) \rceil$ weighings, that is, 3. $\endgroup$ – Nick Matteo May 20 at 17:44
  • $\begingroup$ Yes of course, DOH! And I was quite pleased with my solution ;-( $\endgroup$ – John R Ramsden May 20 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.