Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #23 Dec 11 2021 11:49:27
%S 0,1,1,1,2,1,1,1,2,1,1,2,2,2,1,1,2,2,2,2,1,1,2,2,1,2,2,1,1,2,2,2,2,2,
%T 2,1,1,2,2,2,2,2,2,2,1,1,2,2,1,2,2,2,2,2,1,1,2,2,2,2,2,2,2,2,2,1,1,2,
%U 2,2,2,2,2,2,2,2,2,1,1,2,2,2,2,2,2,2,2,2,2,2,1,1,2,2,2,2,2,2,2,2,2,2,2,2,1
%N Baron Munchhausen's Sequence.
%C Let n coins weighing 1, 2, ..., n grams be given. Suppose Baron Munchhausen knows which coin weighs how much, but his audience does not. Then a(n) is the minimum number of weighings the Baron must conduct on a balance scale, so as to unequivocally demonstrate the weight of at least one of the coins.
%C After a(1) = 0, a(n) is either 1 or 2 for all n.
%C a(n) = 1 for n triangular, n triangular-plus-one, T_n a square, and T_n a square-plus-one, where T_n is the n-th triangular number; a(n) = 2 for all other n > 1.
%H M. Brand, <a href="https://doi.org/10.1016/j.disc.2011.12.026">Tightening the bounds on the Baron's Omni-sequence</a>, Discrete Math., 312 (2012), 1326-1335.
%H T. Khovanova, K. Knop and A. Radul, <a href="https://arxiv.org/abs/1003.3406">Baron Munchhausen's Sequence</a>, arXiv:1003.3406 [math.CO], 2010.
%H T. Khovanova, K. Knop, A. Radul, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Khovanova/khova4.html">Baron Munchhausen's Sequence</a>, J. Int. Seq. 13 (2010) # 10.8.7.
%H T. Khovanova, A. Radul, <a href="http://blog.tanyakhovanova.com/?p=179">Another Coins Sequence</a>
%e a(7) = 1 because the weighing 1 + 2 + 3 < 7 conclusively demonstrates the weight of the seven-gram coin.
%t triangularQ[n_] := IntegerQ[ Sqrt[8n+1]]; a[1] = 0; a[n_ /; triangularQ[n] || triangularQ[n-1] || IntegerQ[ Sqrt[n*(n+1)/2]] || IntegerQ[ Sqrt[n*(n+1)/2 - 1]]] = 1; a[_] = 2; Table[a[n], {n, 1, 105}] (* _Jean-François Alcover_, Jul 30 2012, after comments *)
%o (Scheme) ;;; The following Scheme program generates terms of Baron
%o ;;; Munchhausen's Sequence.
%o (define (acceptable? n)
%o ..(or (triangle? n)
%o ......(= n 2)
%o ......(triangle? (- n 1))
%o ......(square? (triangle n))
%o ......(square? (- (triangle n) 1))))
%o (stream-map
%o .(lambda (n)
%o ...(if (= n 1)
%o .......0
%o .......(if (acceptable? n)
%o ...........1
%o ...........2)))
%o .(the-integers))
%Y Cf. A000217, A000124, A001108, A072221, A186313.
%K nonn,nice
%O 1,5
%A _Tanya Khovanova_, _Konstantin Knop_, and Alexey Radul, Mar 21 2010