Münchhausen matrices (Q1953350)

Summary: ''The Baron's omni-sequence'', \(B(n)\), first defined by \textit{T. Khovanova} and \textit{J. B. Lewis} [Electron. J. Comb. 18, No. 1, Research Paper P37, 14 p. (2011; Zbl 1229.05266)], 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 \(O(\log n)\). We introduce new theoretical tools for the study of this problem, and show that \(B(n)\) is \(\log_3 n + 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.