The complexity of B(n) is Θ(log n).
The fact that this is a lower bound on the complexity is evident from B(n)≥log3 n, which can be proved as follows. In each weighing, a coin plays one of 3 roles: it can be on the left pan, on the right pan or held out. This indicates that the full role played by the coin in all k weighings is one of 3k possibilities. If n>3k, there are at least two coins that play the same role in all k weighings. Hence, these cannot be disambiguated.
Proving that B(n) is also upper-bounded by O(log n) takes a little more effort.
First, let us get a lower bound estimate on the weights of some of the coins. We do this by the following sequence of weighings:
(This notation should be read as "place the coin labeled '1' on the left pan and weigh it against coin '2' on the right pan, ascertaining that '1' is lighter than '2'; next, place the coins labeled '1' and '2' on the left pan and weigh them against the coin labeled '3' on the right pan, ascertaining that the pans balance each other; etc.)
We continue with the weighings described above, always matching the coin that weighs exactly like the sum of all previous coins, until no such coin exists. (The total weight is larger than ng.) This gives a lower bound to the weights of the coins labeled 2, 3, 6, 12 and any other 3*2i. The coin labeled 1 is also lower-bounded, simply because there is no lighter coin.
The last coin to be verified in this process has a weight, 3*2i (for some i), in the range
If 3*2i is actually equal to n, the above weighings also upper-bound the weights of all coins involved, and thereby establish their exact weights. If not, consider the following.
Any weight between 0 and n grams can be generated as the sum of the weights of some subset of the coins already used. (The 3*2i coins can generate any weight that is a multiple of 3 in this range. Together with '1' and '2', this completes to any weight in the range.) Let us therefore take the subset that sums up to n and weigh it against the 'n' coin. This will upper-bound the coins used in this last weighing, thereby fully establishing the weights of the '1' and '2' coins, thereby fully establishing the weights of all coins which have been weighed so far. (Clearly, if '1' and '2' are correct than all coins are correct. If '1' and '2' are incorrect, then their sum is at least 4 and all remaining coins are at least 1.25 times heavier than their labels. This would indicate that the weights of the coins involved in the last weighing sum up to more than n, in which case no single coin would have counterbalanced all of them. Because we did manage to counterbalance all by use of a single coin, we know that the weights are all accurate.)
So far, we've used up O(log n) weighings and have verified the weights of a subset of the coins that can generate any sum in the range between 0 and n. We'll call these the 'helper coins'. Let us now use these helper coins in order to verify the weights of all remaining coins in an additional O(log n) weighings.
The idea now is as follows. First, take all helper coins and remove them from the full set of n coins. Let us call the set of remaining coins S. In all subsequent weighings, we first take the coins of S and partition them according to the roles already played by each coin. After i weighings, this will partition S into 3i piles. We next take the coins in each pile and divide them up into three sets: the lightest coins, the heaviest coins and the rest of the coins. The three sets should be picked so that the total sum of the weight within each set is roughly a third of the total.
It is not always possible to make it into a third exactly (sometimes the total is not even a multiple of 3), but it is clear that we can balance them well enough that the difference between the grand total of the weight of all 'lightest coin' sets and the grand total of the weight of all 'heaviest coin' sets will differ by no more than n grams. (If they differ by more, simply add/subtract a coin from the third set to make the difference smaller. Any coin picked will do the trick.)
Now, place all 'light coins' on the left pan, all 'heavy coins' on the right pan, and use the helper coins in order to get the pans to balance out completely.
You will note that even though the weights of the non-helper coins are not known at this stage, for any two partitions of S it is known whether the coins in partition A are heavier or lighter than the coins in partition B. The answer will always be the same for all pairs of coins picked one from A and one from B. For this reason, whenever a partition is reduced to a size of 1, the weight of the coin in it becomes fully known. At this point, it can be removed from set S.
It is not difficult to see that this process must terminate, when all coin weights have been verified, in O(log n) weighings. When we divide the partitions into three, the number of coins in each set can be made to be never less than 1-sqrt(2/3) and never more than sqrt(1/3) of the total number of coins in the original partition. The later correction (in order to make sure that the total weights differ by no more than n) can be made by never picking more than a single coin from each subset. In total, this means that the sizes of the partitions decrease exponentially, and the process cannot continue for more than O(log n) steps.
(Some fine print is left here for the reader.)
Q.E.D.
Now, as promised, some references.
The sequence B(n) is called Baron Münchhausen's Omni-sequence (sequence A186313 of the Online Encyclopedia of Integer Sequences). The name is derived from a variation published by Alexander Shapovalov, which appeared in the regional round of the All-Russian Math Olympiad in 2000. In this variation, the solver is asked to find the optimal set of weighings that derives the weight of at least one coin, for the special case n=8. The general case was tackled by Tanya Khovanova, Konstantin Knop and Alexey Radul, who dubbed this variant Baron Münchhausen's Sequence. (It is sequence A174541 of the OEIS.)
However, The Baron's Omni-sequence (verifying the weights of all coins, rather than just one coin) is older than its name. It first appeared in a puzzle due to Sergey Tokarev at the last round of the Moscow Math Olympiad in 1991, where it was asked for the special case of n=6.
As you may have guessed, part of what makes this 75th anniversary riddle special is that the problem is still open. The complexity of B(n) was proved by Tanya Khovanova and Joel Brewster Lewis, but that's very far from a full characterization of the omni-sequence (which, for comparison, the "sequence", A174541, has).
The main thing, however, that makes this a special riddle is that it has become a personal topic of interest of mine. I view the Münchhausen problem as a new and hitherto unexplored type of problem, which I refer to as a "verification" problem. (Technically, a verification problem is the problem of finding the communication complexity of a set under restrictions to the communication protocol.)
As a result of this interest, I have published several papers on the problem. The first dealt with improving the constants over Khovanova and Lewis's method (a simplified version of which is the solution published here).
Some months later, I wrote another paper, which introduces a completely novel technique for how to verify the coins' weights (which I find very elegant, but requires a lot of technical details to prove and/or explain in full), and this method managed to pin down B(n) to the narrow gap between log3 n and log3 n+O(log log n).
A third paper, currently still under review but available here, also proposes a first non-trivial lower bound on the problem, namely 3B(n)≥n+Ω(log log n). Unlike the best upper bound, this lower bound offers only little improvement over the trivial solution, but, nevertheless, nothing better is known.
Other than these results, nothing is presently known about the problem. In particular, it is still not known whether the sequence is monotone. Indeed, closing this problem would be a spectacular result.
As mentioned, I view this problem as the tip of the iceberg for an entire, hitherto unexplored genre of mathematical questions. I can only encourage all readers who wish to pursue either the Münchhausen problem or any of its generalizations further. It remains a fantastic and highly intriguing open problem.
Last note: I am indebted to Ian Wanless, for having introduced me to this fascinating problem to begin with.