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,3

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).

Links

Table of n, a(n) for n=1..19.

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.

Example

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.

Crossrefs

Cf. A174541.

Sequence in context: A133874 A053384 A321857 * A165020 A235224 A092139

Adjacent sequences: A186310 A186311 A186312 * A186314 A186315 A186316

Keyword

hard,nonn,more

Author

Tanya Khovanova and Joel B. Lewis, Feb 17 2011

Status

approved