How to find solutions of coin weighing problems with multiple light coins and prove optimality

290 Views Asked by At

So the classical coin weighing problem with $3^n$ coins all equal weight except for one light coin, where we want to find the one light coin, can be solved optimally with $n$ uses of a balancing scale, assuming that the scale either tips in the heavy direction or balances if the two weights are equal. But what if we have $N$ coins (it's possible that $N$ should be parametrized for simplicity, like $N = 3^n$ but I'm not sure how), and we know there are $k$ lighter coins all of equal weight (so there are $N \choose k$ possibilities for which coins might be lighter). How can the scale optimally be used to find the $k$ lighter coins? And what if the $k$ lighter coins are all of different weights and we want to know the $k$ lighter coins as well as their ordering according to weight? Then there are $k! {N \choose k}$ possibilities. Again how can the scale optimally be used to find the $k$ lighter coins and their weight ordering?