Here’s an old trick that we found useful for proving some tight complexity lower bounds. You are given *m* coins, each of weight either *a* or *b*, and a modern scale that can tell you the total weight of any chosen subset of coins. How many weighings do …read more

From:: Banach’s Algorithmic Corner