// file type: console application
// description : of twelve identical looking objects
// identify the one object which is heavier or lighter
// in a maximum of three balance scale observations

#include <tchar.h>
#include <iostream>
 
int obj[] = { 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0 };
 
struct ScaleResult
{
   bool balanced;
   bool groupA_isHeavier;
   bool groupB_isHeavier;
} scaleResult;
 
 
ScaleResult testWeight(int groupA, int groupB)
{
   ScaleResult result = { false, false, false };
 
   if (groupA == groupB)
      result.balanced = true;
   else if (groupA > groupB)
      result.groupA_isHeavier = true;
   else
      result.groupB_isHeavier = true;
 
   return result;
}
 
 
void printResult(int index, bool isHeavier)
{
   std::cout << "object weights = { ";
   for (int i = 0; i < 12; ++i) { std::cout << obj[i] << " "; }
   std::cout << "}\n";
 
   std::cout << "object number " << index + 1 << " is ";
   (isHeavier) ? std::cout << "heavier\n" : std::cout << "lighter\n";
}
 
 
 
int _tmain(int argc, _TCHAR* argv[])
{
   // observation test 1
   int weight_groupA = obj[0] + obj[1] + obj[2] + obj[3];
   int weight_groupB = obj[4] + obj[5] + obj[6] + obj[7];
   scaleResult = testWeight(weight_groupA, weight_groupB);
 
   if (scaleResult.balanced) 
   {
      // observation test 2
      weight_groupA = obj[5] + obj[6] + obj[7];
      weight_groupB = obj[8] + obj[9] + obj[10];
      scaleResult = testWeight(weight_groupA, weight_groupB);
 
      if (scaleResult.balanced)
      {
         // observation test 3
         scaleResult = testWeight(obj[0], obj[11]);
         if (scaleResult.balanced) { std::cout << "error: All objects even weighted\n"; return 0; }
         printResult(11, scaleResult.groupB_isHeavier);
      }
      else if (scaleResult.groupA_isHeavier)
      {
         // lighter object is in groupB
         // observation test 3
         scaleResult = testWeight(obj[8], obj[9]);
         if (scaleResult.balanced)
            printResult(10, false);
         else if (obj[8] > obj[9])
            printResult(9, false);
         else
            printResult(8, false);
      }
      else
      {
         // heavier ball is in groupA
         // observation test 3
         scaleResult = testWeight(obj[8], obj[9]);
         if (scaleResult.balanced)
            printResult(10, true);
         else if (obj[8] > obj[9])
            printResult(8, true);
         else
            printResult(9, true);
      }
   }
   else if (scaleResult.groupA_isHeavier)
   {
      // observation test 2
      weight_groupA = obj[4] + obj[5] + obj[0];
      weight_groupB = obj[6] + obj[1] + obj[11];
      scaleResult = testWeight(weight_groupA, weight_groupB);
 
      if (scaleResult.balanced)
      {
         // observation test 3
         scaleResult = testWeight(obj[2], obj[3]);
         if (scaleResult.balanced)
            printResult(7, false);
         else if (obj[2] > obj[3])
            printResult(2, true);
         else
            printResult(3, true);
      }
      else if (scaleResult.groupB_isHeavier)
      {
         // observation test 3
         scaleResult = testWeight(obj[4], obj[5]);
         if (scaleResult.balanced)
            printResult(1, true);
         else if (scaleResult.groupA_isHeavier)
            printResult(5, false);
         else
            printResult(4, false);
      }
      else
      {
         // observation test 3
         scaleResult = testWeight(obj[6], obj[1]);
         if (scaleResult.balanced)
            printResult(0, true);
         else
            printResult(6, false);
      }
   }
   else
   {
      // observation test 2
      weight_groupA = obj[0] + obj[1] + obj[4];
      weight_groupB = obj[2] + obj[5] + obj[11];
      scaleResult = testWeight(weight_groupA, weight_groupB);
 
      if (scaleResult.balanced)
      {
         // observation test 3
         scaleResult = testWeight(obj[6], obj[7]);
         if (scaleResult.balanced)
            printResult(3, false);
         else if (scaleResult.groupA_isHeavier)
            printResult(6, true);
         else
            printResult(7, true);
      }
      else if (scaleResult.groupB_isHeavier)
      {
         // observation test 3
         scaleResult = testWeight(obj[0], obj[1]);
         if (scaleResult.balanced)
            printResult(5, true);
         else if (scaleResult.groupA_isHeavier)
            printResult(1, false);
         else
            printResult(0, false);
      }
      else
      {
         // observation test 3
         scaleResult = testWeight(obj[2], obj[3]);
         if (scaleResult.balanced)
            printResult(4, true);
         else
            printResult(2, false);
      }
   }
 
   return 0;
}

Love these...took 30 seconds.

Absolutely no clue what you're talking about :P

Let's just say it doesn't look like my solution at all.

Took me less than a minute..

EDIT: Or so I thought.. I got it completely wrong, interesting how simple it seemed and I got an obvious error :)

Love these...took 30 seconds.

Absolutely no clue what you're talking about

Let's just say it doesn't look like my solution at all.

lov' you buddy.... <big kiss...smack>

Yeah, it would be great to see your solution...I'm a absolute semi-admirer of your work.

edit:

