Article ID Journal Published Year Pages File Type
4648449 Discrete Mathematics 2012 10 Pages PDF
Abstract

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

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,