And indeed Erich just independently said the same as in my last message. On Mon, Jul 29, 2013 at 10:29 AM, Erich Friedman <efriedma@stetson.edu>wrote:

the weighing of 2 coins versus 2 coins is a very powerful tool.

whenever we weigh AB<CD and lose D, either A=B (and are therefore light) or C is heavy.

so we can use this trick repeatedly to reduce the (H,L) problem to the (H-1,L-2) problem.

i can't for the life of me see how to use weighings of more than 3 coins effectively.

so i'm guessing this is optimal. that is, (H,L) is feasible for L <= 2H-2.

but i'd be glad to be proved wrong.

erich

On Jul 29, 2013, at 9:35 AM, Veit Elser wrote:

...

On Jul 28, 2013, at 6:56 AM, Erich Friedman <efriedma@stetson.edu> wrote:

...

...

More natural questions: What's the first feasible (H,L) with L > H?

How

...

...

...

about with L >= H + k for k=1, 2, 3, ...? Must some (H,L) work for any k?

i'm in the weird position of receiving math-fun posts, but am unable to post to the list.

...

but (3,4) is feasible. Nice solution! Just two quibbles:

randomly weigh AB against CD until AB<CD and D is removed. If EFG are the heavy ones then this will never happen, so you have to try out all three weighings to be able to detect that case.

...

then weigh A against B. if they don't balance, C is heavy. And if they do balance I would then say the problem has been reduced to (2,2) (because we've eliminated two light coins) which is already known to be feasible.

...

then randomly weigh CE against FG until they don't balance. the remaining coin from the heavy side is guaranteed to be heavy.

erich

-- Forewarned is worth an octopus in the bush.