Münchhausen matrices

Michael Brand¹

¹Faculty of IT, Monash University

The electronic journal of combinatorics, Tome 19 (2012) no. 4

Résumé

"The Baron's omni-sequence", $B(n)$, first defined by Khovanova and Lewis (2011), is a sequence that gives for each $n$ the minimum number of weighings on balance scales that can verify the correct labeling of $n$ identically-looking coins with distinct integer weights between $1$ gram and $n$ grams.A trivial lower bound on $B(n)$ is $\log_3 n$, and it has been shown that $B(n)$ is $\text{O}(\log n)$.We introduce new theoretical tools for the study of this problem, and show that $B(n)$ is $\log_3 n + \text{O}(\log \log n)$, thus settling in the affirmative a conjecture by Khovanova and Lewis that the true growth rate of the sequence is very close to the natural lower bound.

Détail

DOI : 10.37236/2342

Classification : 11B75, 05B20, 05D99, 05A99
Mots-clés : Baron's omni-sequence, Münchhausen, coin weighing, verification