never mind. I see the solution over at mathisfun.com. well played...

Thanks HappyCoder, I enjoyed that. <serious>

You now know that the last weight is the special one, but you don't know if it's heavier or lighter than a normal weight.

Hm, actually missed that requirement...

Anyways the logic used for the 8 weights seems to work just fine for the 4 as well.

Think I got it now, though didn't go through it very well so may be some mistake..

Tried it with 9 first after reading frobs post which was easy, then thought about 12 again and seemed to work :)

[spoiler]

For 9:
1: 3 vs 3
if equal:
 2: 1 vs 1 from the last 3
 if equal:
  3: last 1 vs any to see if it's heavier or lighter
 else:
  3: heavier of the 2 vs any other to find out if it's the odd, or if the remaining is the odd and lighter
else:
 2: heavier 3 vs last 3
 if equal:
  3: 1 vs 1 from the lighter 3
   if one is lighter that is the odd one and lighter
   if they are equal the remaining 1 from the lighter 1 is the odd and lighter
 else:
  3: 1 vs 1 from the heavier 3
   if one is heavier that is the odd one and heavier
   if they are equal the remaining 1 from the heavier 1 is the odd and heavier


for 12:
1: 4 vs 4
if equal:
 2: 3 of the 4 remaining vs any 3 from the 8 that are determined equal in the first step
 if equal:
  3: the last 1 is the odd one, weigh it vs any to find if it's heavier or lighter
 else:
  we know now that the odd is in the 3 and whether it's heavier or lighter from the result of (2)
  3: 1 vs 1 of any from the 3
   if they are equal the remaining one is the odd (and we already know heavy vs light)
   if they are not equal the last is odd, and we already determined if it's heavy or light
else: (have 8, know which 4 are heavier and which 4 are lighter)
 call the heavier group A and lighter group B, and the unused (known regular) group U
 2: 3 vs 3 with A0 + B1 + B2 vs B0 + A1 + any U
 if A0B1B2 == B0A1Ux:
  A2 or A3 or B3 is the odd one:
  3: A2 vs A3
   if one is heavier it is odd and heavy, otherwise B3 is odd and light
 else if A0B1B2 is heavier than B0A1Ux:
  either A0 is heavy or B0 is light
  3: A0 vs any not B0
   if it's heavier it's odd and heavy, otherwise B0 is odd and light
 else (A0B1B2 is lighter B0A1Ux):
  either A1 is heavy or B1 or B2 is light
  3: B1 vs B2
   if one is lighter, it is odd and light
   otherwise A1 is heavy

[/spoiler]

I didn't read any of the above answers, maybe it's already in there, but i think this works:

[spoiler]

weight 6 vs 6

if one is heavier, split that into 3 vs 3

split the heavier one into 1/1 and take one away.

if the remaining two are equal, it's the one taken away, else the heavier one.

[/spoiler]

I didn't read any of the above answers, maybe it's already in there, but i think this works:

It doesn't.

The special weight might be heavier, or it might be lighter; you don't know.

You need to figure out 2 things:

- Which is the special weight?

- Is the special weight heavier or lighter than the normal weights?

Took me a while, but I managed to figure it out .

[spoiler]Step 1: balance 4/4, if they are balanced it's trivial to find to special one in the remaining 4 so I won't cover that.

Step 2: take 3 off the right side, swap the last one on the right side with one on the left, then put 3 normal weighs from step 1 on the right side. If the scale is balanced, the special one is in the 3 you took off, but since they were all on one side, you know whether the special weight is lighter or heavier than the rest, in which case you can randomly balance 1/1 and know which one it is.

Step 3: If the balance from step 2 hasn't shifted, you can eliminate the two swapped weights and 3 possibilities remain, but since these were also all on the same side, it falls back to what was explained in step 2. If the balance has shifted, it must be one of the two swapped weights.[/spoiler]

Are you sure 12 weights can be done in 3 steps? 9-weight version can be done in 3 steps, but I can't seem to find 3-step solution for 12 weights. There is that one case that needs the 4th-final step.

Anyway, here's mine:

[spoiler]

Split weights into sets of 4/4/4, let's call these S1, S2, and S3

1. Compare S1 and S2. If same, S3 is the problem set. Take two weights from either S1 or S2 (good weights) compare with two weights from S3:
   1. If same, remaining two weights on S3 contain the problem weight, do another comparison and you get the answer.
   2. If not, one of the two weights from S3 is the problem weight, do another comparison and you get the answer.
2. If not same, now we know S3 contains good weights, compare S3 with S1 or S2. Using S1 as example:
   If S3 == S1, S2 is the problem set
   If S3 != S1, then S1 is the problem set
   At this point, we also know if the problem weight is heavier or lighter.
3. Given a problem set S with 4 weights, and we know that the problem weight is lighter or heavier, we can do a binary search:
   Split S into two weights each, do comparisons until you reach the final weight.
   Now with 4 weights, this requires TWO comparisons to get to the final conclusion. But at this point, we have done two comparison, so that makes it 4 comparisons.

The 9-weight version, step 3 can be done by only one measurement:

Compare two weights. If they are not the same, then the problem weight is one of these two weights. Since we already knew the problem weight is lighter/heavier from previous measurements, we know which one. If the two weights are the same, then the other weight is the problem weight.

[/spoiler]