A280433 The mailbox manufacturer's problem, for the 2-mailbox case.
1, 3, 5, 7, 10, 14, 17, 20, 23, 28, 33, 37, 41, 45, 50, 55, 60, 66, 73, 78, 84, 89, 94, 99, 105, 114, 121, 127, 134, 140, 147, 154, 161, 167, 173, 183, 190, 202, 210, 218, 225, 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
Offset: 1
Keywords
Examples
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. 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.
Links
- Joerg Arndt, Table of n, a(n) for n = 1..9999
- Kattis, The Mailbox Manufacturers Problem, from Norwegian/Swedish Championships 2002.
Programs
-
Python
seen = {} def solve(start, end, boxes): tup = (start, end, boxes) if boxes == 1 or start >= end-1: val = (start + end) * (end-start+1) // 2 seen[tup] = val return val lowest = 100000000000000000 for x in range(end-1, start, -1): firstup = (x+1, end, boxes) first = seen[firstup] if firstup in seen else solve(x+1, end, boxes) if first >= lowest: break secondtup = (start, x-1, boxes-1) second = seen[secondtup] if secondtup in seen else solve(start, x-1, boxes-1) if second >= lowest: break lowest = min(lowest, x + max(first, second)) seen[tup] = lowest return lowest print([solve(1, n, 2) for n in range(1, 40)])
Formula
From Jon E. Schoenfield, Jan 10 2017: (Start)
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(L,U,1) = Sum_{k=L+1..U} k = (L+1+U)*(U-L)/2.
For B >= 2 and U > L, we have
f(L,U,B) = min_{k=L+1..U} (k + max(f(k,U,B), f(L,k-1,B-1)))
(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)
and when L=U, we have
f(L,U,B) = 0 (since M has been determined).
Using the above recursive formula, we can compute
a(n) = f(0,n,2). (End)
It looks as though lim_{n->inf} a(n)/n^(3/2) = 0.818... - Jon E. Schoenfield, Jan 12 2017
Extensions
More terms from Joerg Arndt, Jan 11 2017
Comments