Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648449 | Discrete Mathematics | 2012 | 10 Pages |
“The Baron’s Omni-sequence”, first defined by Khovanova and Lewis (2011) [5], is a sequence that gives for each nn the minimum number of weighings on balance scales that can verify the correct labeling of nn identically-looking coins with distinct integer weights between 1 gram and ngrams.In [5], Khovanova and Lewis provide upper and lower bounds for this sequence, where the upper bound follows from the use of a particular algorithmic scheme. We continue this investigation by providing new algorithms that provide better upper bounds, within a factor of 22 from the lower bounds (improving on Khovanova and Lewis’s 2.962.96). Furthermore, we show that these new algorithms are, under certain criteria, optimal within the framework of the present algorithmic scheme. We also discuss directions that may provide improvements within or over the scheme.