4
$\begingroup$

In this weighing problem objects of four different weighs are to be identified with four weighings with a balance scale.

Now given that the four weights are all different, on one hand, there are $4!=24$ possibilities how the weights can be distributed.

On the other hand, each weighing can in principle give three different answers (left side is more heavy, right side is more heavy, scale balanced). Therefore three weighings can give $27$ different results.

Now from those numbers one might guess that three weighings should be sufficient to identify the objects. However with the weights given in that question, one can show that the objects can not be reliably identified with at most three weighings.

Now the question is: Is there any other set of four different weights so that the objects can be distinguished in just three weighings?

$\endgroup$
  • $\begingroup$ Can you clarify what do you mean by other in "any other set of four different weights"? Do you have one example in your mind already? $\endgroup$ – Matsmath Sep 21 '16 at 8:25
  • 1
    $\begingroup$ Just a thought: in the first weighing, if all weights are indistinguishable, it seems that the only important results are both sides equal or both sides not equal. This means that 3 weighings would actually yield only 2*3*3 = 18 different results, which may not be sufficient if your premise is that there are 24 possibilities. Still working on an answer, though... $\endgroup$ – Xenocacia Sep 21 '16 at 8:32
  • 1
    $\begingroup$ @Matsmath: The linked question uses the set {3,5,8,11}. Any other set of four different weights means exactly that: Four weights that are all different, and are obviously not {3,5,8,11}, but are otherwise arbitrary, except for that they should allow distinguishing in at most three weighings. And no, I didn't have any example in mind; it's a genuine question. $\endgroup$ – celtschk Sep 21 '16 at 17:01
  • $\begingroup$ @Xenocacia: No, I can for example for put one object on one side, and two on the other side. Then I can get three different results: (1) The one object is more heavy than the other two (e.g., if in the original puzzle, I weigh the 11oz ball vs. the 3 oz and the 5 oz objects). (2) The one object balances the two other objects (e.g., if in the original puzzle I weigh the 11oz object against the 3oz and the 8oz objects). (3) The one object is lighter than the other two objects (e.g. if in the original puzzle I weigh the 11 oz object against the 5oz object and the 8oz object). $\endgroup$ – celtschk Sep 21 '16 at 17:06
  • $\begingroup$ @Xenocacia: And even if I weigh 2 objects against 2 objects, not only whether it is balances, but also which side goes down gives me information:; namely (unsurprisingly) which side is the more heavy one. In particular, given two objects of different weight, if you were right, I could not distinguish which is which, as all I can do is to put them on both sides of the scale, and I already know before weighing that one side will go down. But indeed, seeing which side goes down definitely allows me to identify which of the objects is the heavier one. $\endgroup$ – celtschk Sep 21 '16 at 17:13
3
$\begingroup$

OK, I now figured it out myself:

It is not possible to do it in three weighings.

Let's start with some general observations for the first weighing.

For any of the three possible results (one side more heavy, other side more heavy, equilibrium), there have to be at most $9$ possibilities remaining, as the two remaining weighings can at most have $9$ different outcomes. Since there are $24$ possibilities in total, this implies that each result needs to leave at least $6$ possible weight assignments, as the other two can at most cover $18$ possibilities.

Now with this observation, it is easy to weed out all but one possibility for the first weighing:

Obviously an $1:1$ weighing (one object against a single other) cannot give equilibrium, so that can be immediately excluded. A $1:2$ weighing where one of the two lightest objects is the single one will always give that the two balls are more heavy; those already give 12 possibilities, so that obviously doesn't work either. A $1:3$ weighing will necessarily give a heavier weight on the three-object side if the heaviest object is among those three; but if the heaviest object is alone, then you have only one possible result, so at least one result is impossible. So the only viable first weighing is a $2:2$ weighing.

This then gives a first constraint on the weights:

Obviously the most heavy two objects are always heavier than the two lightest object. Also the most heavy and the second-lightest object are together heavier than the two remaining objects. So the only way equilibrium can be achieved is if the most heavy and the lightest object together have the same weight as the two remaining ones.

If this condition is fulfilled,

the $2:2$ measurement gives exactly $8$ remaining possibilities for each of the results, so that is actually perfect.

Now after having identified the correct first measurement, let's look at how to continue:

