login
A174541
Baron Munchhausen's Sequence.
1
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, 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, 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
OFFSET
1,5
COMMENTS
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.
After a(1) = 0, a(n) is either 1 or 2 for all n.
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.
LINKS
M. Brand, Tightening the bounds on the Baron's Omni-sequence, Discrete Math., 312 (2012), 1326-1335.
T. Khovanova, K. Knop and A. Radul, Baron Munchhausen's Sequence, arXiv:1003.3406 [math.CO], 2010.
T. Khovanova, K. Knop, A. Radul, Baron Munchhausen's Sequence, J. Int. Seq. 13 (2010) # 10.8.7.
T. Khovanova, A. Radul, Another Coins Sequence
EXAMPLE
a(7) = 1 because the weighing 1 + 2 + 3 < 7 conclusively demonstrates the weight of the seven-gram coin.
MATHEMATICA
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 *)
PROG
(Scheme) ;;; The following Scheme program generates terms of Baron
;;; Munchhausen's Sequence.
(define (acceptable? n)
..(or (triangle? n)
......(= n 2)
......(triangle? (- n 1))
......(square? (triangle n))
......(square? (- (triangle n) 1))))
(stream-map
.(lambda (n)
...(if (= n 1)
.......0
.......(if (acceptable? n)
...........1
...........2)))
.(the-integers))
CROSSREFS
KEYWORD
nonn,nice
AUTHOR
Tanya Khovanova, Konstantin Knop, and Alexey Radul, Mar 21 2010
STATUS
approved