10
$\begingroup$

You are given 4 balls, all equal in weight except for one that is either heavier or lighter. You are also given a two-pan balance to use. In each use of the balance you may put any number of the 4 balls on the left pan, and the same number on the right pan, and push a button to initiate the weighing; there are three possible outcomes: either the weights are equal, or the balls on the left are heavier, or the balls on the left are lighter. Your task is to design a strategy to determine which is the odd ball and whether it is heavier or lighter than the others in as few uses of the balance as possible.

My solution is 3 weighting. However, some body told me he can get down to 2 weighting. Can someone please confirm this?

Improve this question
$\endgroup$
8
  • $\begingroup$ This is a puzzle, not a statistics question. You can find the odd ball of $4$ in $2$ weighings (a) if you do not need to know whether the odd ball is heavier or lighter or (b) if you have a fifth ball you know is of standard weight you can use. $\endgroup$
    – Henry
    Commented Oct 12, 2014 at 20:50
  • $\begingroup$ 4*2=8<9=3^2, so you can do it in 2 weightings. The approach was already described here: puzzling.stackexchange.com/questions/183/… $\endgroup$
    – klm123
    Commented Oct 13, 2014 at 7:28
  • $\begingroup$ @klm123 So that would be $o^w=2b$, where $w$="weighings", $o$="options" and $b$="balls"? So $9 \ge 8$. That would suggest that it's possible, but can you see an encoding of the possibilities of weighing to the configurations of the balls? $\endgroup$
    – d'alar'cop
    Commented Oct 13, 2014 at 9:22
  • $\begingroup$ @d'alar'cop, have you tried it? I almost sure that it is possible, but I am lazy here. I can try if nobody manages. $\endgroup$
    – klm123
    Commented Oct 13, 2014 at 9:33
  • $\begingroup$ @klm123 yes, I gave it a decent little go, but the problem is that I think there are certain possibilities that we need to exclude, like E E (equal equal) is impossible weighing all 4 balls (unless we have an unused ball) - then we can't determine if it's heavier or lighter. So, we are already down to 8:8, and there may be other encodings that won't work for similar reasons to the above. $\endgroup$
    – d'alar'cop
    Commented Oct 13, 2014 at 9:36

7 Answers 7

Reset to default
10
$\begingroup$

You can not do it in 2 weightings.
Let's prove it step by step.

  1. Initially you have 8 possible combinations: 1st ball is heavier, 1st ball is lighter, 2nd ball is heavier, .., 4th ball is lighter. So you must be able to set correspondence between outcomes or 2 weightings and 8 combinations.
  2. Each time you can put either 4 balls on the scale or 2 balls.
  3. Suppose you put 4 balls on the scale at least ones. In such a weighting only 2 outcomes would be possible: left is heavier or lighter. You can not have them equal since one and only one ball is not normal. In another weighting you can have maximum 3 outcomes. so in total you can 6 possible outcomes of 2 weightings, this is not enough to chose between 8 combinations.
  4. So each time you should put only 2 balls on the scale.
  5. Suppose you decided to compare A and B first, and C and D second. But at least one pair of the balls have equal weight. So you will have only 4 possible outcomes of such 2 weightings. This is not enough too.
  6. So you must do it differently. But then one of the balls will never be on the scale. Then, if it is not normal ball you won't be able to find out whether it is lighter or heavier.

It is easy to do in 3 weightings. d'alar'cop already done it, but I would write it too for completeness of my answer.
1.2. Weight A against B then C against D. Then you will know immediately 2 balls, which have normal weight. And two candidates for not normal ball. Suppose that A=B and C>D. Then either C is not normal heavy ball or D is not normal light ball.
3. Weight A+B against C+D. If C+D is heavier, then C is heavy ball. If C+D is lighter, then D is light ball.

You can do it in 2 weightings if you have 5th ball known to be normal for sure.. Let's call it E.
You can do it like it was done here for more complex problem. You may need to read the explanations there to understand the following, but in principle it is quite self explanatory.

Ball's arrangement:

Ball  A  B  C  D  E -A -B -C -D
W1    L     L  R  R  R     R  L 
W2       L  R  R  L     R  L  L

Weighing schedule of balls:

