Münchhausen matrices (Q1953350)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Münchhausen matrices |
scientific article |
Statements
Münchhausen matrices (English)
0 references
7 June 2013
0 references
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.
0 references
Baron's omni-sequence
0 references
Münchhausen
0 references
coin weighing
0 references
verification
0 references