256
Logo

Gray Watson's Answer to the 12 Balls Question

The following is the answer to the "12 Balls" question from my brain teasers page. There are (at least) 2 solutions to this problem. The first way I figured it out is to weigh some balls and then based on the result, determine which balls to weigh next. I've posted details about that solution.

After some prodding by some people that there was an alternate method, I figured it out in the following manner. You can configure which balls to weigh and how for all 3 of the weighings beforehand and then look at the results to determine which ball is different. I've included my small C program at the bottom of the page with which I verified my algorithm. Yes, I am a geek.

Solution

Basically you will be weighing the 12 balls as 3 sets of 4. For each weigh, 4 balls go on the left-hand part of the scale, 4 balls go on the right-hand part of the scale, and 4 balls are off-scale. Basically you need to find a unique pattern for each ball so when you look at the 3 weighs, you can tell which ball is different and how it is. For example, take ball #1 and put it on the left hand side (L) for the 1st weigh and off-scale (-) for weighs 2 and 3. The produces the pattern "L--". Put ball #2 off-scale on the 1st weigh, left-side for the 2nd, and off-scale for the 3rd weigh (pattern "-L-"). The 3rd ball's pattern should be "--R".

To determine the specific ball, the patterns must be unique and can't have a mirror. For instance, if ball #1 is "L--", there must not be another ball which is "L--" nor can there be a ball which is "R--". If a ball is "LRL" then another ball can't be "RLR".

So I worked out a set of patterns which are unique and not mirrored. I did it by hand although there is probably a set of rules to use to do it, and a program would be easy to iterate them all.

Ball # -> 1 2 3 4 5 6 7 8 9 10 11 12
Weighs 1 Left - - Left Left RightRight - - Left RightRight
2 - Left - - - LeftRight LeftRightRight LeftRight
3 - - Right LeftRight - - RightRight Left Left Left

So ball #6 should be on the right-side of the scale for the 1st weigh, the left-side for the 2nd weigh, and off-scale for the 3rd ("RL-"). Ball #12 should be on the right-side for the 1st weigh, right-side for the 2nd, and left-side for the 3rd ("RRL").

So if you use these patterns, if the scale goes down to the left on the 1st weigh, down to the left on the 2nd weigh, and is even the 3rd weigh you should be able to figure it out. You would look for a ball whose pattern is "LL-" or "RR-". Only ball #7 ("RR-") matches this and since the scale went down to the left and the #7 was on the right side, it must be lighter than the others.

C Program

So I wrote a quick little C program to verify my algoritm above. Enjoy.

/* 12 balls program #2, copyright gray watson, http://256.com/gray/ */

#include <stdlib.h>
#include <stdarg.h>

#define BALL_N		12
#define NORMAL_WEIGHT	10
#define MAX_WEIGHS	3

static int balls[BALL_N + 1];		/* ball weights */
static int weight_c = 0;		/* number of weighs performed */

/* positions of each ball for each weight, position 0 is not used */
static char weigh1_positions[] = " L--LLRR--LRR";
static char weigh2_positions[] = " -L---LRLRRLR";
static char weigh3_positions[] = " --RLR--RRLLL";

/* returns: <0 if right heavier, 0 if equal, >0 if left heaver */
static int weigh(const char *positions)
{
  int ball_c, ball, total = 0;
  
  weight_c++;
  if (weight_c > MAX_WEIGHS) abort();
  
  for (ball_c = 1; ball_c <= BALL_N; ball_c++) {
    if (positions[ball_c] == 'L') {
      total += balls[ball_c];
    }
    else if (positions[ball_c] == 'R') {
      total -= balls[ball_c];
    }
  }
  
  return total;
}

/*
 * Do the 3 weighs and then figure out which ball is different.  It
 * will return the number of the ball as a negative number if it is
 * lighter than the others or a position value if it is heavier.
 */
int do_it(void)
{
  int	ball_c, weigh1, weigh2, weigh3;
  
  weigh1 = weigh(weigh1_positions);
  weigh2 = weigh(weigh2_positions);
  weigh3 = weigh(weigh3_positions);
  
  /* check for heavier */
  for (ball_c = 1; ball_c <= BALL_N; ball_c++) {
    switch (weigh1_positions[ball_c]) {
    case 'L':  if (weigh1 <= 0) continue;  break;
    case 'R':  if (weigh1 >= 0) continue;  break;
    case '-':  if (weigh1 != 0) continue;  break;
    }
    switch (weigh2_positions[ball_c]) {
    case 'L':  if (weigh2 <= 0) continue;  break;
    case 'R':  if (weigh2 >= 0) continue;  break;
    case '-':  if (weigh2 != 0) continue;  break;
    }
    switch (weigh3_positions[ball_c]) {
    case 'L':  if (weigh3 <= 0) continue;  break;
    case 'R':  if (weigh3 >= 0) continue;  break;
    case '-':  if (weigh3 != 0) continue;  break;
    }
    return ball_c;
  }
  
  /* check for lighter */
  for (ball_c = 1; ball_c <= BALL_N; ball_c++) {
    switch (weigh1_positions[ball_c]) {
    case 'L':  if (weigh1 >= 0) continue;  break;
    case 'R':  if (weigh1 <= 0) continue;  break;
    case '-':  if (weigh1 != 0) continue;  break;
    }
    switch (weigh2_positions[ball_c]) {
    case 'L':  if (weigh2 >= 0) continue;  break;
    case 'R':  if (weigh2 <= 0) continue;  break;
    case '-':  if (weigh2 != 0) continue;  break;
    }
    switch (weigh3_positions[ball_c]) {
    case 'L':  if (weigh3 >= 0) continue;  break;
    case 'R':  if (weigh3 <= 0) continue;  break;
    case '-':  if (weigh3 != 0) continue;  break;
    }
    return -ball_c;
  }
  
  abort();
}

int main()
{
  int	diff_c, ball_c;
  
  /* init all of the balls */
  for (ball_c = 1; ball_c <= BALL_N; ball_c++)
    balls[ball_c] = NORMAL_WEIGHT;
  
  for (diff_c = 1; diff_c <= BALL_N; diff_c++) {
    (void)printf("Odd is %2d: ", diff_c);
    
    weight_c = 0;
    balls[diff_c] = NORMAL_WEIGHT - 1;
    if (do_it() != -diff_c) abort();
    (void)printf("lighter, ");    
    
    weight_c = 0;
    balls[diff_c] = NORMAL_WEIGHT + 1;
    if (do_it() != diff_c) abort();
    (void)printf("heavier\n");    
    
    balls[diff_c] = NORMAL_WEIGHT;
  }
  return 0;
}
/* end of program */

Free Spam Protection   Eggnog Recipe   Android ORM   Simple Java Magic   JMX using HTTP