Weighing 1:  A C / D E
Weighing 2:  B E / C D

The outcomes interpretation:

L = : AH  R = : AL  
= L : BH  = R : BL  
L R : CH  R L : CL
R R : DH  L L : DL
Improve this answer
$\endgroup$
9
  • $\begingroup$ this is good and complete. and the explanation of why it cannot be done in 2 is just great $\endgroup$
    – d'alar'cop
    Commented Oct 13, 2014 at 10:13
  • $\begingroup$ Might be worth editing your summary to say that it can be done in two weighings if you're lucky, which is perhaps where the OP's friend got his figure of two from. $\endgroup$
    – Richiban
    Commented Oct 13, 2014 at 13:30
  • $\begingroup$ @Richiban, it can be true about OP's friend, but I do not agree that this can be related to the puzzle. It can be done in 0 weights if you are lucky - just guess, that 1st ball is the odd one. By design nobody should care about luck in this type of puzzles, you must guaranty to find the ball. $\endgroup$
    – klm123
    Commented Oct 13, 2014 at 13:51
  • $\begingroup$ It's not the same as guessing, but I take your point. I was saying that certain logical paths through the procedure require only two uses of the scales, i.e. when your first weighing of two balls results in the scale tipping. I was intending that this was a message that the OP could take back rather than just "No, you're wrong. It's three". :) $\endgroup$
    – Richiban
    Commented Oct 13, 2014 at 14:56
  • $\begingroup$ @Richiban, if you think this is relevant, you can create your own answer from this.:) $\endgroup$
    – klm123
    Commented Oct 13, 2014 at 15:28
6
$\begingroup$

Label the balls ABCD. Weigh A and B. Then weigh A and C.

  • If A is the odd ball it will be lighter or heavier in both weighings and you have solved it
  • If B is the odd ball, it will be lighter or heavier in the first weighing and the second weighing (which balances) will confirm it is B that is the odd ball
  • If C is the odd ball, you will know A is standard so the second weighing gives the solution
  • If D is the odd ball you will know this after the second weighing, because A, B, and C were all equal, but if you need to know whether it's lighter or heavier you cannot escape a third weighing. If it's enough to know which is different, two weighings are enough.

So you have a 75% chance of solving it completely in two weighings, and a 25% chance of only identifying the odd ball in two weighings, and needing a third to know if it is heavy or light. I think this is the best that can be done.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Why the downvote? This answer is correct, concise, and complete. $\endgroup$
    – user3294068
    Commented Oct 13, 2014 at 14:52
  • $\begingroup$ @user3294068, I downvote too because the answer is not relevant. Here is the question: "some body told me he can get down to 2 weighting. Can someone please confirm this?". The OP knows solution in 3 weightings and asked a question about solution in 2 weightings, this answer meanwhile totally ignores it in my opinion. $\endgroup$
    – klm123
    Commented Oct 14, 2014 at 16:46
  • $\begingroup$ Ah. What was not included was explanation/proof that this approach is optimal. $\endgroup$
    – user3294068
    Commented Oct 15, 2014 at 18:15
2
$\begingroup$

