Imp Pow 15: 12 Bags Of Gold

Problem Statement

There are twelve items numbered 1 through 12. All of the values or "weights" are the same except one item whose value is either greater than or less that the other 11 by an unknown amount.

One can compare the sum of the values of a number of items in a set with the sum of the values of items in a disjoint set to see which one is greater. This comparison is also called "weighing."

Find the least number of ways to determine which item has a greater or lesser value.

Process

From the previous POW it was concluded that it would take 5 weighings as described by the equation for an unknown item value:

However, this is an overestimate as there is a way to determine the lighter of nine items with only two weighings. This was overlooked in the last POW (Eight Bags of Gold). Nine items can be weighed by dividing into three sets of size three. Comparing two sets together would determine which set contained the lighter item. With the last weighing, one can determine the lightest item.

This raises the limit of weighings meaning that it would take a mere three weighings to single out the different item out of a set of 27.

Anyway, determining the item which is either lighter or heavier out of 12 is claimed to need only three weighings. It can be done in four because the largest power of three that's within 12 is 33, hence taking three to determine which item is the faulty one. Because the item isn't known to be greater or lesser in value than the other 11, it takes one more. This sets a limit at 4 weighings, at most.

The previous method described goes by a method where the original set of 12 is divided into four sets of three. This is the most efficient method if the sets aren't remixed when measuring. This is also the most efficient if only an imbalance is noticed, and not the direction of the imbalance. To make the method of singling out the unknown valued item out of 12 more efficient to three comparisons, more observation is needed. Also, it is known that one cannot accomplish this in two measurements because it takes two measurements to determine the greatest out of three.

Solution

The way to determine which single item out of 12 is different and how it is different (having a value greater than or less than the other 11) can be done in three comparisons. Here's how:

Start with four sets of three. Compare any two sets with each other. If the sum of the values of each element in each set is equal, then the comparison would come out to be equal. If they are different, then it is known that the different item is in one of the two sets, or six items, being compared. This step just isolates which six items is possibly the lighter and that the other six are all normal. Keep a note of which set is greater (or which set is lesser, it's all relative), call this the orientation of the weighing. These three facts are important for later on. Suppose a set with items (1, 2, 3) is compared against a set with items (4, 5, 6). Without loss of generalization, one can assume that these two sets are unequal because if they are, then it is known that the other two sets are unequal. That's one comparison.

Then, one needs to switch some items around. Switch item 3 with item 4 and then take two items from the two other "normal" sets: . Since it is already known that the items from these two sets are not the different item, they are the Ð''control items.' Suppose one switches 7 with 2 and 8 with 5. With these switchings of items one would end up with two sets of such: (1, 7, 4) and (3, 8, 6). That's two comparisons.

One then compares these two sets with each other.

If the orientation of the weighing doesn't change, then that means all of the items switched out are equal with the ones they were substituted with. That would mean that either item 1 or 6, the items not switched, is the different item.

If the orientation changes so that the two sets are equal then it is known that the different item was switched out of the system. This means that either items 2 or 5, the items that were removed from the two sets being weighed, is different.

If the orientations change then one knows that the different item has exchanged sets and hence changed the weight of the set. This would mean that either item 3 or 4 is the different item.

Keep note of the orientation of the weighing again. That would be two comparisons.

The third and final comparison requires one to take the two items that were suspected from the last step and comparing