The OEIS is supported by the many generous donors to the OEIS Foundation.
%I #43 Dec 07 2019 12:18:28
%S 1,3,5,7,10,14,17,20,23,28,33,37,41,45,50,55,60,66,73,78,84,89,94,99,
%T 105,114,121,127,134,140,147,154,161,167,173,183,190,202,210,218,225,
%U 232,240,247,254,261,268,276,290,301,310,318,327,335,343,353,362,371,380,390,399,408,417,430,443,455,466,476,485,496,506
%N The mailbox manufacturer's problem, for the 2-mailbox case.
%C Given two identical mailboxes, each of which can hold up to n firecrackers, let M be the maximum number of firecrackers that can be simultaneously exploded in a mailbox without bursting it (and making it unusable for further testing). Assume that each mailbox can withstand an unlimited number of explosions of M or fewer firecrackers at a time. a(n) is the number of firecrackers needed to determine M, in the worst case, using an optimal strategy.
%C From _Jon E. Schoenfield_, Jan 11 2017: (Start)
%C As the number of mailboxes B increases without limit, the sequences appear to converge to A007078 (Optimal cost of search tree); the first 25 terms for cases B=1 (A000217), B=2 (this sequence), B=3 through B=6, and A007078 are as follows, where dots indicate a repeat of the value to the left:
%C .
%C n | B=1 B=2 B=3 B=4 B=5 B=6 A007078
%C ---+------------------------ -------
%C 1 | 1 .. .. .. .. .. 1
%C 2 | 3 .. .. .. .. .. 3
%C 3 | 6 5 .. .. .. .. 5
%C 4 | 10 7 .. .. .. .. 7
%C 5 | 15 10 9 .. .. .. 9
%C 6 | 21 14 12 .. .. .. 12
%C 7 | 28 17 16 15 .. .. 15
%C 8 | 36 20 20 19 .. .. 19
%C 9 | 45 23 .. .. .. .. 23
%C 10 | 55 28 26 .. .. .. 26
%C 11 | 66 33 29 .. .. .. 29
%C 12 | 78 37 32 .. .. .. 32
%C 13 | 91 41 35 .. .. .. 35
%C 14 | 105 45 39 38 .. .. 38
%C 15 | 120 50 45 41 .. .. 41
%C 16 | 136 55 50 45 .. .. 45
%C 17 | 153 60 55 49 .. .. 49
%C 18 | 171 66 60 54 53 .. 53
%C 19 | 190 73 65 61 57 .. 57
%C 20 | 210 78 69 67 62 .. 62
%C 21 | 231 84 73 .. 67 .. 67
%C 22 | 253 89 77 .. 73 72 72
%C 23 | 276 94 81 .. .. 77 77
%C 24 | 300 99 85 .. .. 83 83
%C 25 | 325 105 89 .. .. .. 89
%C (End)
%H Joerg Arndt, <a href="/A280433/b280433.txt">Table of n, a(n) for n = 1..9999</a>
%H Kattis, <a href="https://open.kattis.com/problems/mailbox">The Mailbox Manufacturers Problem</a>, from Norwegian/Swedish Championships 2002.
%F From _Jon E. Schoenfield_, Jan 10 2017: (Start)
%F Let f(L,U,B) be the number of firecrackers needed to determine M (in the worst case, using an optimal strategy), given that M is known to be in the closed interval [L, U] and B mailboxes remain available for testing. Then if B=1, we must sequentially test each integer number k of firecrackers from L+1 upward until the mailbox fails (since a failure will destroy our only remaining mailbox), and in the worst case (largest total number of firecrackers used) we will use L+1 + L+2 + ... + U firecrackers, so
%F f(L,U,1) = Sum_{k=L+1..U} k = (L+1+U)*(U-L)/2.
%F For B >= 2 and U > L, we have
%F f(L,U,B) = min_{k=L+1..U} (k + max(f(k,U,B), f(L,k-1,B-1)))
%F (where the minimum gives the best strategy (minimizing the total number of firecrackers needed), and max(f(k,U,B), f(L,k-1,B-1)) is the worst-case result from the outcomes of mailbox success and failure at a k-firecracker test)
%F and when L=U, we have
%F f(L,U,B) = 0 (since M has been determined).
%F Using the above recursive formula, we can compute
%F a(n) = f(0,n,2). (End)
%F It looks as though lim_{n->inf} a(n)/n^(3/2) = 0.818... - _Jon E. Schoenfield_, Jan 12 2017
%e For n = 3, the optimal strategy uses 2 firecrackers for the first test, and in the worst case, the mailbox holds up and we need to try 3 firecrackers, for a(3) = 2 + 3 = 5 in total.
%e For n = 6, the optimal strategy uses 3 firecrackers for the first test. In the worst case, the mailbox holds up and we try a second test with 5. Again, the worst case is that the mailbox withstands the test, so the third test uses 6, for a final sum of a(6) = 3 + 5 + 6 = 14.
%o (Python 2)
%o seen = {}
%o def solve(start, end, boxes):
%o tup = (start, end, boxes)
%o if boxes == 1 or start >= end-1:
%o val = (start + end) * (end-start+1) / 2
%o seen[tup] = val
%o return val
%o lowest = 100000000000000000
%o for x in range(end-1, start, -1):
%o firstup = (x+1, end, boxes)
%o first = seen[firstup] if firstup in seen else solve(x+1, end, boxes)
%o if first >= lowest:
%o break
%o secondtup = (start, x-1, boxes-1)
%o second = seen[secondtup] if secondtup in seen else solve(start, x-1, boxes-1)
%o if second >= lowest:
%o break
%o lowest = min(lowest, x + max(first, second))
%o seen[tup] = lowest
%o return lowest
%Y Cf. A000217, A007078, A180975.
%K nonn
%O 1,2
%A _Christofer Ohlsson_, Jan 03 2017
%E More terms from _Joerg Arndt_, Jan 11 2017