Otdfbt

I've gotten this riddle and have been struggling with solving it:

Suppose you have 20 stones which have different weights [0 ... n] . You have no way of measuring the weight of any stone individually, instead you can only measure them by putting 10 on each side of a balance. After doing this you see which "group" of stones is heavier. You can do this only 10 times in total. You can also switch the stones from either side to the other as much as you want between the measurements.

Your task is to find a stone for which you can be certain is not the lightest of them all.

All the stones are marked, so you always know which is which. Their appearance or anything similar does not help you with to determine their weight, the only way you can do it is by putting it on the balance.

Measure 10 and 10.

In each subsequent weighing you change one of the originals of one side for one of the originals of the other side.

At some point, the balance turns around.

The stone that you have put on the side that has come down is not the lightest, because the other is lighter than that.

If at the tenth weighing the sides have not been turned around, the only original stone left on the side that is below is not the lightest.

Here's a solution that needs at most

5

weighings.

For convenience, I arbitrarily number each stone on side "A" (which I declare to be the lighter side for convenience) of the balance in the first weighing to be stones 1, 3, 5...19 and each stone on the heaver side B 2, 4, 6...20. The original weighing of all of the stones is taken to count toward the weighing total, but will be named "step zero" for convenience, because it's the only possible thing to do at the beginning.

Note: if at any point the scale balances, a not-lightest stone can be found in one more weighing by switching any two stones and seeing which way the balance tips.

Step one:

Swap stones 1, 3, 5, and 7 with stones 2, 4, 6, and 8. If the balance tips, you would skip to step 3, but that wouldn't be worst-case scenario (as you will see), so we won't skip ahead. We assume the balance does not tip. Total weighings: 2

Step two:

Swap stones 9, 11, 13, and 15 with stones 10, 12, 14, and 16. If the balance tips doesn't tip, you would skip to step 4, but that's not the worst case, so we will assume that the balance does tip. Total weighings: 3

Step three:

Swap four of the 8 stones that you have just swapped. Assuming that we are still following the worst case, swap stones 9 and 11 with 10 and 12. If the scale does not tip back to side B, then you know that switching 13 and 15 with 14 and 16 will. Total weighings: 4

Step four:

Regardless of which route we took to get here, we currently have four stones which we know either have tipped the scale when swapped, or would tip the scale when swapped. Swap two of them across the balance. If the scale doesn't change state when these are swapped, then the unswapped stone on the side that the scale was expected to tip away from is definitely not the lightest stone. If the scale does change state, the swapped stone that ended up on the side that the scale just tipped toward is definitely _not the lightest stone. Total weighings: 5

And there's your answer!

An optimization on Hermes's solution:

You have 2n stones numbered 0 to 2n-1.


Weigh stones 0..n-1 against stones n..2n-1.

If it balances, just swap 2 stones, the scale must tip to one side. The stone you added to the heavier side is not the lightest.

Else, let's say it tips left. Stones 0..(n-1) are left and the rest are right.


Consider what happens if you weigh stones k..(k+n-1) against the rest.
For k=0 the scale tips left, for k=n it tips right. At some point there is a value 'a' such that the scale tips left for k=a, but balances or tips right for k=a+1.


To find 'a' do a binary search: set a=0, b=n. Then choose k=(a+b)/2 rounded down. If the scale tips left, set a=k and restart, else set b=k and restart. When a+1=b then you are done.


From k=a to k=a+1, stone (a) is moved right and stone (a+n) is moved left. If it tips the scale, stone (a) is heavier than stone (a+n). You can pick stone (a) as guaranteed not the lightest.


This method requires at most 5 weighings for 20 stones.