06015227

j

06015227 Brand, Michael Tightening the bounds on the Baron's omni-sequence. Discrete Math. 312, No. 7, 1326-1335 (2012). 2012 Elsevier Science B.V. (North-Holland), Amsterdam EN Baron's omni-sequence M\"unchhausen coin weighing verification Zbl 1229.05266

doi:10.1016/j.disc.2011.12.026

Summary: ``The Baron's omni-sequence'', first defined by {\it P. Khovanova} and {\it J. B. Lewis} [Electron. J. Comb. 18, No. 1, Research Paper P37, 14 p., electronic only (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. {\it P. Khovanova} and {\it J. B. Lewis} [loc. cit.] 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 2 from the lower bounds (improving on Khovanova and Lewis' 2.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.