Solution to cricket balls problem

Last week, I set a little brain-teaser. Out of 12 balls, eleven are normal, and the other is either heavier or lighter than the others. Using a simple set of balances no more than three times, find out which ball is the odd one out, and whether it’s heavier or lighter than the other balls.

(And may I add that it is while preparing this post that I realised that the functionality in Word that allows one to use mathematical symbols appears not to be recognised by WordPress!)

First, a bit of notation.

Define set N as the set of all balls known to be normal. (Before the first weighing, this set is clearly empty.)

Define set X the set of all balls not yet known to be normal.  (In other words, balls in this set could be light, or they could be heavy, or they could be normal … we just don’t know. Set X is the set of all unknowns – i.e. those balls about which we as yet know nothing.)

Define set H the set of all balls not yet definitely known to be normal, but known not to be light (i.e. any single ball in this set could be normal, or it could be heavy).

Define set L as the set of all balls not yet definitely known to be normal, but known not to be heavy (i.e. any single ball in this set could be normal, or it could be light).

It is also useful to define #S as the number of elements in any set S. So, if, say, #H= 3, then there are 3 balls in set H.

At each weighing, there are a number of possible outcomes. For each of these outcomes, different strategies must be applied. So, to ease understanding, any given point in the procedure will be described by a sequence of numbers indicating the outcomes at previous weighings. So, for instance, if we are considering point 1.3.2, then we have had 3 weighings; at the 1st weighing, we had Outcome Number 1;  at the 2nd weighing, we had Outcome Number 3; and at the 3rd (and final) weighing, we had Outcome Number 2. All possible combinations of outcomes will be considered, and the odd ball identified as heavy or as light by the end of the third weighing.

Right. Let us begin.

To begin with, all balls are in the set X . So  #X = 12.

Weighing 1:

Weigh 4 balls against 4 other balls. There are 2 possible outcomes:

  1. Both sides are equally balanced
  2. One side is heavier than the other.

Let us first consider Outcome1. (We will consider Outcome 2 later.) If the sides are equally balanced then the 8 balls we have weighed are now definitely known to be normal. The other 4 , that weren’t used in the weighing, aren’t yet known to be normal. So we have:

 #N = 8

 #X = 4.

Now, let us consider Outcome 2, where one side is heavier than the other. Clearly, the 4 balls that weren’t placed in the scales are all normal; none of the 4 balls on the heavier side can be light; and none of the 4 balls on the lighter side can be heavy. So we have:

#N = 4

#H = 4

#L = 4

Let us first follow the branch down from Outcome 1, where we have #N = 8 and #X = 4. The second weighing can now be as follows:

Weighing 2:

On one side of the scales, place 3 balls from set N, and on the other, place 3 balls from set X  .

                                    N N N     vs.     X X X  

There are 3 possible outcomes:

1.1  The side with the balls from set X  is heavier

1.2  The side with the balls from set  X  is lighter

1.3  The two sides are equal

If we have 1.1, then it is clear that the odd ball is one of the 3 balls from set  X that were used in the weighing. And it is also obvious that these balls cannot be light – i.e. they belong to set H. And all the other balls apart from these three are now known to be normal. So we have:

#N = 9

#H = 3

We may now solve the problem at the 3rd weighing:

Weighing 3:

Weigh one ball from set  H against another ball from set H.

H    vs.    H

There are two possible outcomes:

1.1.1      One side is heavier than the other – in which case, the ball on the heavier side is the odd ball, and it is heavier than the other 11.

1.1.2      The two sides are equally balanced – in which case, the ball from set  H that hadn’t been used in this weighing is the odd ball, and, once again, it is heavier than the other eleven.

Now, let us go back to Point 1.2, i.e. we have had two weighings, and at the second weighing,  the side with the balls from set  X  is lighter.

It is clear that the odd ball is one of the three balls from set  X  that were used in the weighting. And it is also obvious that these balls cannot be heavy – i.e. they’re all in set L. And all the other balls are now known to be normal. So we have:

#N = 9

#L = 3

We may now solve the problem at the 3rd weighing:

Weighing 3:

Weigh one ball from set against another ball from set  L.

L    vs.    L

