Münchhausen Matrices

Abstract

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