A Dozen Golden Eggs, Part 2

Question

_{This is a variant of A Dozen Golden Eggs posted by TSLF, this time with the digital scale removed.}

You have twelve golden eggs arranged on the shelf according to shell thickness, with weight tags in ounces from 1 to 12. You've been told that two of the eggs were swapped by some culprit! You must put them back again in the right positions, but the only tool you have is a set of balance scales, with which you can compare the relative weight of one egg or group of eggs against another.

What is the minimum number of weighings needed to find out which two eggs were swapped?

_{Disclaimer: I don't know the correct answer.}

Answer 1

There are ${12\choose 2} = 66$ combinations, and $3^3 = 27 < 66 < 81 = 3^4$, so the best possible solution would be $4$ weighings. So all we need to do is find a plan that will always succeed in at most 4 weighings.

Step 1

Weigh (1,2,11,12) vs (5,6,7,8). This yields 24 cases where the scale tips left, 24 cases where it tips right, and 18 cases where the scale is even.

Tips Left

In this case, both 11 and 12 must be correct. Specifically, either 1 or 2 is swapped with one of (3-10) or 3 or 4 is swapped with (5-8).

Step 2 Weigh (1,12) vs (2,11). This yields 8 cases for each result.

If it tipped left, we know 1 is one of the swapped eggs. If it tipped right, we know 2 is one of the swapped eggs. In either case, we need to determine which of (3-10) is the other. To determine which:

Step 3: weigh (3,5,10) vs (4,6,8).

• Tip left: one of 4,6,8 is the egg. Weigh (4,11) vs (6,9).

• Tip right: one of 3,5,10 is the egg. Weigh (3,11) vs (5,9).

• Balance: one of 7,9 is the egg. Weigh (7,12) vs (9,10).

If Step 2 balanced, we know one of the swapped eggs is 3 or 4, and the other is one of (5,6,7,8).

Step 3: Weigh (4,5,6,7) vs (1,2,8,11).

• Tip left: one of the pairs (3,8) or (4,8). Weigh (3,12) vs (4,11).
• Tip right: one of the pairs (3,5), (3,6), (3,7). Weigh (5,12) vs (6,11).
• Balance: one of the pairs (4,5), (4,6), (4,7). Weigh (5,12) vs (6,11).

Tips Right

If the first weighing tipped right, then the procedure is much as above, swapping left vs right, and reversing the order of the numbers. A bit of rearrangement is needed to make the scales balance for step 3.

Balance

If the first weighing balanced, then there are 18 possibilities, with both swapped eggs on the left, both on the right, or both unweighed.

*Step 2: * Weigh (2,4,6) vs (5,7)

Tips Left. The swapped pair must be one of: (2,11), (2,12), (4,9), (4,10), (6,7) or (6,8). Weigh (1,4) vs (2,3) to determine which is the lightest swapped egg. Then weigh (1,X) vs (X+1) to determine which is the heavier swapped egg. (Eg. (1,9) vs (10). Tips left indicates 10 is light, tips right indicates 9 is light).

Tips Right. The swapped pair must be one of: (1,2), (3,4), (5,6), (5,8) or (7,8). Weigh (5,8) vs (1,12). Tip left: the pair is (5,6). Tip right: (1,2) or (7,8). Balance: (3,4) or (5,8). One more weighing is needed, at most.

Balances. The swapped pair must be one of: (1,11), (1,12), (11,12), (3,9), (3,10), (9,10), or (5,7). Weigh (1,4) vs (2,3).

Tips left: The lighter swapped egg is 1. Weigh (2,12) vs (3,11) to find the other.

Tips right: The lighter swapped egg is 3. Weigh (1,9) vs (10) to find the other.

Balances: The pair is one of (11,12), (9,10), or (5,7). Weigh (5,6) vs (9,2) to determine which of the three.

In all cases, it is possible to determine which pair is the swapped pair in at most 4 weighings. Since that is the minimum theoretically possible, that must be the answer.

Answer 2

Because after 10 hour nobody try to answer, I think we need community wiki to answer this.

I try to give partial answer.

weight [1,2] vs [3], if the scale is balanced, so

• [3] must be not swapped, you can use it as a balance stone.
• [1] and [2] can be swapped, but [1]+[2] can be used as another balance stone as [[3]]. To determine whether [1][2] is swapped or not, weight [1,3] vs [4]
  • if the scale is balanced so [1],[2] and [3] is not swapped,
  • if not there are many possibilities.

Answer 3

We could solve this with

a bubble sort, which would take at most 11 comparisons.

Once we find something out of order, we know we have one or both eggs, and continue until we find its place.

Eg. If 5 was swapped with 1: we start at the first slot, comparing "1" to 2, finding "1" is heavier. Then compare "1" to 3, etc. Until we find "1" is not heavier than 6.

So I guess technically the very least is 2, if eggs 1 and 2 were swapped. We compare "1" to "2", "1" would be heavier, then compare "1" to 3. 3 would be heavier so we know 1 and 2 were swapped.

Answer 4

I am interested in a sillier and harder variant/generalization:

What if the eggs were untagged and their ordered weights unconstrained?

I.e. Just the expected weight order were given (with somebody swapping two eggs), with no written weight values at all? Also, the weights being able to assume whatever possible values as long as they are ordered with only one swapping?

Here we go:

---

The weights form a list with:

Either 1 or 2 inversions. If two consecutive eggs $a$ and $a + 1$ are swapped the, the inversion would be just those two. If the non-consecutive eggs $a$ and $b$ are swapped, the inversions would be between eggs $a$ and $a + 1$ and between $b - 1$ and $b$.

Let's start with the naïve simple algorithm:

Simply weight eggs 1 and 2, then 2 and 3, then 3 and 4,..., until 11 and 12. With that, you will find the two inversions, then switch the leftest egg in the first inversion with the rightest one from the second. If there is only one inversion, just swap the two switched eggs. In the worst case, you will need 11 weighings and in the best only 1.

Lets try a simple optimization:

If after measuring eggs 10 and 11, you did not found the inversion, so you it must be eggs 11 and 12. If you found only one inversion, then eggs 11 and 12 are the second one. There would not be any need to weight them. So, the minimum number of weights is no more than 10.

However this will not work (as noted by @MMAdams). If the swapped eggs are 10 and 12, you won't be able to differentiate it from 10 and 11.

Is it possible to do it any better...

By measuring a lot of eggs at once?

Perhaps, but if we do that then:

If the eggs have very similar weight. E.g, the heaviest egg is just 1% heavier than the lightest, putting anything other than an equal number of eggs in each side of the balance will not give us any useful measurement, since the side which more eggs would always be the heaviest, which is not useful, since we don't need to do any weighing to know that.

So, the only form of doing an useful weighting is by weighting equal number of eggs in each side of the balance.

Further:

By measuring equals number of eggs in each side, we are effectively measuring the sum of differences of weight from the each individual egg to the lightest one.

And, of course, the difference in weight from the lightest one to itself is zero.

How could this go wrong?

If there is some way to hand-wave eggs weights that every possible way of weighing the eggs make the rightest side be the heaviest (other than the case of one egg in each side), then there would be no way to get useful information from measuring more than one egg with another one.

However, there is no way to do such weight hand-waving. The simple reason is because if we swap the left-side and right-side eggs from a measurement where the right side was the heaviest, then the left side will the heaviest.

Is there a better/worse way to make it go wrong?

But what if the heaviest side is always the one with the heaviest egg? This is almost the same as that.

Then, each weighing will only show where is the heaviest egg. This can be accomplished if the differences in eggs weights (not the eggs weights themselves) grows exponentially. E.g: $1000 g$, $1000.001 g$, $1000.002 g$, ..., $1001.024 g$, $1002.048 g$.

Another possibility is if the differences diminishes exponentially. In this case the heaviest side will always be the one that is not with the lightest egg. Eg. $1000 g$, $1001.024 g$, $1001.536 g$, $1001.768 g$, ..., $1002.041 g$, $1002.045 g$, $1002.047 g$, $1002.048 g$.

Why is this probably the worst possible combination?

I can't give a hard proof on that. But, I conjecture that this is indeed the worst scenario.

In the egg-weight-differences-exponentially-growing scenario, if we do any weighting and swaps a few eggs from one side to the other, nothing will change other than just saying where is the heaviest eggs. Adding or subtracting eggs other than the heaviest one will not be anything useful either. Something similar (but showing where the lightest is) happens in the exponentially diminishing differences scenario.

That seems to be bad, but is it exploitable anyway?

If you already know beforehand that the heaviest side will be the one with the heaviest egg (and you don't, I hand-waved this particular case), put 6 eggs in each side. Then select the 6 heaviest eggs and put 3 in each side. Get the three eggs from the heaviest side, plus one from the lightest and measure them. Get the two eggs from the heaviest side and compare them. This will give you what is the heaviest egg in 4 steps. But...

You don't need to know what is the heaviest egg. This is not what you want to know.

What if we try do measure incrementally (by adding eggs)?

In the egg-weight-differences-exponentially-growing scenario, once the heaviest egg was added, whatever added pair will not change anything. The same happens in the egg-weight-differences-exponentially-diminishing scenario. Further, you don't know which type of scenario you are handling.

And using a subtractive method?

This might (or might not) tell you only that at some time you subtracted the heaviest egg in the egg-weight-differences-exponentially-growing scenario or the lightest one in the egg-weight-differences-exponentially-diminishing scenario. If you are unlucky and those are left to the last step, you aren't gaining information.

Can we just sort the eggs?

Yes, let's suppose that you start with 6 eggs in each side. Suppose that the measurement was useful somehow (I doubt). Then, you proceed by comparing 3 to 3, twice. Then from each one of the four triplets, compare one to the other leaving the third off. This will give you 7 weighings. This shows that whatever is the lowest number of weighings, it is no less than 7. However, this doesn't means that it is exactly 7, since we don't know yet how to extract useful information from those weighings (if this would in fact be possible).

There is really no way better than that?

If you are constrained to take equals number of eggs in each side (and as I already explained, you are) of the balance, no. This is the minimum way to classify each individual egg each one in its own group.

We really need to separate them in that way in order to find (somehow, I don't think that this is sufficient) where is a possible inversion. If we end with more than one egg in a group, we won't be able to know if the are or aren't inverted.

Can the other algorithm use that same optimization?

No, we have three eggs in the last step.

Anyway, we have pretty constrained it:

The minimum is no more than 11 and no less than 7.

Can we fix that new recursive algorithm?

Let's suppose that in the first step you added some 6 in the left side and the other 6 in the right, choosing them by some arbitrary rule. If the swapped eggs were in different sides of the balance in the first weighing or any of the 3 vs 3 weighings, you won't be able to tell. Those 7 weighings will not give you enough information to denounce you were the inversion is, and you have only 2 weighings left to beat the other guaranteed algorithm (with 4 you will tie, so, this will not be interesting afterall).

Is it doable with no more than just 3 more weighings?

Let's suppose that the inverted eggs were in the same side in the first 6 vs 6 weighing, but were separated by one of the four 3 vs 3 weighing. You would need at least 2 weighings to differentiate those cases (since each weighing give you only one bit of information), and you would need at least 2 bits for differentiating between those 4 cases. But there is still the case were they were separated by the first weighing, so 2 extra bits of information will not be enough. Further, in the last steps, you left out 4 eggs from the last weighings. So if you weighted eggs a, b and c and there was one inversion, you are still lacking information, and you would still need at least more 4 weighings (or perhaps 3 if the optimization of not performing the last weighing could apply). Anyway, you are screwed in this method.

Although this is not a hard proof, I think that it is a pretty strong conjecture that the minimum number of weighings is:

11 - By using the naïve algorithm.

Answer 5

I will edit time by time here until I finish since the answer is kinda long.

First part will be "all the way everything is equal":

1- $A_{1e}:=\{1,2,3,10,11,12\}$ and $B_{1e}:=\{4,5,6,7,8,9\}$.

If this scaling is equal, there are 30 number of possibilities, but we know that there is no relation between $A_{1e}$ members and $B_{1e}$ member for switching. Then another measurement:

2- $A_{2e}:=\{1,2,3,11,12\}$ and $B_{2e}:=\{5,7,8,9\}$.

What if there is inequality here?

if $A_{2e}>B_{2e}$, then only possibilities become $\{1,10\}$, $\{2,10\}$, $\{3,10\}$, $\{4,5\}$, $\{6,7\}$, $\{6,8\}$, $\{6,9\}$. So from 30 to 8. I will not continue for this any more since it is easy to say that you can find at most 4 tries with a few possibilities from this point.

if $A_{2e}<B_{2e}$, same thing as previous. Possibilities are kinda not many and you can find at most 4 tries without any problem.

So What if there is equality:

3- $A_{3e}:=\{1,11,12\}$ and $B_{3e}:=\{7,8,9\}$.

This is our third try and if there is still equality, the possibilities become: $\{2,3\}$, $\{1,11\}$, $\{1,12\}$, $\{11,12\}$, $\{7,8\}$, $\{8,9\}$, $\{7,9\}$ and $\{4,6\}$. So After 3 tries with balance scale, we have decreased the number of possibities to $9$.

For the last part we need to add some specific numbers:

4- $A_{4e}:=\{1,2,12\}$ and $B_{4e}:=\{6,9\}$.

So we can test $\{2,3\}$, $\{4,6\}$ while checking other possibities as well. So If there is an equality, only possibility becomes $\{7,8\}$ or $\{1,12\}$. and with last call, we can easily find which one.

NOTE: I will edit the answer later, the answer will be

5