login
A280433
The mailbox manufacturer's problem, for the 2-mailbox case.
1
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,2
COMMENTS
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.
From Jon E. Schoenfield, Jan 11 2017: (Start)
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:
.
n | B=1 B=2 B=3 B=4 B=5 B=6 A007078
---+------------------------ -------
1 | 1 .. .. .. .. .. 1
2 | 3 .. .. .. .. .. 3
3 | 6 5 .. .. .. .. 5
4 | 10 7 .. .. .. .. 7
5 | 15 10 9 .. .. .. 9
6 | 21 14 12 .. .. .. 12
7 | 28 17 16 15 .. .. 15
8 | 36 20 20 19 .. .. 19
9 | 45 23 .. .. .. .. 23
10 | 55 28 26 .. .. .. 26
11 | 66 33 29 .. .. .. 29
12 | 78 37 32 .. .. .. 32
13 | 91 41 35 .. .. .. 35
14 | 105 45 39 38 .. .. 38
15 | 120 50 45 41 .. .. 41
16 | 136 55 50 45 .. .. 45
17 | 153 60 55 49 .. .. 49
18 | 171 66 60 54 53 .. 53
19 | 190 73 65 61 57 .. 57
20 | 210 78 69 67 62 .. 62
21 | 231 84 73 .. 67 .. 67
22 | 253 89 77 .. 73 72 72
23 | 276 94 81 .. .. 77 77
24 | 300 99 85 .. .. 83 83
25 | 325 105 89 .. .. .. 89
(End)
LINKS
Kattis, The Mailbox Manufacturers Problem, from Norwegian/Swedish Championships 2002.
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
EXAMPLE
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.
PROG
(Python 2)
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
CROSSREFS
KEYWORD
nonn
AUTHOR
Christofer Ohlsson, Jan 03 2017
EXTENSIONS
More terms from Joerg Arndt, Jan 11 2017
STATUS
approved