A186313 Baron Munchhausen's Omni-Sequence.

0, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3

Offset: 1

Author

Tanya Khovanova and Joel B. Lewis, Feb 17 2011

Keywords

• hard
• nonn
• more

Comments

a(n) is the minimal number of weighings necessary to differentiate unlabeled coins of weight 1, 2, ..., n grams on a two-pan balance. See the Khovanova-Lewis paper for more information.

We have 3 <= a(n) <= 4 for 20 <= n <= 26 and a(n) = 4 for 27 <= n <= 58.

In general, log_3(n) <= a(n) <= 2log_2(n).

Examples

			For n = 6, the weighings 6 = 1 + 2 + 3 and 1 + 6 < 3 + 5 uniquely identify the six coins 1, 2, 3, 4, 5, 6.
		

Links

• M. Brand, Tightening the bounds on the Baron's Omni-sequence, Discrete Math., 312 (2012), 1326-1335.
• Michael Brand, Munchhausen Matrices, Electronic Journal of Combinatorics, Vol. 19 (2012) #P40.
• Michael Brand, Lower bounds on the Munchhausen problem, arXiv preprint arXiv:1304.7075 [cs.IT], 2013.
• Michael Brand, Lower bounds on the Münchhausen problem, Australasian Journal of Combinatorics, Volume 59(1) (2014), Pages 81-85.
• T. Khovanova, Coins Sequence
• T. Khovanova, My First Polymath Project
• T. Khovanova and J. B. Lewis, Baron Munchhausen Redeems Himself: Bounds for a Coin-Weighing Puzzle, Electronic J. Combinatorics 18 (2011) P37.

Crossrefs

Cf. A174541.