You cannot. It can be derived (although it's a bit longish) that the maximum number of balls you can resolve with N weightings is $(3^N-3)/2$. For N=2 that's only three and not four. However if you have one extra "known good" ball at your disposal you can up this to $(3^N-1)/2$, so in this case 4 would be possible.

Here is a outline of the proof assuming N weightings and K balls

  1. Each weighting has three possible outcomes.These form a tree structure and the number of leaves at the end of the tree is $3^N$.
  2. The number of solutions (e.g. #4 is heavy, #12 is light, etc.) is $2*K$
  3. The puzzle can be solved my mapping the solutions on the tree structure. At every weighting the solution spaces gets divided into three sub sets that than progress down the tree in the next step
  4. The puzzle is solvable if every solution ends up at a unique leaf
  5. We can immediately see that number of leaves must be equal or larger than the number of solutions. So we have $K <= 3^N/2$. Since $3^N$ is odd and K is an integer we get $K <= (3^N-1)/2$
  6. If you only have unknown balls, you have start with a weighting of M unknowns against M unknowns. If the scale moves the number of remaining solutions is $2*M$. If it doesn't move the number of remaining solutions is $2*(K-2*M)$. These are all even numbers.
  7. At every weighting you need to split the solution space in three equal parts, however $3^N/3$ is always an odd number so you can't do this perfectly with only even numbers and the best you can do is split the solution space into three parts of $3^N/3-1$ and we get the max possible number of balls to be $(3^N-3)/2$

So in the case of N=2 and K=4 we have a 9 leaves and 8 possible solutions. However in the first weighing we can split the solution space either 2/2/4 or 4/4/0. In either case you have a "4" in there which can't be resolved in only one weighting which has only 3 outcomes.

Adding the known good ball allow you to split the solution space into 3/3/2 and hence this works.

Improve this answer
$\endgroup$
1
$\begingroup$

Here is a more succinct answer to why it is impossible in 2 weighings.

You have 8 cases to discriminate. Identify the ball and whether it is heavy or light.

On the first weighing, your only choice is to weigh 1 against 1 ball or 2 against 2 balls.

  • If you weigh 2 against 2, the scale cannot balance, so you have only 2 outcomes. Each outcome leaves 4 possibilities that you cannot discriminate in a single weighing.

  • If you weigh 1 against 1, and the scale balances, the odd ball is one of the remaining balls, either heavy or light. It leaves 4 possibilities which, again, one weighing is not enough to discriminate.

Note that if you only need to identify the odd ball but not tell whether it is heavy or light, it can be done in 2 weighings. I think this is what was meant when someone told you it can be done.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Ooh, this is elegant. $\endgroup$
    – Lopsy
    Commented Dec 21, 2014 at 13:38
-1
$\begingroup$

This strategy involves a case where 3 weighings are required. I would contend that it is impossible to handle that case without 3 weighings.

Pick 2, A and B, and weigh them against each other.

If A and B are equal, then I'm afraid that a solution cannot be found within the 2-weighing limit. Weigh C and D. One will be lighter or heavier - call C the lighter. Weigh A and C, if A and C are equal, then D is the odd one out and is heavier. If A and C are not equal, then C is the odd one out and is lighter.

If A and B are not equal, call A the lighter one, then pick another one C, and weigh A and C. If A and C are equal, then B is the odd one out and is heavier. If A and C are not equal, then A is the odd one out and is lighter.

Done, in 2 weighings minimum and 3 weighings maximum.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Your first case is 3 weightings. $\endgroup$
    – Miniman
    Commented Oct 13, 2014 at 2:32
  • $\begingroup$ @Miniman I'm working on that $\endgroup$
    – d'alar'cop
    Commented Oct 13, 2014 at 5:30
-1
$\begingroup$

You balance 2 balls (A & B). 1 in each side of the scale, and leave 2 out. (C & D)

Case 1. If one of those balls is heavier, then you can assume that the 2 balls out are fine. So you weight the heavier with one of the 2 out ones. If its still heavier, then you have your answer. If it's equal in weight, then the other (A or B) is the bad one. (2 weightings)

Case 2. Both A & B are balanced. That means that either C or D are the bad/defective one. You use C and balance it with either A or B. If they are balanced, then D is the problem. If they are not balanced then C is the problem. (2 weightings)

Improve this answer
$\endgroup$
1
  • $\begingroup$ What if A & B weigh the same so you weigh A & C instead and they weigh the same. Now you know that D has a different weight but you don't know if it weighs more or less. You've only solved half the problem. $\endgroup$
    – Engineer Toast
    Commented Apr 20, 2015 at 16:10
-4
$\begingroup$

Lets call the balls A,B,C,D. Put AB on the left and CD on the right. If AB is lighter/heavier put A on the left and B on the right and you find the exact one that is lighter/heavier. Other case is CD is lighter/heavier then put C on the left and D on the right and you can find the lighter/heavier exactly. So always in 2 weighins

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ what does lighter/heavier mean? if the first weighing one side is heavier than the other, this doesn't give any information about which side has the odd ball. " If AB is lighter/heavier" - "Other case is CD is lighter/heavier " - both of these things will be true. $\endgroup$
    – d'alar'cop
    Commented Oct 13, 2014 at 7:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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