Let's look at the case where we have equilibrium. Again, we can figure out that any result has to leave at most $3$ possibilities (or otherwise there's no way to distinguish them with a single weighing) and at least $2$ possibilities (or else the other two results would need to cover more than the maximal $6$ possibilities).

For the same reasons as before, we can exclude $1:1$ and $1:3$ weighings. Moreover, the second weighing cannot be another $2:2$ weighing, as the only way we can get more information is if we take on each side one object from each side of the first weighing; but for that configuration we already know that equilibrium cannot be achieved.

So the only weighing that might work as second is a $3:1$ weighing. Let's again consider the case where we have equilibrium.

Obviously, if we have equilibrium, the single ball is one of the two heaviest. Moreover, since the middle two weights are heavier than the most heavy one, we know that the lightest object is among the two objects on the other side of the scale. But this means that for each of the two possible single objects, we can identify which of the two objects is the lightest: If the single object is the most heavy one, the lightest is the one which was on the same side of the scale for the first weighing, otherwise it's the one which was on the other side.

Therefore the only way we can get two possibilities at equilibrium is if both the second-most heavy object weighs the same as the two lightest together, and the most heavy object weighs as much as the second-most heavy and the lightest together.

Together with the condition from the first weighing, this means that if there is a solution at all, it has to be of the form $\{a,2a,3a,4a\}$.

But in that case, the only way the single object is more heavy than the two objects on the other side is if the single object has weight $4a$ and the two objects on the other side are the objects with weights $a$ and $2a$. But that violates the condition that each result needs to leave at least two remaining possibilities.

Therefore there is no combination of four different weights that can be reliably distinguished with only three weighings.

$\endgroup$
1
$\begingroup$

I think three measurement are sufficient under three conditions.

Condition n. 1

You start always with a measurement 2 vs 2. If you are unable to identify the heavier, there is too much indeterminatin. Condition number 1 is Heavier + lighter > the two added wheigts. If you are unable to identify the lighter: same thing.

Condition n.2

If condition is satisfied, lets put in an ideal order the wheigt from the most heavy: A (most heavy) B C and D (most light) You have 3 different cases. In each one you can determine (with the second and the third measurement) which is the most heavy of the first heavier couple and which is the most light of the first lighter couple. If in the heavier couple there are A and D, everithing is fine. If it is not, you can still determine the most heavy and the most light, but nothing can be said about the other two If you don't know which case you have in the first measurement, there is indetermination. So second condition is that B and C has to be the same wheigt

Excluding other cases (proving condition 3)

A and B have the same weight: is not ok. There is indetermination unless you know that the two equals are the most heavy
C and D have the same weight: again the same condition
B and C have the same weight: everything is fine if condition 1 is satisfied AND again you know that the two equals are nor the most heavy neither the most light.

So my answer is

You must have 3 rules
1- The sum of the weight of the must ligth and must heavy item is bigger than the sum of others two
2 - Two weight has to be equal
3 - You must know before which types there is of wheigt has a duplicate (heavy, middle or light) without knowing specifically which is

Variant

3b (instead of 3) You must know that 2 specific wheight are equal (without knowing if are the most havy or the most ligth or the 2 middle weight)

$\endgroup$
  • 1
    $\begingroup$ OP said that it had to be a set of 4 different weights, though. I think that means your second condition might not be applicable. $\endgroup$ – Xenocacia Sep 21 '16 at 8:13
  • $\begingroup$ @Xenocacia yes, you are right. I tried to analize the situation (not pretending to be right or exaustive at 100%) to verify when 3 measurement can be sufficient to put 4 weigths in order. Comes out that for me 2 has to be equal. Yes, my conclusion is that four different weights (intended as 4 different values and not as 4 different object to measure) are too many for 3 measurements. $\endgroup$ – marcoresk Sep 21 '16 at 8:33
  • $\begingroup$ @Xenocacia may I ask what "OP" stands for? (I understand that it referres to the person who proposed the problem, but english is not my mother-tongue) $\endgroup$ – marcoresk Sep 21 '16 at 8:36
  • 1
    $\begingroup$ I see, so your answer is that 4 different weights cannot be distinguished in 3 weighings? I'm tending to the same conclusion. By the way, OP stands for Original Poster. :) $\endgroup$ – Xenocacia Sep 21 '16 at 8:38
  • $\begingroup$ Why does the first measurement have to be 2 vs. 2? $\endgroup$ – celtschk Sep 21 '16 at 17:16

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.