Using your Head is Permitted

Consider the following puzzle:

You have n identically looking coins, each with a distinct integer weight in grams, between 1 gram and n grams (i.e., the weights are 1g, 2g,..., ng). This is where it gets interesting: you know which coin has which weight, and you have labeled them accordingly. However, because I can't tell the coins apart, I have asked you to prove to me that your labeling is correct. (Clarification: I know that the coins weigh 1g, 2g,..., ng. I just don't know which is which.)

To do so, all you have at your disposal are balance scales. You can put any subset of the coins on any side of the scales, but you cannot put on the scales anything other than the coins themselves. Naturally, you also cannot place a single coin multiple times on the scales in any given weighing (though the coins can be reused between weighings).

The question is: what is the minimum number of weighings, B(n), with which you can prove undeniably that your labeling of the coins is the correct one?

I will give references about this riddle on the solution page, as well as a more thorough explanation of what makes it a special (75th anniversary) riddle. For now, I will say that the success criterion for this riddle is somewhat fuzzier than in our usual riddles.

To get your name on the solvers list, state and prove the complexity of B(n) as a function of n. (You are required to give the exact complexity, in the Θ(f(n)) sense, not just upper and lower bounds. That is, you should find a function, f(n), such that there exist two constants, L and H, such that for every large enough n the equation

holds. Finding L and H is not required, nor is it required to specify which n values are "large enough".)

A special mention (and/or an asterisk next to his/her name) will be given to anyone who can say more interesting things about B(n), beyond its complexity in n. I reserve the right to decide what is interesting in this context.

(If I deem the observation interesting enough, a special mention and/or a place on the solvers list can be awarded even to someone who did not solve the basic question about the complexity of B(n).)

Such extra questions that you may wish to tackle include

1. Give tighter upper bounds than the complexity ones.
2. Give tighter lower bounds than the complexity ones.
3. Determine if B(n) is a monotone sequence.

Good luck! And thank you for reading Using your Head is Permitted and keeping it going for 75 months already!

List of solvers: