My solution of the NYT puzzle was exactly the same as Michael's: Reduce (7,7) to (6,6) … until you get to (2,2), then you have to do a 2 vs. 2 weighing and, if they balance, a 1 vs. 1. I'm still puzzled why the original puzzle asked for (7,7). Maybe Victor was as well, and asked the obvious question: For given L, how small can H be for (H,L) to be feasible? For example, (3,3) is feasible but (2,3) is not. -Veit On Jul 27, 2013, at 8:12 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
Neat type of problem!
It seems to me the easy reduction is that if you can solve (H heavy, L light) coins, then you can also solve (H+1, L+1): from (H+1, L+1) you can weigh random pairs of single coins against one another until you find two whose weights differ, at which point the scale keeps the heavier of the two, and you can discard the returned lighter one, getting to (H, L).
Ah -- if you do the same one-on-one weighings and *don't* throw away the identified light coin, you reduce to (H,L) from (H+1,L), which is what Victor intuited and asked for a proof of.
I'm not sure I understand the rules of the "You're not allowed to label" alternative. If I can tell which coins came from the heavier / lighter pan after a weighing, then I can do (2, 2), and therefore (n, n) for n>=2.
Rather than minimizing expected number of weighings, I'd like to maximize the number of heavy coins you can exhibit at the end. With (7, 7) you can certainly end up holding one heavy coin, but can you end up with two? Three?
--Michael