There are two possible outcomes:

1.1.3      One side is heavier than the other – in which case, the ball on the lighter side is the odd ball, and it is lighter than the other 11.

1.1.4      The two sides are equally balanced – in which case, the ball from set L that hadn’t been used in this weighing is the odd ball, and, once again, it is lighter than the other eleven.

Now let us go back to consider Point 1.3, i.e. to the point where we have had 2 weighings, had Outcome 1 at the first weighing (i.e. the two sides were equally balanced), and Outcome 3 at the 2nd weighing,  the two sides are, again, equally balanced.

It follows that the odd ball out must be that one ball that had been in set X   after the 1st weighing, but which didn’t take part in the 2nd weighing; and also that all the other balls must be normal, i.e. we have

#N = 11

 # X  = 1

So we may now solve the problem with the 3rd weighing.

Weighing 3:

Put the ball in set X  on one side, and any ball from set N in the other.

X       vs.      N

If the side containing the ball in set X  is heavier, then the ball on that side is the odd ball, and is heavier than the others; if the side containing the ball in set  X  is lighter, then the ball on that side is the odd ball, and is lighter than the others.

We have now considered all possibilities from Outcome 1 at first weighing, and in each case, have solved the problem within three weighings, as required.

Now let us return to the first weighing, and consider how we should proceed if we had Outcome 2, i.e. if, when we weighed 4 balls against 4, one side was heavier than the other. As we said, we would then have:

#N = 4

#H = 4

#L = 4

In this case, for the 2nd weighing is as follows:

Weighing 2:

Place on each side of the scales 2 balls from set H, and one from set L.

H H L     vs.    H H L

There are two possible outcomes:

2.1  The two sides are equally balanced

2.2  One side is heavier than the other

Let us first consider 2.1.

If the two sides are equally balanced, then it is clear that the 6 balls used in the last weighing are now known to be normal, and that the odd ball is one of the two balls in set L that weren’t used in the last weighing. This gives us:

 #N = 10

#L = 2

So we may now solve the problem with the 3rd weighing.

Weighing 3:

Weigh one of the balls in set  L against the other ball in set L .

L    vs.    L

Obviously, the ball on the lighter side is the odd ball, and it is lighter than the other 11.

Now, let us return to Point 2.2, where, at the second weighing, one side was heavier than the other.

There can be two possible reasons for this:

(i)            One of the 2 balls in set  H on the heavier side is the odd ball, and is heavier than the others

(ii)           The ball in set  L on the lighter side is the odd ball, and is lighter than the others

In either case, the 2 balls in set L  that weren’t used in Weighing 2 are now known to be normal. Also, the ball in set  L on the heavier side, and the 2 balls in set  H on the lighter side, are all now known to be normal.

This gives us:

#N = 9

#H = 2

#L = 1

We may now solve the problem with the 3rd and final weighing.

Weighing 3:

Weigh one of the balls in set  H against the other ball in set H .

H    vs.    H

There are 2 possible outcomes:

2.2.1      The two sides are equally balanced

2.2.2      One side is heavier than the other

If we have 2.2.1, then, clearly, the two balls that were used in the 3rd weighing are now known to be normal. This means that the ball in set  L is the odd ball out, and is lighter than the others.

If we have 2.2.2, then clearly, the ball on the heavier side is the odd ball, and is heavier than the others.

We have now considered every single possibility, and have solved the problem, as required, within 3 uses of the scales.

(I often take this problem as an illustration of the importance of defining one’s terms well: if all terms are well defined from the start, everything tends to fall into place.)

Advertisements

6 responses to this post.

  1. Of course I couldn’t find the answer and I felt so stupid when my husband solved it in a minute.

    Reply

  2. Posted by Peter Gino Marchese on June 30, 2011 at 7:06 pm

    Ones first thoughts would be that each weighing yeilds to bits of information so that 4 weighings would be required, this is a common mistake, you must remember that a balanced situation is also possible hence three bits per weighing are produced so that three weighings are sufficient.

    Reply

  3. As you know from our email exchange, I got there by a slightly different method (with the help of a little prompting), but your explanation is much neater and more lucidly explained. Thanks for a fun & challenging problem!

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: